2018-11-20 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-ssa-sccvn.c
blob941752e7887a0be27b7bd956d7939b4264a422be
1 /* SCC value numbering for trees
2 Copyright (C) 2006-2018 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "ssa.h"
29 #include "expmed.h"
30 #include "insn-config.h"
31 #include "memmodel.h"
32 #include "emit-rtl.h"
33 #include "cgraph.h"
34 #include "gimple-pretty-print.h"
35 #include "alias.h"
36 #include "fold-const.h"
37 #include "stor-layout.h"
38 #include "cfganal.h"
39 #include "tree-inline.h"
40 #include "internal-fn.h"
41 #include "gimple-fold.h"
42 #include "tree-eh.h"
43 #include "gimplify.h"
44 #include "flags.h"
45 #include "dojump.h"
46 #include "explow.h"
47 #include "calls.h"
48 #include "varasm.h"
49 #include "stmt.h"
50 #include "expr.h"
51 #include "tree-dfa.h"
52 #include "tree-ssa.h"
53 #include "dumpfile.h"
54 #include "cfgloop.h"
55 #include "params.h"
56 #include "tree-ssa-propagate.h"
57 #include "tree-cfg.h"
58 #include "domwalk.h"
59 #include "gimple-iterator.h"
60 #include "gimple-match.h"
61 #include "stringpool.h"
62 #include "attribs.h"
63 #include "tree-pass.h"
64 #include "statistics.h"
65 #include "langhooks.h"
66 #include "ipa-utils.h"
67 #include "dbgcnt.h"
68 #include "tree-cfgcleanup.h"
69 #include "tree-ssa-loop.h"
70 #include "tree-scalar-evolution.h"
71 #include "tree-ssa-sccvn.h"
73 /* This algorithm is based on the SCC algorithm presented by Keith
74 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
75 (http://citeseer.ist.psu.edu/41805.html). In
76 straight line code, it is equivalent to a regular hash based value
77 numbering that is performed in reverse postorder.
79 For code with cycles, there are two alternatives, both of which
80 require keeping the hashtables separate from the actual list of
81 value numbers for SSA names.
83 1. Iterate value numbering in an RPO walk of the blocks, removing
84 all the entries from the hashtable after each iteration (but
85 keeping the SSA name->value number mapping between iterations).
86 Iterate until it does not change.
88 2. Perform value numbering as part of an SCC walk on the SSA graph,
89 iterating only the cycles in the SSA graph until they do not change
90 (using a separate, optimistic hashtable for value numbering the SCC
91 operands).
93 The second is not just faster in practice (because most SSA graph
94 cycles do not involve all the variables in the graph), it also has
95 some nice properties.
97 One of these nice properties is that when we pop an SCC off the
98 stack, we are guaranteed to have processed all the operands coming from
99 *outside of that SCC*, so we do not need to do anything special to
100 ensure they have value numbers.
102 Another nice property is that the SCC walk is done as part of a DFS
103 of the SSA graph, which makes it easy to perform combining and
104 simplifying operations at the same time.
106 The code below is deliberately written in a way that makes it easy
107 to separate the SCC walk from the other work it does.
109 In order to propagate constants through the code, we track which
110 expressions contain constants, and use those while folding. In
111 theory, we could also track expressions whose value numbers are
112 replaced, in case we end up folding based on expression
113 identities.
115 In order to value number memory, we assign value numbers to vuses.
116 This enables us to note that, for example, stores to the same
117 address of the same value from the same starting memory states are
118 equivalent.
119 TODO:
121 1. We can iterate only the changing portions of the SCC's, but
122 I have not seen an SCC big enough for this to be a win.
123 2. If you differentiate between phi nodes for loops and phi nodes
124 for if-then-else, you can properly consider phi nodes in different
125 blocks for equivalence.
126 3. We could value number vuses in more cases, particularly, whole
127 structure copies.
130 /* There's no BB_EXECUTABLE but we can use BB_VISITED. */
131 #define BB_EXECUTABLE BB_VISITED
133 static tree *last_vuse_ptr;
134 static vn_lookup_kind vn_walk_kind;
135 static vn_lookup_kind default_vn_walk_kind;
137 /* vn_nary_op hashtable helpers. */
139 struct vn_nary_op_hasher : nofree_ptr_hash <vn_nary_op_s>
141 typedef vn_nary_op_s *compare_type;
142 static inline hashval_t hash (const vn_nary_op_s *);
143 static inline bool equal (const vn_nary_op_s *, const vn_nary_op_s *);
146 /* Return the computed hashcode for nary operation P1. */
148 inline hashval_t
149 vn_nary_op_hasher::hash (const vn_nary_op_s *vno1)
151 return vno1->hashcode;
154 /* Compare nary operations P1 and P2 and return true if they are
155 equivalent. */
157 inline bool
158 vn_nary_op_hasher::equal (const vn_nary_op_s *vno1, const vn_nary_op_s *vno2)
160 return vno1 == vno2 || vn_nary_op_eq (vno1, vno2);
163 typedef hash_table<vn_nary_op_hasher> vn_nary_op_table_type;
164 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type;
167 /* vn_phi hashtable helpers. */
169 static int
170 vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2);
172 struct vn_phi_hasher : nofree_ptr_hash <vn_phi_s>
174 static inline hashval_t hash (const vn_phi_s *);
175 static inline bool equal (const vn_phi_s *, const vn_phi_s *);
178 /* Return the computed hashcode for phi operation P1. */
180 inline hashval_t
181 vn_phi_hasher::hash (const vn_phi_s *vp1)
183 return vp1->hashcode;
186 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
188 inline bool
189 vn_phi_hasher::equal (const vn_phi_s *vp1, const vn_phi_s *vp2)
191 return vp1 == vp2 || vn_phi_eq (vp1, vp2);
194 typedef hash_table<vn_phi_hasher> vn_phi_table_type;
195 typedef vn_phi_table_type::iterator vn_phi_iterator_type;
198 /* Compare two reference operands P1 and P2 for equality. Return true if
199 they are equal, and false otherwise. */
201 static int
202 vn_reference_op_eq (const void *p1, const void *p2)
204 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
205 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
207 return (vro1->opcode == vro2->opcode
208 /* We do not care for differences in type qualification. */
209 && (vro1->type == vro2->type
210 || (vro1->type && vro2->type
211 && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type),
212 TYPE_MAIN_VARIANT (vro2->type))))
213 && expressions_equal_p (vro1->op0, vro2->op0)
214 && expressions_equal_p (vro1->op1, vro2->op1)
215 && expressions_equal_p (vro1->op2, vro2->op2));
218 /* Free a reference operation structure VP. */
220 static inline void
221 free_reference (vn_reference_s *vr)
223 vr->operands.release ();
227 /* vn_reference hashtable helpers. */
229 struct vn_reference_hasher : nofree_ptr_hash <vn_reference_s>
231 static inline hashval_t hash (const vn_reference_s *);
232 static inline bool equal (const vn_reference_s *, const vn_reference_s *);
235 /* Return the hashcode for a given reference operation P1. */
237 inline hashval_t
238 vn_reference_hasher::hash (const vn_reference_s *vr1)
240 return vr1->hashcode;
243 inline bool
244 vn_reference_hasher::equal (const vn_reference_s *v, const vn_reference_s *c)
246 return v == c || vn_reference_eq (v, c);
249 typedef hash_table<vn_reference_hasher> vn_reference_table_type;
250 typedef vn_reference_table_type::iterator vn_reference_iterator_type;
253 /* The set of VN hashtables. */
255 typedef struct vn_tables_s
257 vn_nary_op_table_type *nary;
258 vn_phi_table_type *phis;
259 vn_reference_table_type *references;
260 } *vn_tables_t;
263 /* vn_constant hashtable helpers. */
265 struct vn_constant_hasher : free_ptr_hash <vn_constant_s>
267 static inline hashval_t hash (const vn_constant_s *);
268 static inline bool equal (const vn_constant_s *, const vn_constant_s *);
271 /* Hash table hash function for vn_constant_t. */
273 inline hashval_t
274 vn_constant_hasher::hash (const vn_constant_s *vc1)
276 return vc1->hashcode;
279 /* Hash table equality function for vn_constant_t. */
281 inline bool
282 vn_constant_hasher::equal (const vn_constant_s *vc1, const vn_constant_s *vc2)
284 if (vc1->hashcode != vc2->hashcode)
285 return false;
287 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
290 static hash_table<vn_constant_hasher> *constant_to_value_id;
291 static bitmap constant_value_ids;
294 /* Obstack we allocate the vn-tables elements from. */
295 static obstack vn_tables_obstack;
296 /* Special obstack we never unwind. */
297 static obstack vn_tables_insert_obstack;
299 static vn_reference_t last_inserted_ref;
300 static vn_phi_t last_inserted_phi;
301 static vn_nary_op_t last_inserted_nary;
303 /* Valid hashtables storing information we have proven to be
304 correct. */
305 static vn_tables_t valid_info;
308 /* Valueization hook. Valueize NAME if it is an SSA name, otherwise
309 just return it. */
310 tree (*vn_valueize) (tree);
313 /* This represents the top of the VN lattice, which is the universal
314 value. */
316 tree VN_TOP;
318 /* Unique counter for our value ids. */
320 static unsigned int next_value_id;
323 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
324 are allocated on an obstack for locality reasons, and to free them
325 without looping over the vec. */
327 struct vn_ssa_aux_hasher : typed_noop_remove <vn_ssa_aux_t>
329 typedef vn_ssa_aux_t value_type;
330 typedef tree compare_type;
331 static inline hashval_t hash (const value_type &);
332 static inline bool equal (const value_type &, const compare_type &);
333 static inline void mark_deleted (value_type &) {}
334 static inline void mark_empty (value_type &e) { e = NULL; }
335 static inline bool is_deleted (value_type &) { return false; }
336 static inline bool is_empty (value_type &e) { return e == NULL; }
339 hashval_t
340 vn_ssa_aux_hasher::hash (const value_type &entry)
342 return SSA_NAME_VERSION (entry->name);
345 bool
346 vn_ssa_aux_hasher::equal (const value_type &entry, const compare_type &name)
348 return name == entry->name;
351 static hash_table<vn_ssa_aux_hasher> *vn_ssa_aux_hash;
352 typedef hash_table<vn_ssa_aux_hasher>::iterator vn_ssa_aux_iterator_type;
353 static struct obstack vn_ssa_aux_obstack;
355 static vn_nary_op_t vn_nary_op_insert_stmt (gimple *, tree);
356 static unsigned int vn_nary_length_from_stmt (gimple *);
357 static vn_nary_op_t alloc_vn_nary_op_noinit (unsigned int, obstack *);
358 static vn_nary_op_t vn_nary_op_insert_into (vn_nary_op_t,
359 vn_nary_op_table_type *, bool);
360 static void init_vn_nary_op_from_stmt (vn_nary_op_t, gimple *);
361 static void init_vn_nary_op_from_pieces (vn_nary_op_t, unsigned int,
362 enum tree_code, tree, tree *);
363 static tree vn_lookup_simplify_result (gimple_match_op *);
365 /* Return whether there is value numbering information for a given SSA name. */
367 bool
368 has_VN_INFO (tree name)
370 return vn_ssa_aux_hash->find_with_hash (name, SSA_NAME_VERSION (name));
373 vn_ssa_aux_t
374 VN_INFO (tree name)
376 vn_ssa_aux_t *res
377 = vn_ssa_aux_hash->find_slot_with_hash (name, SSA_NAME_VERSION (name),
378 INSERT);
379 if (*res != NULL)
380 return *res;
382 vn_ssa_aux_t newinfo = *res = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
383 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
384 newinfo->name = name;
385 newinfo->valnum = VN_TOP;
386 /* We are using the visited flag to handle uses with defs not within the
387 region being value-numbered. */
388 newinfo->visited = false;
390 /* Given we create the VN_INFOs on-demand now we have to do initialization
391 different than VN_TOP here. */
392 if (SSA_NAME_IS_DEFAULT_DEF (name))
393 switch (TREE_CODE (SSA_NAME_VAR (name)))
395 case VAR_DECL:
396 /* All undefined vars are VARYING. */
397 newinfo->valnum = name;
398 newinfo->visited = true;
399 break;
401 case PARM_DECL:
402 /* Parameters are VARYING but we can record a condition
403 if we know it is a non-NULL pointer. */
404 newinfo->visited = true;
405 newinfo->valnum = name;
406 if (POINTER_TYPE_P (TREE_TYPE (name))
407 && nonnull_arg_p (SSA_NAME_VAR (name)))
409 tree ops[2];
410 ops[0] = name;
411 ops[1] = build_int_cst (TREE_TYPE (name), 0);
412 vn_nary_op_t nary;
413 /* Allocate from non-unwinding stack. */
414 nary = alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack);
415 init_vn_nary_op_from_pieces (nary, 2, NE_EXPR,
416 boolean_type_node, ops);
417 nary->predicated_values = 0;
418 nary->u.result = boolean_true_node;
419 vn_nary_op_insert_into (nary, valid_info->nary, true);
420 gcc_assert (nary->unwind_to == NULL);
421 /* Also do not link it into the undo chain. */
422 last_inserted_nary = nary->next;
423 nary->next = (vn_nary_op_t)(void *)-1;
424 nary = alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack);
425 init_vn_nary_op_from_pieces (nary, 2, EQ_EXPR,
426 boolean_type_node, ops);
427 nary->predicated_values = 0;
428 nary->u.result = boolean_false_node;
429 vn_nary_op_insert_into (nary, valid_info->nary, true);
430 gcc_assert (nary->unwind_to == NULL);
431 last_inserted_nary = nary->next;
432 nary->next = (vn_nary_op_t)(void *)-1;
433 if (dump_file && (dump_flags & TDF_DETAILS))
435 fprintf (dump_file, "Recording ");
436 print_generic_expr (dump_file, name, TDF_SLIM);
437 fprintf (dump_file, " != 0\n");
440 break;
442 case RESULT_DECL:
443 /* If the result is passed by invisible reference the default
444 def is initialized, otherwise it's uninitialized. Still
445 undefined is varying. */
446 newinfo->visited = true;
447 newinfo->valnum = name;
448 break;
450 default:
451 gcc_unreachable ();
453 return newinfo;
456 /* Return the SSA value of X. */
458 inline tree
459 SSA_VAL (tree x, bool *visited = NULL)
461 vn_ssa_aux_t tem = vn_ssa_aux_hash->find_with_hash (x, SSA_NAME_VERSION (x));
462 if (visited)
463 *visited = tem && tem->visited;
464 return tem && tem->visited ? tem->valnum : x;
467 /* Return the SSA value of the VUSE x, supporting released VDEFs
468 during elimination which will value-number the VDEF to the
469 associated VUSE (but not substitute in the whole lattice). */
471 static inline tree
472 vuse_ssa_val (tree x)
474 if (!x)
475 return NULL_TREE;
479 x = SSA_VAL (x);
480 gcc_assert (x != VN_TOP);
482 while (SSA_NAME_IN_FREE_LIST (x));
484 return x;
487 /* Similar to the above but used as callback for walk_non_aliases_vuses
488 and thus should stop at unvisited VUSE to not walk across region
489 boundaries. */
491 static tree
492 vuse_valueize (tree vuse)
496 bool visited;
497 vuse = SSA_VAL (vuse, &visited);
498 if (!visited)
499 return NULL_TREE;
500 gcc_assert (vuse != VN_TOP);
502 while (SSA_NAME_IN_FREE_LIST (vuse));
503 return vuse;
507 /* Return the vn_kind the expression computed by the stmt should be
508 associated with. */
510 enum vn_kind
511 vn_get_stmt_kind (gimple *stmt)
513 switch (gimple_code (stmt))
515 case GIMPLE_CALL:
516 return VN_REFERENCE;
517 case GIMPLE_PHI:
518 return VN_PHI;
519 case GIMPLE_ASSIGN:
521 enum tree_code code = gimple_assign_rhs_code (stmt);
522 tree rhs1 = gimple_assign_rhs1 (stmt);
523 switch (get_gimple_rhs_class (code))
525 case GIMPLE_UNARY_RHS:
526 case GIMPLE_BINARY_RHS:
527 case GIMPLE_TERNARY_RHS:
528 return VN_NARY;
529 case GIMPLE_SINGLE_RHS:
530 switch (TREE_CODE_CLASS (code))
532 case tcc_reference:
533 /* VOP-less references can go through unary case. */
534 if ((code == REALPART_EXPR
535 || code == IMAGPART_EXPR
536 || code == VIEW_CONVERT_EXPR
537 || code == BIT_FIELD_REF)
538 && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
539 return VN_NARY;
541 /* Fallthrough. */
542 case tcc_declaration:
543 return VN_REFERENCE;
545 case tcc_constant:
546 return VN_CONSTANT;
548 default:
549 if (code == ADDR_EXPR)
550 return (is_gimple_min_invariant (rhs1)
551 ? VN_CONSTANT : VN_REFERENCE);
552 else if (code == CONSTRUCTOR)
553 return VN_NARY;
554 return VN_NONE;
556 default:
557 return VN_NONE;
560 default:
561 return VN_NONE;
565 /* Lookup a value id for CONSTANT and return it. If it does not
566 exist returns 0. */
568 unsigned int
569 get_constant_value_id (tree constant)
571 vn_constant_s **slot;
572 struct vn_constant_s vc;
574 vc.hashcode = vn_hash_constant_with_type (constant);
575 vc.constant = constant;
576 slot = constant_to_value_id->find_slot (&vc, NO_INSERT);
577 if (slot)
578 return (*slot)->value_id;
579 return 0;
582 /* Lookup a value id for CONSTANT, and if it does not exist, create a
583 new one and return it. If it does exist, return it. */
585 unsigned int
586 get_or_alloc_constant_value_id (tree constant)
588 vn_constant_s **slot;
589 struct vn_constant_s vc;
590 vn_constant_t vcp;
592 /* If the hashtable isn't initialized we're not running from PRE and thus
593 do not need value-ids. */
594 if (!constant_to_value_id)
595 return 0;
597 vc.hashcode = vn_hash_constant_with_type (constant);
598 vc.constant = constant;
599 slot = constant_to_value_id->find_slot (&vc, INSERT);
600 if (*slot)
601 return (*slot)->value_id;
603 vcp = XNEW (struct vn_constant_s);
604 vcp->hashcode = vc.hashcode;
605 vcp->constant = constant;
606 vcp->value_id = get_next_value_id ();
607 *slot = vcp;
608 bitmap_set_bit (constant_value_ids, vcp->value_id);
609 return vcp->value_id;
612 /* Return true if V is a value id for a constant. */
614 bool
615 value_id_constant_p (unsigned int v)
617 return bitmap_bit_p (constant_value_ids, v);
620 /* Compute the hash for a reference operand VRO1. */
622 static void
623 vn_reference_op_compute_hash (const vn_reference_op_t vro1, inchash::hash &hstate)
625 hstate.add_int (vro1->opcode);
626 if (vro1->op0)
627 inchash::add_expr (vro1->op0, hstate);
628 if (vro1->op1)
629 inchash::add_expr (vro1->op1, hstate);
630 if (vro1->op2)
631 inchash::add_expr (vro1->op2, hstate);
634 /* Compute a hash for the reference operation VR1 and return it. */
636 static hashval_t
637 vn_reference_compute_hash (const vn_reference_t vr1)
639 inchash::hash hstate;
640 hashval_t result;
641 int i;
642 vn_reference_op_t vro;
643 poly_int64 off = -1;
644 bool deref = false;
646 FOR_EACH_VEC_ELT (vr1->operands, i, vro)
648 if (vro->opcode == MEM_REF)
649 deref = true;
650 else if (vro->opcode != ADDR_EXPR)
651 deref = false;
652 if (maybe_ne (vro->off, -1))
654 if (known_eq (off, -1))
655 off = 0;
656 off += vro->off;
658 else
660 if (maybe_ne (off, -1)
661 && maybe_ne (off, 0))
662 hstate.add_poly_int (off);
663 off = -1;
664 if (deref
665 && vro->opcode == ADDR_EXPR)
667 if (vro->op0)
669 tree op = TREE_OPERAND (vro->op0, 0);
670 hstate.add_int (TREE_CODE (op));
671 inchash::add_expr (op, hstate);
674 else
675 vn_reference_op_compute_hash (vro, hstate);
678 result = hstate.end ();
679 /* ??? We would ICE later if we hash instead of adding that in. */
680 if (vr1->vuse)
681 result += SSA_NAME_VERSION (vr1->vuse);
683 return result;
686 /* Return true if reference operations VR1 and VR2 are equivalent. This
687 means they have the same set of operands and vuses. */
689 bool
690 vn_reference_eq (const_vn_reference_t const vr1, const_vn_reference_t const vr2)
692 unsigned i, j;
694 /* Early out if this is not a hash collision. */
695 if (vr1->hashcode != vr2->hashcode)
696 return false;
698 /* The VOP needs to be the same. */
699 if (vr1->vuse != vr2->vuse)
700 return false;
702 /* If the operands are the same we are done. */
703 if (vr1->operands == vr2->operands)
704 return true;
706 if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
707 return false;
709 if (INTEGRAL_TYPE_P (vr1->type)
710 && INTEGRAL_TYPE_P (vr2->type))
712 if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
713 return false;
715 else if (INTEGRAL_TYPE_P (vr1->type)
716 && (TYPE_PRECISION (vr1->type)
717 != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
718 return false;
719 else if (INTEGRAL_TYPE_P (vr2->type)
720 && (TYPE_PRECISION (vr2->type)
721 != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
722 return false;
724 i = 0;
725 j = 0;
728 poly_int64 off1 = 0, off2 = 0;
729 vn_reference_op_t vro1, vro2;
730 vn_reference_op_s tem1, tem2;
731 bool deref1 = false, deref2 = false;
732 for (; vr1->operands.iterate (i, &vro1); i++)
734 if (vro1->opcode == MEM_REF)
735 deref1 = true;
736 /* Do not look through a storage order barrier. */
737 else if (vro1->opcode == VIEW_CONVERT_EXPR && vro1->reverse)
738 return false;
739 if (known_eq (vro1->off, -1))
740 break;
741 off1 += vro1->off;
743 for (; vr2->operands.iterate (j, &vro2); j++)
745 if (vro2->opcode == MEM_REF)
746 deref2 = true;
747 /* Do not look through a storage order barrier. */
748 else if (vro2->opcode == VIEW_CONVERT_EXPR && vro2->reverse)
749 return false;
750 if (known_eq (vro2->off, -1))
751 break;
752 off2 += vro2->off;
754 if (maybe_ne (off1, off2))
755 return false;
756 if (deref1 && vro1->opcode == ADDR_EXPR)
758 memset (&tem1, 0, sizeof (tem1));
759 tem1.op0 = TREE_OPERAND (vro1->op0, 0);
760 tem1.type = TREE_TYPE (tem1.op0);
761 tem1.opcode = TREE_CODE (tem1.op0);
762 vro1 = &tem1;
763 deref1 = false;
765 if (deref2 && vro2->opcode == ADDR_EXPR)
767 memset (&tem2, 0, sizeof (tem2));
768 tem2.op0 = TREE_OPERAND (vro2->op0, 0);
769 tem2.type = TREE_TYPE (tem2.op0);
770 tem2.opcode = TREE_CODE (tem2.op0);
771 vro2 = &tem2;
772 deref2 = false;
774 if (deref1 != deref2)
775 return false;
776 if (!vn_reference_op_eq (vro1, vro2))
777 return false;
778 ++j;
779 ++i;
781 while (vr1->operands.length () != i
782 || vr2->operands.length () != j);
784 return true;
787 /* Copy the operations present in load/store REF into RESULT, a vector of
788 vn_reference_op_s's. */
790 static void
791 copy_reference_ops_from_ref (tree ref, vec<vn_reference_op_s> *result)
793 if (TREE_CODE (ref) == TARGET_MEM_REF)
795 vn_reference_op_s temp;
797 result->reserve (3);
799 memset (&temp, 0, sizeof (temp));
800 temp.type = TREE_TYPE (ref);
801 temp.opcode = TREE_CODE (ref);
802 temp.op0 = TMR_INDEX (ref);
803 temp.op1 = TMR_STEP (ref);
804 temp.op2 = TMR_OFFSET (ref);
805 temp.off = -1;
806 temp.clique = MR_DEPENDENCE_CLIQUE (ref);
807 temp.base = MR_DEPENDENCE_BASE (ref);
808 result->quick_push (temp);
810 memset (&temp, 0, sizeof (temp));
811 temp.type = NULL_TREE;
812 temp.opcode = ERROR_MARK;
813 temp.op0 = TMR_INDEX2 (ref);
814 temp.off = -1;
815 result->quick_push (temp);
817 memset (&temp, 0, sizeof (temp));
818 temp.type = NULL_TREE;
819 temp.opcode = TREE_CODE (TMR_BASE (ref));
820 temp.op0 = TMR_BASE (ref);
821 temp.off = -1;
822 result->quick_push (temp);
823 return;
826 /* For non-calls, store the information that makes up the address. */
827 tree orig = ref;
828 while (ref)
830 vn_reference_op_s temp;
832 memset (&temp, 0, sizeof (temp));
833 temp.type = TREE_TYPE (ref);
834 temp.opcode = TREE_CODE (ref);
835 temp.off = -1;
837 switch (temp.opcode)
839 case MODIFY_EXPR:
840 temp.op0 = TREE_OPERAND (ref, 1);
841 break;
842 case WITH_SIZE_EXPR:
843 temp.op0 = TREE_OPERAND (ref, 1);
844 temp.off = 0;
845 break;
846 case MEM_REF:
847 /* The base address gets its own vn_reference_op_s structure. */
848 temp.op0 = TREE_OPERAND (ref, 1);
849 if (!mem_ref_offset (ref).to_shwi (&temp.off))
850 temp.off = -1;
851 temp.clique = MR_DEPENDENCE_CLIQUE (ref);
852 temp.base = MR_DEPENDENCE_BASE (ref);
853 temp.reverse = REF_REVERSE_STORAGE_ORDER (ref);
854 break;
855 case BIT_FIELD_REF:
856 /* Record bits, position and storage order. */
857 temp.op0 = TREE_OPERAND (ref, 1);
858 temp.op1 = TREE_OPERAND (ref, 2);
859 if (!multiple_p (bit_field_offset (ref), BITS_PER_UNIT, &temp.off))
860 temp.off = -1;
861 temp.reverse = REF_REVERSE_STORAGE_ORDER (ref);
862 break;
863 case COMPONENT_REF:
864 /* The field decl is enough to unambiguously specify the field,
865 a matching type is not necessary and a mismatching type
866 is always a spurious difference. */
867 temp.type = NULL_TREE;
868 temp.op0 = TREE_OPERAND (ref, 1);
869 temp.op1 = TREE_OPERAND (ref, 2);
871 tree this_offset = component_ref_field_offset (ref);
872 if (this_offset
873 && poly_int_tree_p (this_offset))
875 tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
876 if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0)
878 poly_offset_int off
879 = (wi::to_poly_offset (this_offset)
880 + (wi::to_offset (bit_offset) >> LOG2_BITS_PER_UNIT));
881 /* Probibit value-numbering zero offset components
882 of addresses the same before the pass folding
883 __builtin_object_size had a chance to run
884 (checking cfun->after_inlining does the
885 trick here). */
886 if (TREE_CODE (orig) != ADDR_EXPR
887 || maybe_ne (off, 0)
888 || cfun->after_inlining)
889 off.to_shwi (&temp.off);
893 break;
894 case ARRAY_RANGE_REF:
895 case ARRAY_REF:
897 tree eltype = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref, 0)));
898 /* Record index as operand. */
899 temp.op0 = TREE_OPERAND (ref, 1);
900 /* Always record lower bounds and element size. */
901 temp.op1 = array_ref_low_bound (ref);
902 /* But record element size in units of the type alignment. */
903 temp.op2 = TREE_OPERAND (ref, 3);
904 temp.align = eltype->type_common.align;
905 if (! temp.op2)
906 temp.op2 = size_binop (EXACT_DIV_EXPR, TYPE_SIZE_UNIT (eltype),
907 size_int (TYPE_ALIGN_UNIT (eltype)));
908 if (poly_int_tree_p (temp.op0)
909 && poly_int_tree_p (temp.op1)
910 && TREE_CODE (temp.op2) == INTEGER_CST)
912 poly_offset_int off = ((wi::to_poly_offset (temp.op0)
913 - wi::to_poly_offset (temp.op1))
914 * wi::to_offset (temp.op2)
915 * vn_ref_op_align_unit (&temp));
916 off.to_shwi (&temp.off);
919 break;
920 case VAR_DECL:
921 if (DECL_HARD_REGISTER (ref))
923 temp.op0 = ref;
924 break;
926 /* Fallthru. */
927 case PARM_DECL:
928 case CONST_DECL:
929 case RESULT_DECL:
930 /* Canonicalize decls to MEM[&decl] which is what we end up with
931 when valueizing MEM[ptr] with ptr = &decl. */
932 temp.opcode = MEM_REF;
933 temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0);
934 temp.off = 0;
935 result->safe_push (temp);
936 temp.opcode = ADDR_EXPR;
937 temp.op0 = build1 (ADDR_EXPR, TREE_TYPE (temp.op0), ref);
938 temp.type = TREE_TYPE (temp.op0);
939 temp.off = -1;
940 break;
941 case STRING_CST:
942 case INTEGER_CST:
943 case COMPLEX_CST:
944 case VECTOR_CST:
945 case REAL_CST:
946 case FIXED_CST:
947 case CONSTRUCTOR:
948 case SSA_NAME:
949 temp.op0 = ref;
950 break;
951 case ADDR_EXPR:
952 if (is_gimple_min_invariant (ref))
954 temp.op0 = ref;
955 break;
957 break;
958 /* These are only interesting for their operands, their
959 existence, and their type. They will never be the last
960 ref in the chain of references (IE they require an
961 operand), so we don't have to put anything
962 for op* as it will be handled by the iteration */
963 case REALPART_EXPR:
964 temp.off = 0;
965 break;
966 case VIEW_CONVERT_EXPR:
967 temp.off = 0;
968 temp.reverse = storage_order_barrier_p (ref);
969 break;
970 case IMAGPART_EXPR:
971 /* This is only interesting for its constant offset. */
972 temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
973 break;
974 default:
975 gcc_unreachable ();
977 result->safe_push (temp);
979 if (REFERENCE_CLASS_P (ref)
980 || TREE_CODE (ref) == MODIFY_EXPR
981 || TREE_CODE (ref) == WITH_SIZE_EXPR
982 || (TREE_CODE (ref) == ADDR_EXPR
983 && !is_gimple_min_invariant (ref)))
984 ref = TREE_OPERAND (ref, 0);
985 else
986 ref = NULL_TREE;
990 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
991 operands in *OPS, the reference alias set SET and the reference type TYPE.
992 Return true if something useful was produced. */
994 bool
995 ao_ref_init_from_vn_reference (ao_ref *ref,
996 alias_set_type set, tree type,
997 vec<vn_reference_op_s> ops)
999 vn_reference_op_t op;
1000 unsigned i;
1001 tree base = NULL_TREE;
1002 tree *op0_p = &base;
1003 poly_offset_int offset = 0;
1004 poly_offset_int max_size;
1005 poly_offset_int size = -1;
1006 tree size_tree = NULL_TREE;
1007 alias_set_type base_alias_set = -1;
1009 /* First get the final access size from just the outermost expression. */
1010 op = &ops[0];
1011 if (op->opcode == COMPONENT_REF)
1012 size_tree = DECL_SIZE (op->op0);
1013 else if (op->opcode == BIT_FIELD_REF)
1014 size_tree = op->op0;
1015 else
1017 machine_mode mode = TYPE_MODE (type);
1018 if (mode == BLKmode)
1019 size_tree = TYPE_SIZE (type);
1020 else
1021 size = GET_MODE_BITSIZE (mode);
1023 if (size_tree != NULL_TREE
1024 && poly_int_tree_p (size_tree))
1025 size = wi::to_poly_offset (size_tree);
1027 /* Initially, maxsize is the same as the accessed element size.
1028 In the following it will only grow (or become -1). */
1029 max_size = size;
1031 /* Compute cumulative bit-offset for nested component-refs and array-refs,
1032 and find the ultimate containing object. */
1033 FOR_EACH_VEC_ELT (ops, i, op)
1035 switch (op->opcode)
1037 /* These may be in the reference ops, but we cannot do anything
1038 sensible with them here. */
1039 case ADDR_EXPR:
1040 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1041 if (base != NULL_TREE
1042 && TREE_CODE (base) == MEM_REF
1043 && op->op0
1044 && DECL_P (TREE_OPERAND (op->op0, 0)))
1046 vn_reference_op_t pop = &ops[i-1];
1047 base = TREE_OPERAND (op->op0, 0);
1048 if (known_eq (pop->off, -1))
1050 max_size = -1;
1051 offset = 0;
1053 else
1054 offset += pop->off * BITS_PER_UNIT;
1055 op0_p = NULL;
1056 break;
1058 /* Fallthru. */
1059 case CALL_EXPR:
1060 return false;
1062 /* Record the base objects. */
1063 case MEM_REF:
1064 base_alias_set = get_deref_alias_set (op->op0);
1065 *op0_p = build2 (MEM_REF, op->type,
1066 NULL_TREE, op->op0);
1067 MR_DEPENDENCE_CLIQUE (*op0_p) = op->clique;
1068 MR_DEPENDENCE_BASE (*op0_p) = op->base;
1069 op0_p = &TREE_OPERAND (*op0_p, 0);
1070 break;
1072 case VAR_DECL:
1073 case PARM_DECL:
1074 case RESULT_DECL:
1075 case SSA_NAME:
1076 *op0_p = op->op0;
1077 op0_p = NULL;
1078 break;
1080 /* And now the usual component-reference style ops. */
1081 case BIT_FIELD_REF:
1082 offset += wi::to_poly_offset (op->op1);
1083 break;
1085 case COMPONENT_REF:
1087 tree field = op->op0;
1088 /* We do not have a complete COMPONENT_REF tree here so we
1089 cannot use component_ref_field_offset. Do the interesting
1090 parts manually. */
1091 tree this_offset = DECL_FIELD_OFFSET (field);
1093 if (op->op1 || !poly_int_tree_p (this_offset))
1094 max_size = -1;
1095 else
1097 poly_offset_int woffset = (wi::to_poly_offset (this_offset)
1098 << LOG2_BITS_PER_UNIT);
1099 woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
1100 offset += woffset;
1102 break;
1105 case ARRAY_RANGE_REF:
1106 case ARRAY_REF:
1107 /* We recorded the lower bound and the element size. */
1108 if (!poly_int_tree_p (op->op0)
1109 || !poly_int_tree_p (op->op1)
1110 || TREE_CODE (op->op2) != INTEGER_CST)
1111 max_size = -1;
1112 else
1114 poly_offset_int woffset
1115 = wi::sext (wi::to_poly_offset (op->op0)
1116 - wi::to_poly_offset (op->op1),
1117 TYPE_PRECISION (TREE_TYPE (op->op0)));
1118 woffset *= wi::to_offset (op->op2) * vn_ref_op_align_unit (op);
1119 woffset <<= LOG2_BITS_PER_UNIT;
1120 offset += woffset;
1122 break;
1124 case REALPART_EXPR:
1125 break;
1127 case IMAGPART_EXPR:
1128 offset += size;
1129 break;
1131 case VIEW_CONVERT_EXPR:
1132 break;
1134 case STRING_CST:
1135 case INTEGER_CST:
1136 case COMPLEX_CST:
1137 case VECTOR_CST:
1138 case REAL_CST:
1139 case CONSTRUCTOR:
1140 case CONST_DECL:
1141 return false;
1143 default:
1144 return false;
1148 if (base == NULL_TREE)
1149 return false;
1151 ref->ref = NULL_TREE;
1152 ref->base = base;
1153 ref->ref_alias_set = set;
1154 if (base_alias_set != -1)
1155 ref->base_alias_set = base_alias_set;
1156 else
1157 ref->base_alias_set = get_alias_set (base);
1158 /* We discount volatiles from value-numbering elsewhere. */
1159 ref->volatile_p = false;
1161 if (!size.to_shwi (&ref->size) || maybe_lt (ref->size, 0))
1163 ref->offset = 0;
1164 ref->size = -1;
1165 ref->max_size = -1;
1166 return true;
1169 if (!offset.to_shwi (&ref->offset))
1171 ref->offset = 0;
1172 ref->max_size = -1;
1173 return true;
1176 if (!max_size.to_shwi (&ref->max_size) || maybe_lt (ref->max_size, 0))
1177 ref->max_size = -1;
1179 return true;
1182 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1183 vn_reference_op_s's. */
1185 static void
1186 copy_reference_ops_from_call (gcall *call,
1187 vec<vn_reference_op_s> *result)
1189 vn_reference_op_s temp;
1190 unsigned i;
1191 tree lhs = gimple_call_lhs (call);
1192 int lr;
1194 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1195 different. By adding the lhs here in the vector, we ensure that the
1196 hashcode is different, guaranteeing a different value number. */
1197 if (lhs && TREE_CODE (lhs) != SSA_NAME)
1199 memset (&temp, 0, sizeof (temp));
1200 temp.opcode = MODIFY_EXPR;
1201 temp.type = TREE_TYPE (lhs);
1202 temp.op0 = lhs;
1203 temp.off = -1;
1204 result->safe_push (temp);
1207 /* Copy the type, opcode, function, static chain and EH region, if any. */
1208 memset (&temp, 0, sizeof (temp));
1209 temp.type = gimple_call_fntype (call);
1210 temp.opcode = CALL_EXPR;
1211 temp.op0 = gimple_call_fn (call);
1212 temp.op1 = gimple_call_chain (call);
1213 if (stmt_could_throw_p (cfun, call) && (lr = lookup_stmt_eh_lp (call)) > 0)
1214 temp.op2 = size_int (lr);
1215 temp.off = -1;
1216 result->safe_push (temp);
1218 /* Copy the call arguments. As they can be references as well,
1219 just chain them together. */
1220 for (i = 0; i < gimple_call_num_args (call); ++i)
1222 tree callarg = gimple_call_arg (call, i);
1223 copy_reference_ops_from_ref (callarg, result);
1227 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1228 *I_P to point to the last element of the replacement. */
1229 static bool
1230 vn_reference_fold_indirect (vec<vn_reference_op_s> *ops,
1231 unsigned int *i_p)
1233 unsigned int i = *i_p;
1234 vn_reference_op_t op = &(*ops)[i];
1235 vn_reference_op_t mem_op = &(*ops)[i - 1];
1236 tree addr_base;
1237 poly_int64 addr_offset = 0;
1239 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1240 from .foo.bar to the preceding MEM_REF offset and replace the
1241 address with &OBJ. */
1242 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
1243 &addr_offset);
1244 gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
1245 if (addr_base != TREE_OPERAND (op->op0, 0))
1247 poly_offset_int off
1248 = (poly_offset_int::from (wi::to_poly_wide (mem_op->op0),
1249 SIGNED)
1250 + addr_offset);
1251 mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off);
1252 op->op0 = build_fold_addr_expr (addr_base);
1253 if (tree_fits_shwi_p (mem_op->op0))
1254 mem_op->off = tree_to_shwi (mem_op->op0);
1255 else
1256 mem_op->off = -1;
1257 return true;
1259 return false;
1262 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1263 *I_P to point to the last element of the replacement. */
1264 static bool
1265 vn_reference_maybe_forwprop_address (vec<vn_reference_op_s> *ops,
1266 unsigned int *i_p)
1268 unsigned int i = *i_p;
1269 vn_reference_op_t op = &(*ops)[i];
1270 vn_reference_op_t mem_op = &(*ops)[i - 1];
1271 gimple *def_stmt;
1272 enum tree_code code;
1273 poly_offset_int off;
1275 def_stmt = SSA_NAME_DEF_STMT (op->op0);
1276 if (!is_gimple_assign (def_stmt))
1277 return false;
1279 code = gimple_assign_rhs_code (def_stmt);
1280 if (code != ADDR_EXPR
1281 && code != POINTER_PLUS_EXPR)
1282 return false;
1284 off = poly_offset_int::from (wi::to_poly_wide (mem_op->op0), SIGNED);
1286 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1287 from .foo.bar to the preceding MEM_REF offset and replace the
1288 address with &OBJ. */
1289 if (code == ADDR_EXPR)
1291 tree addr, addr_base;
1292 poly_int64 addr_offset;
1294 addr = gimple_assign_rhs1 (def_stmt);
1295 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1296 &addr_offset);
1297 /* If that didn't work because the address isn't invariant propagate
1298 the reference tree from the address operation in case the current
1299 dereference isn't offsetted. */
1300 if (!addr_base
1301 && *i_p == ops->length () - 1
1302 && known_eq (off, 0)
1303 /* This makes us disable this transform for PRE where the
1304 reference ops might be also used for code insertion which
1305 is invalid. */
1306 && default_vn_walk_kind == VN_WALKREWRITE)
1308 auto_vec<vn_reference_op_s, 32> tem;
1309 copy_reference_ops_from_ref (TREE_OPERAND (addr, 0), &tem);
1310 /* Make sure to preserve TBAA info. The only objects not
1311 wrapped in MEM_REFs that can have their address taken are
1312 STRING_CSTs. */
1313 if (tem.length () >= 2
1314 && tem[tem.length () - 2].opcode == MEM_REF)
1316 vn_reference_op_t new_mem_op = &tem[tem.length () - 2];
1317 new_mem_op->op0
1318 = wide_int_to_tree (TREE_TYPE (mem_op->op0),
1319 wi::to_poly_wide (new_mem_op->op0));
1321 else
1322 gcc_assert (tem.last ().opcode == STRING_CST);
1323 ops->pop ();
1324 ops->pop ();
1325 ops->safe_splice (tem);
1326 --*i_p;
1327 return true;
1329 if (!addr_base
1330 || TREE_CODE (addr_base) != MEM_REF
1331 || (TREE_CODE (TREE_OPERAND (addr_base, 0)) == SSA_NAME
1332 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (addr_base, 0))))
1333 return false;
1335 off += addr_offset;
1336 off += mem_ref_offset (addr_base);
1337 op->op0 = TREE_OPERAND (addr_base, 0);
1339 else
1341 tree ptr, ptroff;
1342 ptr = gimple_assign_rhs1 (def_stmt);
1343 ptroff = gimple_assign_rhs2 (def_stmt);
1344 if (TREE_CODE (ptr) != SSA_NAME
1345 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr)
1346 /* Make sure to not endlessly recurse.
1347 See gcc.dg/tree-ssa/20040408-1.c for an example. Can easily
1348 happen when we value-number a PHI to its backedge value. */
1349 || SSA_VAL (ptr) == op->op0
1350 || !poly_int_tree_p (ptroff))
1351 return false;
1353 off += wi::to_poly_offset (ptroff);
1354 op->op0 = ptr;
1357 mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off);
1358 if (tree_fits_shwi_p (mem_op->op0))
1359 mem_op->off = tree_to_shwi (mem_op->op0);
1360 else
1361 mem_op->off = -1;
1362 /* ??? Can end up with endless recursion here!?
1363 gcc.c-torture/execute/strcmp-1.c */
1364 if (TREE_CODE (op->op0) == SSA_NAME)
1365 op->op0 = SSA_VAL (op->op0);
1366 if (TREE_CODE (op->op0) != SSA_NAME)
1367 op->opcode = TREE_CODE (op->op0);
1369 /* And recurse. */
1370 if (TREE_CODE (op->op0) == SSA_NAME)
1371 vn_reference_maybe_forwprop_address (ops, i_p);
1372 else if (TREE_CODE (op->op0) == ADDR_EXPR)
1373 vn_reference_fold_indirect (ops, i_p);
1374 return true;
1377 /* Optimize the reference REF to a constant if possible or return
1378 NULL_TREE if not. */
1380 tree
1381 fully_constant_vn_reference_p (vn_reference_t ref)
1383 vec<vn_reference_op_s> operands = ref->operands;
1384 vn_reference_op_t op;
1386 /* Try to simplify the translated expression if it is
1387 a call to a builtin function with at most two arguments. */
1388 op = &operands[0];
1389 if (op->opcode == CALL_EXPR
1390 && TREE_CODE (op->op0) == ADDR_EXPR
1391 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1392 && fndecl_built_in_p (TREE_OPERAND (op->op0, 0))
1393 && operands.length () >= 2
1394 && operands.length () <= 3)
1396 vn_reference_op_t arg0, arg1 = NULL;
1397 bool anyconst = false;
1398 arg0 = &operands[1];
1399 if (operands.length () > 2)
1400 arg1 = &operands[2];
1401 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1402 || (arg0->opcode == ADDR_EXPR
1403 && is_gimple_min_invariant (arg0->op0)))
1404 anyconst = true;
1405 if (arg1
1406 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1407 || (arg1->opcode == ADDR_EXPR
1408 && is_gimple_min_invariant (arg1->op0))))
1409 anyconst = true;
1410 if (anyconst)
1412 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1413 arg1 ? 2 : 1,
1414 arg0->op0,
1415 arg1 ? arg1->op0 : NULL);
1416 if (folded
1417 && TREE_CODE (folded) == NOP_EXPR)
1418 folded = TREE_OPERAND (folded, 0);
1419 if (folded
1420 && is_gimple_min_invariant (folded))
1421 return folded;
1425 /* Simplify reads from constants or constant initializers. */
1426 else if (BITS_PER_UNIT == 8
1427 && COMPLETE_TYPE_P (ref->type)
1428 && is_gimple_reg_type (ref->type))
1430 poly_int64 off = 0;
1431 HOST_WIDE_INT size;
1432 if (INTEGRAL_TYPE_P (ref->type))
1433 size = TYPE_PRECISION (ref->type);
1434 else if (tree_fits_shwi_p (TYPE_SIZE (ref->type)))
1435 size = tree_to_shwi (TYPE_SIZE (ref->type));
1436 else
1437 return NULL_TREE;
1438 if (size % BITS_PER_UNIT != 0
1439 || size > MAX_BITSIZE_MODE_ANY_MODE)
1440 return NULL_TREE;
1441 size /= BITS_PER_UNIT;
1442 unsigned i;
1443 for (i = 0; i < operands.length (); ++i)
1445 if (TREE_CODE_CLASS (operands[i].opcode) == tcc_constant)
1447 ++i;
1448 break;
1450 if (known_eq (operands[i].off, -1))
1451 return NULL_TREE;
1452 off += operands[i].off;
1453 if (operands[i].opcode == MEM_REF)
1455 ++i;
1456 break;
1459 vn_reference_op_t base = &operands[--i];
1460 tree ctor = error_mark_node;
1461 tree decl = NULL_TREE;
1462 if (TREE_CODE_CLASS (base->opcode) == tcc_constant)
1463 ctor = base->op0;
1464 else if (base->opcode == MEM_REF
1465 && base[1].opcode == ADDR_EXPR
1466 && (TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == VAR_DECL
1467 || TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == CONST_DECL
1468 || TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == STRING_CST))
1470 decl = TREE_OPERAND (base[1].op0, 0);
1471 if (TREE_CODE (decl) == STRING_CST)
1472 ctor = decl;
1473 else
1474 ctor = ctor_for_folding (decl);
1476 if (ctor == NULL_TREE)
1477 return build_zero_cst (ref->type);
1478 else if (ctor != error_mark_node)
1480 HOST_WIDE_INT const_off;
1481 if (decl)
1483 tree res = fold_ctor_reference (ref->type, ctor,
1484 off * BITS_PER_UNIT,
1485 size * BITS_PER_UNIT, decl);
1486 if (res)
1488 STRIP_USELESS_TYPE_CONVERSION (res);
1489 if (is_gimple_min_invariant (res))
1490 return res;
1493 else if (off.is_constant (&const_off))
1495 unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT];
1496 int len = native_encode_expr (ctor, buf, size, const_off);
1497 if (len > 0)
1498 return native_interpret_expr (ref->type, buf, len);
1503 return NULL_TREE;
1506 /* Return true if OPS contain a storage order barrier. */
1508 static bool
1509 contains_storage_order_barrier_p (vec<vn_reference_op_s> ops)
1511 vn_reference_op_t op;
1512 unsigned i;
1514 FOR_EACH_VEC_ELT (ops, i, op)
1515 if (op->opcode == VIEW_CONVERT_EXPR && op->reverse)
1516 return true;
1518 return false;
1521 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1522 structures into their value numbers. This is done in-place, and
1523 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1524 whether any operands were valueized. */
1526 static vec<vn_reference_op_s>
1527 valueize_refs_1 (vec<vn_reference_op_s> orig, bool *valueized_anything,
1528 bool with_avail = false)
1530 vn_reference_op_t vro;
1531 unsigned int i;
1533 *valueized_anything = false;
1535 FOR_EACH_VEC_ELT (orig, i, vro)
1537 if (vro->opcode == SSA_NAME
1538 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1540 tree tem = with_avail ? vn_valueize (vro->op0) : SSA_VAL (vro->op0);
1541 if (tem != vro->op0)
1543 *valueized_anything = true;
1544 vro->op0 = tem;
1546 /* If it transforms from an SSA_NAME to a constant, update
1547 the opcode. */
1548 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1549 vro->opcode = TREE_CODE (vro->op0);
1551 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1553 tree tem = with_avail ? vn_valueize (vro->op1) : SSA_VAL (vro->op1);
1554 if (tem != vro->op1)
1556 *valueized_anything = true;
1557 vro->op1 = tem;
1560 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1562 tree tem = with_avail ? vn_valueize (vro->op2) : SSA_VAL (vro->op2);
1563 if (tem != vro->op2)
1565 *valueized_anything = true;
1566 vro->op2 = tem;
1569 /* If it transforms from an SSA_NAME to an address, fold with
1570 a preceding indirect reference. */
1571 if (i > 0
1572 && vro->op0
1573 && TREE_CODE (vro->op0) == ADDR_EXPR
1574 && orig[i - 1].opcode == MEM_REF)
1576 if (vn_reference_fold_indirect (&orig, &i))
1577 *valueized_anything = true;
1579 else if (i > 0
1580 && vro->opcode == SSA_NAME
1581 && orig[i - 1].opcode == MEM_REF)
1583 if (vn_reference_maybe_forwprop_address (&orig, &i))
1584 *valueized_anything = true;
1586 /* If it transforms a non-constant ARRAY_REF into a constant
1587 one, adjust the constant offset. */
1588 else if (vro->opcode == ARRAY_REF
1589 && known_eq (vro->off, -1)
1590 && poly_int_tree_p (vro->op0)
1591 && poly_int_tree_p (vro->op1)
1592 && TREE_CODE (vro->op2) == INTEGER_CST)
1594 poly_offset_int off = ((wi::to_poly_offset (vro->op0)
1595 - wi::to_poly_offset (vro->op1))
1596 * wi::to_offset (vro->op2)
1597 * vn_ref_op_align_unit (vro));
1598 off.to_shwi (&vro->off);
1602 return orig;
1605 static vec<vn_reference_op_s>
1606 valueize_refs (vec<vn_reference_op_s> orig)
1608 bool tem;
1609 return valueize_refs_1 (orig, &tem);
1612 static vec<vn_reference_op_s> shared_lookup_references;
1614 /* Create a vector of vn_reference_op_s structures from REF, a
1615 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1616 this function. *VALUEIZED_ANYTHING will specify whether any
1617 operands were valueized. */
1619 static vec<vn_reference_op_s>
1620 valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything)
1622 if (!ref)
1623 return vNULL;
1624 shared_lookup_references.truncate (0);
1625 copy_reference_ops_from_ref (ref, &shared_lookup_references);
1626 shared_lookup_references = valueize_refs_1 (shared_lookup_references,
1627 valueized_anything);
1628 return shared_lookup_references;
1631 /* Create a vector of vn_reference_op_s structures from CALL, a
1632 call statement. The vector is shared among all callers of
1633 this function. */
1635 static vec<vn_reference_op_s>
1636 valueize_shared_reference_ops_from_call (gcall *call)
1638 if (!call)
1639 return vNULL;
1640 shared_lookup_references.truncate (0);
1641 copy_reference_ops_from_call (call, &shared_lookup_references);
1642 shared_lookup_references = valueize_refs (shared_lookup_references);
1643 return shared_lookup_references;
1646 /* Lookup a SCCVN reference operation VR in the current hash table.
1647 Returns the resulting value number if it exists in the hash table,
1648 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1649 vn_reference_t stored in the hashtable if something is found. */
1651 static tree
1652 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1654 vn_reference_s **slot;
1655 hashval_t hash;
1657 hash = vr->hashcode;
1658 slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1659 if (slot)
1661 if (vnresult)
1662 *vnresult = (vn_reference_t)*slot;
1663 return ((vn_reference_t)*slot)->result;
1666 return NULL_TREE;
1669 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1670 with the current VUSE and performs the expression lookup. */
1672 static void *
1673 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse,
1674 unsigned int cnt, void *vr_)
1676 vn_reference_t vr = (vn_reference_t)vr_;
1677 vn_reference_s **slot;
1678 hashval_t hash;
1680 /* This bounds the stmt walks we perform on reference lookups
1681 to O(1) instead of O(N) where N is the number of dominating
1682 stores. */
1683 if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
1684 return (void *)-1;
1686 if (last_vuse_ptr)
1687 *last_vuse_ptr = vuse;
1689 /* Fixup vuse and hash. */
1690 if (vr->vuse)
1691 vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1692 vr->vuse = vuse_ssa_val (vuse);
1693 if (vr->vuse)
1694 vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1696 hash = vr->hashcode;
1697 slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1698 if (slot)
1699 return *slot;
1701 return NULL;
1704 /* Lookup an existing or insert a new vn_reference entry into the
1705 value table for the VUSE, SET, TYPE, OPERANDS reference which
1706 has the value VALUE which is either a constant or an SSA name. */
1708 static vn_reference_t
1709 vn_reference_lookup_or_insert_for_pieces (tree vuse,
1710 alias_set_type set,
1711 tree type,
1712 vec<vn_reference_op_s,
1713 va_heap> operands,
1714 tree value)
1716 vn_reference_s vr1;
1717 vn_reference_t result;
1718 unsigned value_id;
1719 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1720 vr1.operands = operands;
1721 vr1.type = type;
1722 vr1.set = set;
1723 vr1.hashcode = vn_reference_compute_hash (&vr1);
1724 if (vn_reference_lookup_1 (&vr1, &result))
1725 return result;
1726 if (TREE_CODE (value) == SSA_NAME)
1727 value_id = VN_INFO (value)->value_id;
1728 else
1729 value_id = get_or_alloc_constant_value_id (value);
1730 return vn_reference_insert_pieces (vuse, set, type,
1731 operands.copy (), value, value_id);
1734 /* Return a value-number for RCODE OPS... either by looking up an existing
1735 value-number for the simplified result or by inserting the operation if
1736 INSERT is true. */
1738 static tree
1739 vn_nary_build_or_lookup_1 (gimple_match_op *res_op, bool insert)
1741 tree result = NULL_TREE;
1742 /* We will be creating a value number for
1743 RCODE (OPS...).
1744 So first simplify and lookup this expression to see if it
1745 is already available. */
1746 mprts_hook = vn_lookup_simplify_result;
1747 bool res = false;
1748 switch (TREE_CODE_LENGTH ((tree_code) res_op->code))
1750 case 1:
1751 res = gimple_resimplify1 (NULL, res_op, vn_valueize);
1752 break;
1753 case 2:
1754 res = gimple_resimplify2 (NULL, res_op, vn_valueize);
1755 break;
1756 case 3:
1757 res = gimple_resimplify3 (NULL, res_op, vn_valueize);
1758 break;
1760 mprts_hook = NULL;
1761 gimple *new_stmt = NULL;
1762 if (res
1763 && gimple_simplified_result_is_gimple_val (res_op))
1765 /* The expression is already available. */
1766 result = res_op->ops[0];
1767 /* Valueize it, simplification returns sth in AVAIL only. */
1768 if (TREE_CODE (result) == SSA_NAME)
1769 result = SSA_VAL (result);
1771 else
1773 tree val = vn_lookup_simplify_result (res_op);
1774 if (!val && insert)
1776 gimple_seq stmts = NULL;
1777 result = maybe_push_res_to_seq (res_op, &stmts);
1778 if (result)
1780 gcc_assert (gimple_seq_singleton_p (stmts));
1781 new_stmt = gimple_seq_first_stmt (stmts);
1784 else
1785 /* The expression is already available. */
1786 result = val;
1788 if (new_stmt)
1790 /* The expression is not yet available, value-number lhs to
1791 the new SSA_NAME we created. */
1792 /* Initialize value-number information properly. */
1793 vn_ssa_aux_t result_info = VN_INFO (result);
1794 result_info->valnum = result;
1795 result_info->value_id = get_next_value_id ();
1796 result_info->visited = 1;
1797 gimple_seq_add_stmt_without_update (&VN_INFO (result)->expr,
1798 new_stmt);
1799 result_info->needs_insertion = true;
1800 /* ??? PRE phi-translation inserts NARYs without corresponding
1801 SSA name result. Re-use those but set their result according
1802 to the stmt we just built. */
1803 vn_nary_op_t nary = NULL;
1804 vn_nary_op_lookup_stmt (new_stmt, &nary);
1805 if (nary)
1807 gcc_assert (! nary->predicated_values && nary->u.result == NULL_TREE);
1808 nary->u.result = gimple_assign_lhs (new_stmt);
1810 /* As all "inserted" statements are singleton SCCs, insert
1811 to the valid table. This is strictly needed to
1812 avoid re-generating new value SSA_NAMEs for the same
1813 expression during SCC iteration over and over (the
1814 optimistic table gets cleared after each iteration).
1815 We do not need to insert into the optimistic table, as
1816 lookups there will fall back to the valid table. */
1817 else
1819 unsigned int length = vn_nary_length_from_stmt (new_stmt);
1820 vn_nary_op_t vno1
1821 = alloc_vn_nary_op_noinit (length, &vn_tables_insert_obstack);
1822 vno1->value_id = result_info->value_id;
1823 vno1->length = length;
1824 vno1->predicated_values = 0;
1825 vno1->u.result = result;
1826 init_vn_nary_op_from_stmt (vno1, new_stmt);
1827 vn_nary_op_insert_into (vno1, valid_info->nary, true);
1828 /* Also do not link it into the undo chain. */
1829 last_inserted_nary = vno1->next;
1830 vno1->next = (vn_nary_op_t)(void *)-1;
1832 if (dump_file && (dump_flags & TDF_DETAILS))
1834 fprintf (dump_file, "Inserting name ");
1835 print_generic_expr (dump_file, result);
1836 fprintf (dump_file, " for expression ");
1837 print_gimple_expr (dump_file, new_stmt, 0, TDF_SLIM);
1838 fprintf (dump_file, "\n");
1841 return result;
1844 /* Return a value-number for RCODE OPS... either by looking up an existing
1845 value-number for the simplified result or by inserting the operation. */
1847 static tree
1848 vn_nary_build_or_lookup (gimple_match_op *res_op)
1850 return vn_nary_build_or_lookup_1 (res_op, true);
1853 /* Try to simplify the expression RCODE OPS... of type TYPE and return
1854 its value if present. */
1856 tree
1857 vn_nary_simplify (vn_nary_op_t nary)
1859 if (nary->length > gimple_match_op::MAX_NUM_OPS)
1860 return NULL_TREE;
1861 gimple_match_op op (gimple_match_cond::UNCOND, nary->opcode,
1862 nary->type, nary->length);
1863 memcpy (op.ops, nary->op, sizeof (tree) * nary->length);
1864 return vn_nary_build_or_lookup_1 (&op, false);
1867 basic_block vn_context_bb;
1869 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1870 from the statement defining VUSE and if not successful tries to
1871 translate *REFP and VR_ through an aggregate copy at the definition
1872 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
1873 of *REF and *VR. If only disambiguation was performed then
1874 *DISAMBIGUATE_ONLY is set to true. */
1876 static void *
1877 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_,
1878 bool *disambiguate_only)
1880 vn_reference_t vr = (vn_reference_t)vr_;
1881 gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
1882 tree base = ao_ref_base (ref);
1883 HOST_WIDE_INT offseti, maxsizei;
1884 static vec<vn_reference_op_s> lhs_ops;
1885 ao_ref lhs_ref;
1886 bool lhs_ref_ok = false;
1887 poly_int64 copy_size;
1889 /* First try to disambiguate after value-replacing in the definitions LHS. */
1890 if (is_gimple_assign (def_stmt))
1892 tree lhs = gimple_assign_lhs (def_stmt);
1893 bool valueized_anything = false;
1894 /* Avoid re-allocation overhead. */
1895 lhs_ops.truncate (0);
1896 basic_block saved_rpo_bb = vn_context_bb;
1897 vn_context_bb = gimple_bb (def_stmt);
1898 copy_reference_ops_from_ref (lhs, &lhs_ops);
1899 lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything, true);
1900 vn_context_bb = saved_rpo_bb;
1901 if (valueized_anything)
1903 lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
1904 get_alias_set (lhs),
1905 TREE_TYPE (lhs), lhs_ops);
1906 if (lhs_ref_ok
1907 && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1909 *disambiguate_only = true;
1910 return NULL;
1913 else
1915 ao_ref_init (&lhs_ref, lhs);
1916 lhs_ref_ok = true;
1919 /* If we reach a clobbering statement try to skip it and see if
1920 we find a VN result with exactly the same value as the
1921 possible clobber. In this case we can ignore the clobber
1922 and return the found value.
1923 Note that we don't need to worry about partial overlapping
1924 accesses as we then can use TBAA to disambiguate against the
1925 clobbering statement when looking up a load (thus the
1926 VN_WALKREWRITE guard). */
1927 if (vn_walk_kind == VN_WALKREWRITE
1928 && is_gimple_reg_type (TREE_TYPE (lhs))
1929 && types_compatible_p (TREE_TYPE (lhs), vr->type))
1931 tree *saved_last_vuse_ptr = last_vuse_ptr;
1932 /* Do not update last_vuse_ptr in vn_reference_lookup_2. */
1933 last_vuse_ptr = NULL;
1934 tree saved_vuse = vr->vuse;
1935 hashval_t saved_hashcode = vr->hashcode;
1936 void *res = vn_reference_lookup_2 (ref,
1937 gimple_vuse (def_stmt), 0, vr);
1938 /* Need to restore vr->vuse and vr->hashcode. */
1939 vr->vuse = saved_vuse;
1940 vr->hashcode = saved_hashcode;
1941 last_vuse_ptr = saved_last_vuse_ptr;
1942 if (res && res != (void *)-1)
1944 vn_reference_t vnresult = (vn_reference_t) res;
1945 if (vnresult->result
1946 && operand_equal_p (vnresult->result,
1947 gimple_assign_rhs1 (def_stmt), 0))
1948 return res;
1952 else if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL)
1953 && gimple_call_num_args (def_stmt) <= 4)
1955 /* For builtin calls valueize its arguments and call the
1956 alias oracle again. Valueization may improve points-to
1957 info of pointers and constify size and position arguments.
1958 Originally this was motivated by PR61034 which has
1959 conditional calls to free falsely clobbering ref because
1960 of imprecise points-to info of the argument. */
1961 tree oldargs[4];
1962 bool valueized_anything = false;
1963 for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
1965 oldargs[i] = gimple_call_arg (def_stmt, i);
1966 tree val = vn_valueize (oldargs[i]);
1967 if (val != oldargs[i])
1969 gimple_call_set_arg (def_stmt, i, val);
1970 valueized_anything = true;
1973 if (valueized_anything)
1975 bool res = call_may_clobber_ref_p_1 (as_a <gcall *> (def_stmt),
1976 ref);
1977 for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
1978 gimple_call_set_arg (def_stmt, i, oldargs[i]);
1979 if (!res)
1981 *disambiguate_only = true;
1982 return NULL;
1987 if (*disambiguate_only)
1988 return (void *)-1;
1990 /* If we cannot constrain the size of the reference we cannot
1991 test if anything kills it. */
1992 if (!ref->max_size_known_p ())
1993 return (void *)-1;
1995 poly_int64 offset = ref->offset;
1996 poly_int64 maxsize = ref->max_size;
1998 /* We can't deduce anything useful from clobbers. */
1999 if (gimple_clobber_p (def_stmt))
2000 return (void *)-1;
2002 /* def_stmt may-defs *ref. See if we can derive a value for *ref
2003 from that definition.
2004 1) Memset. */
2005 if (is_gimple_reg_type (vr->type)
2006 && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
2007 && (integer_zerop (gimple_call_arg (def_stmt, 1))
2008 || ((TREE_CODE (gimple_call_arg (def_stmt, 1)) == INTEGER_CST
2009 || (INTEGRAL_TYPE_P (vr->type) && known_eq (ref->size, 8)))
2010 && CHAR_BIT == 8 && BITS_PER_UNIT == 8
2011 && offset.is_constant (&offseti)
2012 && offseti % BITS_PER_UNIT == 0))
2013 && poly_int_tree_p (gimple_call_arg (def_stmt, 2))
2014 && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
2015 || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME))
2017 tree base2;
2018 poly_int64 offset2, size2, maxsize2;
2019 bool reverse;
2020 tree ref2 = gimple_call_arg (def_stmt, 0);
2021 if (TREE_CODE (ref2) == SSA_NAME)
2023 ref2 = SSA_VAL (ref2);
2024 if (TREE_CODE (ref2) == SSA_NAME
2025 && (TREE_CODE (base) != MEM_REF
2026 || TREE_OPERAND (base, 0) != ref2))
2028 gimple *def_stmt = SSA_NAME_DEF_STMT (ref2);
2029 if (gimple_assign_single_p (def_stmt)
2030 && gimple_assign_rhs_code (def_stmt) == ADDR_EXPR)
2031 ref2 = gimple_assign_rhs1 (def_stmt);
2034 if (TREE_CODE (ref2) == ADDR_EXPR)
2036 ref2 = TREE_OPERAND (ref2, 0);
2037 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2,
2038 &reverse);
2039 if (!known_size_p (maxsize2)
2040 || !known_eq (maxsize2, size2)
2041 || !operand_equal_p (base, base2, OEP_ADDRESS_OF))
2042 return (void *)-1;
2044 else if (TREE_CODE (ref2) == SSA_NAME)
2046 poly_int64 soff;
2047 if (TREE_CODE (base) != MEM_REF
2048 || !(mem_ref_offset (base) << LOG2_BITS_PER_UNIT).to_shwi (&soff))
2049 return (void *)-1;
2050 offset += soff;
2051 offset2 = 0;
2052 if (TREE_OPERAND (base, 0) != ref2)
2054 gimple *def = SSA_NAME_DEF_STMT (ref2);
2055 if (is_gimple_assign (def)
2056 && gimple_assign_rhs_code (def) == POINTER_PLUS_EXPR
2057 && gimple_assign_rhs1 (def) == TREE_OPERAND (base, 0)
2058 && poly_int_tree_p (gimple_assign_rhs2 (def))
2059 && (wi::to_poly_offset (gimple_assign_rhs2 (def))
2060 << LOG2_BITS_PER_UNIT).to_shwi (&offset2))
2062 ref2 = gimple_assign_rhs1 (def);
2063 if (TREE_CODE (ref2) == SSA_NAME)
2064 ref2 = SSA_VAL (ref2);
2066 else
2067 return (void *)-1;
2070 else
2071 return (void *)-1;
2072 tree len = gimple_call_arg (def_stmt, 2);
2073 if (known_subrange_p (offset, maxsize, offset2,
2074 wi::to_poly_offset (len) << LOG2_BITS_PER_UNIT))
2076 tree val;
2077 if (integer_zerop (gimple_call_arg (def_stmt, 1)))
2078 val = build_zero_cst (vr->type);
2079 else if (INTEGRAL_TYPE_P (vr->type)
2080 && known_eq (ref->size, 8))
2082 gimple_match_op res_op (gimple_match_cond::UNCOND, NOP_EXPR,
2083 vr->type, gimple_call_arg (def_stmt, 1));
2084 val = vn_nary_build_or_lookup (&res_op);
2085 if (!val
2086 || (TREE_CODE (val) == SSA_NAME
2087 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val)))
2088 return (void *)-1;
2090 else
2092 unsigned len = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (vr->type));
2093 unsigned char *buf = XALLOCAVEC (unsigned char, len);
2094 memset (buf, TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 1)),
2095 len);
2096 val = native_interpret_expr (vr->type, buf, len);
2097 if (!val)
2098 return (void *)-1;
2100 return vn_reference_lookup_or_insert_for_pieces
2101 (vuse, vr->set, vr->type, vr->operands, val);
2105 /* 2) Assignment from an empty CONSTRUCTOR. */
2106 else if (is_gimple_reg_type (vr->type)
2107 && gimple_assign_single_p (def_stmt)
2108 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
2109 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
2111 tree base2;
2112 poly_int64 offset2, size2, maxsize2;
2113 bool reverse;
2114 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
2115 &offset2, &size2, &maxsize2, &reverse);
2116 if (known_size_p (maxsize2)
2117 && operand_equal_p (base, base2, 0)
2118 && known_subrange_p (offset, maxsize, offset2, size2))
2120 tree val = build_zero_cst (vr->type);
2121 return vn_reference_lookup_or_insert_for_pieces
2122 (vuse, vr->set, vr->type, vr->operands, val);
2126 /* 3) Assignment from a constant. We can use folds native encode/interpret
2127 routines to extract the assigned bits. */
2128 else if (known_eq (ref->size, maxsize)
2129 && is_gimple_reg_type (vr->type)
2130 && !contains_storage_order_barrier_p (vr->operands)
2131 && gimple_assign_single_p (def_stmt)
2132 && CHAR_BIT == 8 && BITS_PER_UNIT == 8
2133 /* native_encode and native_decode operate on arrays of bytes
2134 and so fundamentally need a compile-time size and offset. */
2135 && maxsize.is_constant (&maxsizei)
2136 && maxsizei % BITS_PER_UNIT == 0
2137 && offset.is_constant (&offseti)
2138 && offseti % BITS_PER_UNIT == 0
2139 && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt))
2140 || (TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
2141 && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt))))))
2143 tree base2;
2144 HOST_WIDE_INT offset2, size2;
2145 bool reverse;
2146 base2 = get_ref_base_and_extent_hwi (gimple_assign_lhs (def_stmt),
2147 &offset2, &size2, &reverse);
2148 if (base2
2149 && !reverse
2150 && size2 % BITS_PER_UNIT == 0
2151 && offset2 % BITS_PER_UNIT == 0
2152 && operand_equal_p (base, base2, 0)
2153 && known_subrange_p (offseti, maxsizei, offset2, size2))
2155 /* We support up to 512-bit values (for V8DFmode). */
2156 unsigned char buffer[64];
2157 int len;
2159 tree rhs = gimple_assign_rhs1 (def_stmt);
2160 if (TREE_CODE (rhs) == SSA_NAME)
2161 rhs = SSA_VAL (rhs);
2162 len = native_encode_expr (gimple_assign_rhs1 (def_stmt),
2163 buffer, sizeof (buffer),
2164 (offseti - offset2) / BITS_PER_UNIT);
2165 if (len > 0 && len * BITS_PER_UNIT >= maxsizei)
2167 tree type = vr->type;
2168 /* Make sure to interpret in a type that has a range
2169 covering the whole access size. */
2170 if (INTEGRAL_TYPE_P (vr->type)
2171 && maxsizei != TYPE_PRECISION (vr->type))
2172 type = build_nonstandard_integer_type (maxsizei,
2173 TYPE_UNSIGNED (type));
2174 tree val = native_interpret_expr (type, buffer,
2175 maxsizei / BITS_PER_UNIT);
2176 /* If we chop off bits because the types precision doesn't
2177 match the memory access size this is ok when optimizing
2178 reads but not when called from the DSE code during
2179 elimination. */
2180 if (val
2181 && type != vr->type)
2183 if (! int_fits_type_p (val, vr->type))
2184 val = NULL_TREE;
2185 else
2186 val = fold_convert (vr->type, val);
2189 if (val)
2190 return vn_reference_lookup_or_insert_for_pieces
2191 (vuse, vr->set, vr->type, vr->operands, val);
2196 /* 4) Assignment from an SSA name which definition we may be able
2197 to access pieces from. */
2198 else if (known_eq (ref->size, maxsize)
2199 && is_gimple_reg_type (vr->type)
2200 && !contains_storage_order_barrier_p (vr->operands)
2201 && gimple_assign_single_p (def_stmt)
2202 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
2204 tree base2;
2205 poly_int64 offset2, size2, maxsize2;
2206 bool reverse;
2207 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
2208 &offset2, &size2, &maxsize2,
2209 &reverse);
2210 if (!reverse
2211 && known_size_p (maxsize2)
2212 && known_eq (maxsize2, size2)
2213 && operand_equal_p (base, base2, 0)
2214 && known_subrange_p (offset, maxsize, offset2, size2)
2215 /* ??? We can't handle bitfield precision extracts without
2216 either using an alternate type for the BIT_FIELD_REF and
2217 then doing a conversion or possibly adjusting the offset
2218 according to endianness. */
2219 && (! INTEGRAL_TYPE_P (vr->type)
2220 || known_eq (ref->size, TYPE_PRECISION (vr->type)))
2221 && multiple_p (ref->size, BITS_PER_UNIT))
2223 gimple_match_op op (gimple_match_cond::UNCOND,
2224 BIT_FIELD_REF, vr->type,
2225 vn_valueize (gimple_assign_rhs1 (def_stmt)),
2226 bitsize_int (ref->size),
2227 bitsize_int (offset - offset2));
2228 tree val = vn_nary_build_or_lookup (&op);
2229 if (val
2230 && (TREE_CODE (val) != SSA_NAME
2231 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val)))
2233 vn_reference_t res = vn_reference_lookup_or_insert_for_pieces
2234 (vuse, vr->set, vr->type, vr->operands, val);
2235 return res;
2240 /* 5) For aggregate copies translate the reference through them if
2241 the copy kills ref. */
2242 else if (vn_walk_kind == VN_WALKREWRITE
2243 && gimple_assign_single_p (def_stmt)
2244 && (DECL_P (gimple_assign_rhs1 (def_stmt))
2245 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
2246 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
2248 tree base2;
2249 int i, j, k;
2250 auto_vec<vn_reference_op_s> rhs;
2251 vn_reference_op_t vro;
2252 ao_ref r;
2254 if (!lhs_ref_ok)
2255 return (void *)-1;
2257 /* See if the assignment kills REF. */
2258 base2 = ao_ref_base (&lhs_ref);
2259 if (!lhs_ref.max_size_known_p ()
2260 || (base != base2
2261 && (TREE_CODE (base) != MEM_REF
2262 || TREE_CODE (base2) != MEM_REF
2263 || TREE_OPERAND (base, 0) != TREE_OPERAND (base2, 0)
2264 || !tree_int_cst_equal (TREE_OPERAND (base, 1),
2265 TREE_OPERAND (base2, 1))))
2266 || !stmt_kills_ref_p (def_stmt, ref))
2267 return (void *)-1;
2269 /* Find the common base of ref and the lhs. lhs_ops already
2270 contains valueized operands for the lhs. */
2271 i = vr->operands.length () - 1;
2272 j = lhs_ops.length () - 1;
2273 while (j >= 0 && i >= 0
2274 && vn_reference_op_eq (&vr->operands[i], &lhs_ops[j]))
2276 i--;
2277 j--;
2280 /* ??? The innermost op should always be a MEM_REF and we already
2281 checked that the assignment to the lhs kills vr. Thus for
2282 aggregate copies using char[] types the vn_reference_op_eq
2283 may fail when comparing types for compatibility. But we really
2284 don't care here - further lookups with the rewritten operands
2285 will simply fail if we messed up types too badly. */
2286 poly_int64 extra_off = 0;
2287 if (j == 0 && i >= 0
2288 && lhs_ops[0].opcode == MEM_REF
2289 && maybe_ne (lhs_ops[0].off, -1))
2291 if (known_eq (lhs_ops[0].off, vr->operands[i].off))
2292 i--, j--;
2293 else if (vr->operands[i].opcode == MEM_REF
2294 && maybe_ne (vr->operands[i].off, -1))
2296 extra_off = vr->operands[i].off - lhs_ops[0].off;
2297 i--, j--;
2301 /* i now points to the first additional op.
2302 ??? LHS may not be completely contained in VR, one or more
2303 VIEW_CONVERT_EXPRs could be in its way. We could at least
2304 try handling outermost VIEW_CONVERT_EXPRs. */
2305 if (j != -1)
2306 return (void *)-1;
2308 /* Punt if the additional ops contain a storage order barrier. */
2309 for (k = i; k >= 0; k--)
2311 vro = &vr->operands[k];
2312 if (vro->opcode == VIEW_CONVERT_EXPR && vro->reverse)
2313 return (void *)-1;
2316 /* Now re-write REF to be based on the rhs of the assignment. */
2317 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
2319 /* Apply an extra offset to the inner MEM_REF of the RHS. */
2320 if (maybe_ne (extra_off, 0))
2322 if (rhs.length () < 2)
2323 return (void *)-1;
2324 int ix = rhs.length () - 2;
2325 if (rhs[ix].opcode != MEM_REF
2326 || known_eq (rhs[ix].off, -1))
2327 return (void *)-1;
2328 rhs[ix].off += extra_off;
2329 rhs[ix].op0 = int_const_binop (PLUS_EXPR, rhs[ix].op0,
2330 build_int_cst (TREE_TYPE (rhs[ix].op0),
2331 extra_off));
2334 /* We need to pre-pend vr->operands[0..i] to rhs. */
2335 vec<vn_reference_op_s> old = vr->operands;
2336 if (i + 1 + rhs.length () > vr->operands.length ())
2337 vr->operands.safe_grow (i + 1 + rhs.length ());
2338 else
2339 vr->operands.truncate (i + 1 + rhs.length ());
2340 FOR_EACH_VEC_ELT (rhs, j, vro)
2341 vr->operands[i + 1 + j] = *vro;
2342 vr->operands = valueize_refs (vr->operands);
2343 if (old == shared_lookup_references)
2344 shared_lookup_references = vr->operands;
2345 vr->hashcode = vn_reference_compute_hash (vr);
2347 /* Try folding the new reference to a constant. */
2348 tree val = fully_constant_vn_reference_p (vr);
2349 if (val)
2350 return vn_reference_lookup_or_insert_for_pieces
2351 (vuse, vr->set, vr->type, vr->operands, val);
2353 /* Adjust *ref from the new operands. */
2354 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
2355 return (void *)-1;
2356 /* This can happen with bitfields. */
2357 if (maybe_ne (ref->size, r.size))
2358 return (void *)-1;
2359 *ref = r;
2361 /* Do not update last seen VUSE after translating. */
2362 last_vuse_ptr = NULL;
2364 /* Keep looking for the adjusted *REF / VR pair. */
2365 return NULL;
2368 /* 6) For memcpy copies translate the reference through them if
2369 the copy kills ref. */
2370 else if (vn_walk_kind == VN_WALKREWRITE
2371 && is_gimple_reg_type (vr->type)
2372 /* ??? Handle BCOPY as well. */
2373 && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
2374 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
2375 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
2376 && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
2377 || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
2378 && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
2379 || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
2380 && poly_int_tree_p (gimple_call_arg (def_stmt, 2), &copy_size))
2382 tree lhs, rhs;
2383 ao_ref r;
2384 poly_int64 rhs_offset, lhs_offset;
2385 vn_reference_op_s op;
2386 poly_uint64 mem_offset;
2387 poly_int64 at, byte_maxsize;
2389 /* Only handle non-variable, addressable refs. */
2390 if (maybe_ne (ref->size, maxsize)
2391 || !multiple_p (offset, BITS_PER_UNIT, &at)
2392 || !multiple_p (maxsize, BITS_PER_UNIT, &byte_maxsize))
2393 return (void *)-1;
2395 /* Extract a pointer base and an offset for the destination. */
2396 lhs = gimple_call_arg (def_stmt, 0);
2397 lhs_offset = 0;
2398 if (TREE_CODE (lhs) == SSA_NAME)
2400 lhs = vn_valueize (lhs);
2401 if (TREE_CODE (lhs) == SSA_NAME)
2403 gimple *def_stmt = SSA_NAME_DEF_STMT (lhs);
2404 if (gimple_assign_single_p (def_stmt)
2405 && gimple_assign_rhs_code (def_stmt) == ADDR_EXPR)
2406 lhs = gimple_assign_rhs1 (def_stmt);
2409 if (TREE_CODE (lhs) == ADDR_EXPR)
2411 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
2412 &lhs_offset);
2413 if (!tem)
2414 return (void *)-1;
2415 if (TREE_CODE (tem) == MEM_REF
2416 && poly_int_tree_p (TREE_OPERAND (tem, 1), &mem_offset))
2418 lhs = TREE_OPERAND (tem, 0);
2419 if (TREE_CODE (lhs) == SSA_NAME)
2420 lhs = vn_valueize (lhs);
2421 lhs_offset += mem_offset;
2423 else if (DECL_P (tem))
2424 lhs = build_fold_addr_expr (tem);
2425 else
2426 return (void *)-1;
2428 if (TREE_CODE (lhs) != SSA_NAME
2429 && TREE_CODE (lhs) != ADDR_EXPR)
2430 return (void *)-1;
2432 /* Extract a pointer base and an offset for the source. */
2433 rhs = gimple_call_arg (def_stmt, 1);
2434 rhs_offset = 0;
2435 if (TREE_CODE (rhs) == SSA_NAME)
2436 rhs = vn_valueize (rhs);
2437 if (TREE_CODE (rhs) == ADDR_EXPR)
2439 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
2440 &rhs_offset);
2441 if (!tem)
2442 return (void *)-1;
2443 if (TREE_CODE (tem) == MEM_REF
2444 && poly_int_tree_p (TREE_OPERAND (tem, 1), &mem_offset))
2446 rhs = TREE_OPERAND (tem, 0);
2447 rhs_offset += mem_offset;
2449 else if (DECL_P (tem)
2450 || TREE_CODE (tem) == STRING_CST)
2451 rhs = build_fold_addr_expr (tem);
2452 else
2453 return (void *)-1;
2455 if (TREE_CODE (rhs) != SSA_NAME
2456 && TREE_CODE (rhs) != ADDR_EXPR)
2457 return (void *)-1;
2459 /* The bases of the destination and the references have to agree. */
2460 if (TREE_CODE (base) == MEM_REF)
2462 if (TREE_OPERAND (base, 0) != lhs
2463 || !poly_int_tree_p (TREE_OPERAND (base, 1), &mem_offset))
2464 return (void *) -1;
2465 at += mem_offset;
2467 else if (!DECL_P (base)
2468 || TREE_CODE (lhs) != ADDR_EXPR
2469 || TREE_OPERAND (lhs, 0) != base)
2470 return (void *)-1;
2472 /* If the access is completely outside of the memcpy destination
2473 area there is no aliasing. */
2474 if (!ranges_maybe_overlap_p (lhs_offset, copy_size, at, byte_maxsize))
2475 return NULL;
2476 /* And the access has to be contained within the memcpy destination. */
2477 if (!known_subrange_p (at, byte_maxsize, lhs_offset, copy_size))
2478 return (void *)-1;
2480 /* Make room for 2 operands in the new reference. */
2481 if (vr->operands.length () < 2)
2483 vec<vn_reference_op_s> old = vr->operands;
2484 vr->operands.safe_grow_cleared (2);
2485 if (old == shared_lookup_references)
2486 shared_lookup_references = vr->operands;
2488 else
2489 vr->operands.truncate (2);
2491 /* The looked-through reference is a simple MEM_REF. */
2492 memset (&op, 0, sizeof (op));
2493 op.type = vr->type;
2494 op.opcode = MEM_REF;
2495 op.op0 = build_int_cst (ptr_type_node, at - lhs_offset + rhs_offset);
2496 op.off = at - lhs_offset + rhs_offset;
2497 vr->operands[0] = op;
2498 op.type = TREE_TYPE (rhs);
2499 op.opcode = TREE_CODE (rhs);
2500 op.op0 = rhs;
2501 op.off = -1;
2502 vr->operands[1] = op;
2503 vr->hashcode = vn_reference_compute_hash (vr);
2505 /* Try folding the new reference to a constant. */
2506 tree val = fully_constant_vn_reference_p (vr);
2507 if (val)
2508 return vn_reference_lookup_or_insert_for_pieces
2509 (vuse, vr->set, vr->type, vr->operands, val);
2511 /* Adjust *ref from the new operands. */
2512 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
2513 return (void *)-1;
2514 /* This can happen with bitfields. */
2515 if (maybe_ne (ref->size, r.size))
2516 return (void *)-1;
2517 *ref = r;
2519 /* Do not update last seen VUSE after translating. */
2520 last_vuse_ptr = NULL;
2522 /* Keep looking for the adjusted *REF / VR pair. */
2523 return NULL;
2526 /* Bail out and stop walking. */
2527 return (void *)-1;
2530 /* Return a reference op vector from OP that can be used for
2531 vn_reference_lookup_pieces. The caller is responsible for releasing
2532 the vector. */
2534 vec<vn_reference_op_s>
2535 vn_reference_operands_for_lookup (tree op)
2537 bool valueized;
2538 return valueize_shared_reference_ops_from_ref (op, &valueized).copy ();
2541 /* Lookup a reference operation by it's parts, in the current hash table.
2542 Returns the resulting value number if it exists in the hash table,
2543 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2544 vn_reference_t stored in the hashtable if something is found. */
2546 tree
2547 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
2548 vec<vn_reference_op_s> operands,
2549 vn_reference_t *vnresult, vn_lookup_kind kind)
2551 struct vn_reference_s vr1;
2552 vn_reference_t tmp;
2553 tree cst;
2555 if (!vnresult)
2556 vnresult = &tmp;
2557 *vnresult = NULL;
2559 vr1.vuse = vuse_ssa_val (vuse);
2560 shared_lookup_references.truncate (0);
2561 shared_lookup_references.safe_grow (operands.length ());
2562 memcpy (shared_lookup_references.address (),
2563 operands.address (),
2564 sizeof (vn_reference_op_s)
2565 * operands.length ());
2566 vr1.operands = operands = shared_lookup_references
2567 = valueize_refs (shared_lookup_references);
2568 vr1.type = type;
2569 vr1.set = set;
2570 vr1.hashcode = vn_reference_compute_hash (&vr1);
2571 if ((cst = fully_constant_vn_reference_p (&vr1)))
2572 return cst;
2574 vn_reference_lookup_1 (&vr1, vnresult);
2575 if (!*vnresult
2576 && kind != VN_NOWALK
2577 && vr1.vuse)
2579 ao_ref r;
2580 vn_walk_kind = kind;
2581 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
2582 *vnresult =
2583 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
2584 vn_reference_lookup_2,
2585 vn_reference_lookup_3,
2586 vuse_valueize, &vr1);
2587 gcc_checking_assert (vr1.operands == shared_lookup_references);
2590 if (*vnresult)
2591 return (*vnresult)->result;
2593 return NULL_TREE;
2596 /* Lookup OP in the current hash table, and return the resulting value
2597 number if it exists in the hash table. Return NULL_TREE if it does
2598 not exist in the hash table or if the result field of the structure
2599 was NULL.. VNRESULT will be filled in with the vn_reference_t
2600 stored in the hashtable if one exists. When TBAA_P is false assume
2601 we are looking up a store and treat it as having alias-set zero. */
2603 tree
2604 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
2605 vn_reference_t *vnresult, bool tbaa_p)
2607 vec<vn_reference_op_s> operands;
2608 struct vn_reference_s vr1;
2609 tree cst;
2610 bool valuezied_anything;
2612 if (vnresult)
2613 *vnresult = NULL;
2615 vr1.vuse = vuse_ssa_val (vuse);
2616 vr1.operands = operands
2617 = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
2618 vr1.type = TREE_TYPE (op);
2619 vr1.set = tbaa_p ? get_alias_set (op) : 0;
2620 vr1.hashcode = vn_reference_compute_hash (&vr1);
2621 if ((cst = fully_constant_vn_reference_p (&vr1)))
2622 return cst;
2624 if (kind != VN_NOWALK
2625 && vr1.vuse)
2627 vn_reference_t wvnresult;
2628 ao_ref r;
2629 /* Make sure to use a valueized reference if we valueized anything.
2630 Otherwise preserve the full reference for advanced TBAA. */
2631 if (!valuezied_anything
2632 || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
2633 vr1.operands))
2634 ao_ref_init (&r, op);
2635 if (! tbaa_p)
2636 r.ref_alias_set = r.base_alias_set = 0;
2637 vn_walk_kind = kind;
2638 wvnresult =
2639 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
2640 vn_reference_lookup_2,
2641 vn_reference_lookup_3,
2642 vuse_valueize, &vr1);
2643 gcc_checking_assert (vr1.operands == shared_lookup_references);
2644 if (wvnresult)
2646 if (vnresult)
2647 *vnresult = wvnresult;
2648 return wvnresult->result;
2651 return NULL_TREE;
2654 return vn_reference_lookup_1 (&vr1, vnresult);
2657 /* Lookup CALL in the current hash table and return the entry in
2658 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2660 void
2661 vn_reference_lookup_call (gcall *call, vn_reference_t *vnresult,
2662 vn_reference_t vr)
2664 if (vnresult)
2665 *vnresult = NULL;
2667 tree vuse = gimple_vuse (call);
2669 vr->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2670 vr->operands = valueize_shared_reference_ops_from_call (call);
2671 vr->type = gimple_expr_type (call);
2672 vr->set = 0;
2673 vr->hashcode = vn_reference_compute_hash (vr);
2674 vn_reference_lookup_1 (vr, vnresult);
2677 /* Insert OP into the current hash table with a value number of RESULT. */
2679 static void
2680 vn_reference_insert (tree op, tree result, tree vuse, tree vdef)
2682 vn_reference_s **slot;
2683 vn_reference_t vr1;
2684 bool tem;
2686 vr1 = XOBNEW (&vn_tables_obstack, vn_reference_s);
2687 if (TREE_CODE (result) == SSA_NAME)
2688 vr1->value_id = VN_INFO (result)->value_id;
2689 else
2690 vr1->value_id = get_or_alloc_constant_value_id (result);
2691 vr1->vuse = vuse_ssa_val (vuse);
2692 vr1->operands = valueize_shared_reference_ops_from_ref (op, &tem).copy ();
2693 vr1->type = TREE_TYPE (op);
2694 vr1->set = get_alias_set (op);
2695 vr1->hashcode = vn_reference_compute_hash (vr1);
2696 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
2697 vr1->result_vdef = vdef;
2699 slot = valid_info->references->find_slot_with_hash (vr1, vr1->hashcode,
2700 INSERT);
2702 /* Because IL walking on reference lookup can end up visiting
2703 a def that is only to be visited later in iteration order
2704 when we are about to make an irreducible region reducible
2705 the def can be effectively processed and its ref being inserted
2706 by vn_reference_lookup_3 already. So we cannot assert (!*slot)
2707 but save a lookup if we deal with already inserted refs here. */
2708 if (*slot)
2710 /* We cannot assert that we have the same value either because
2711 when disentangling an irreducible region we may end up visiting
2712 a use before the corresponding def. That's a missed optimization
2713 only though. See gcc.dg/tree-ssa/pr87126.c for example. */
2714 if (dump_file && (dump_flags & TDF_DETAILS)
2715 && !operand_equal_p ((*slot)->result, vr1->result, 0))
2717 fprintf (dump_file, "Keeping old value ");
2718 print_generic_expr (dump_file, (*slot)->result);
2719 fprintf (dump_file, " because of collision\n");
2721 free_reference (vr1);
2722 obstack_free (&vn_tables_obstack, vr1);
2723 return;
2726 *slot = vr1;
2727 vr1->next = last_inserted_ref;
2728 last_inserted_ref = vr1;
2731 /* Insert a reference by it's pieces into the current hash table with
2732 a value number of RESULT. Return the resulting reference
2733 structure we created. */
2735 vn_reference_t
2736 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
2737 vec<vn_reference_op_s> operands,
2738 tree result, unsigned int value_id)
2741 vn_reference_s **slot;
2742 vn_reference_t vr1;
2744 vr1 = XOBNEW (&vn_tables_obstack, vn_reference_s);
2745 vr1->value_id = value_id;
2746 vr1->vuse = vuse_ssa_val (vuse);
2747 vr1->operands = valueize_refs (operands);
2748 vr1->type = type;
2749 vr1->set = set;
2750 vr1->hashcode = vn_reference_compute_hash (vr1);
2751 if (result && TREE_CODE (result) == SSA_NAME)
2752 result = SSA_VAL (result);
2753 vr1->result = result;
2755 slot = valid_info->references->find_slot_with_hash (vr1, vr1->hashcode,
2756 INSERT);
2758 /* At this point we should have all the things inserted that we have
2759 seen before, and we should never try inserting something that
2760 already exists. */
2761 gcc_assert (!*slot);
2763 *slot = vr1;
2764 vr1->next = last_inserted_ref;
2765 last_inserted_ref = vr1;
2766 return vr1;
2769 /* Compute and return the hash value for nary operation VBO1. */
2771 static hashval_t
2772 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
2774 inchash::hash hstate;
2775 unsigned i;
2777 for (i = 0; i < vno1->length; ++i)
2778 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
2779 vno1->op[i] = SSA_VAL (vno1->op[i]);
2781 if (((vno1->length == 2
2782 && commutative_tree_code (vno1->opcode))
2783 || (vno1->length == 3
2784 && commutative_ternary_tree_code (vno1->opcode)))
2785 && tree_swap_operands_p (vno1->op[0], vno1->op[1]))
2786 std::swap (vno1->op[0], vno1->op[1]);
2787 else if (TREE_CODE_CLASS (vno1->opcode) == tcc_comparison
2788 && tree_swap_operands_p (vno1->op[0], vno1->op[1]))
2790 std::swap (vno1->op[0], vno1->op[1]);
2791 vno1->opcode = swap_tree_comparison (vno1->opcode);
2794 hstate.add_int (vno1->opcode);
2795 for (i = 0; i < vno1->length; ++i)
2796 inchash::add_expr (vno1->op[i], hstate);
2798 return hstate.end ();
2801 /* Compare nary operations VNO1 and VNO2 and return true if they are
2802 equivalent. */
2804 bool
2805 vn_nary_op_eq (const_vn_nary_op_t const vno1, const_vn_nary_op_t const vno2)
2807 unsigned i;
2809 if (vno1->hashcode != vno2->hashcode)
2810 return false;
2812 if (vno1->length != vno2->length)
2813 return false;
2815 if (vno1->opcode != vno2->opcode
2816 || !types_compatible_p (vno1->type, vno2->type))
2817 return false;
2819 for (i = 0; i < vno1->length; ++i)
2820 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
2821 return false;
2823 /* BIT_INSERT_EXPR has an implict operand as the type precision
2824 of op1. Need to check to make sure they are the same. */
2825 if (vno1->opcode == BIT_INSERT_EXPR
2826 && TREE_CODE (vno1->op[1]) == INTEGER_CST
2827 && TYPE_PRECISION (TREE_TYPE (vno1->op[1]))
2828 != TYPE_PRECISION (TREE_TYPE (vno2->op[1])))
2829 return false;
2831 return true;
2834 /* Initialize VNO from the pieces provided. */
2836 static void
2837 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
2838 enum tree_code code, tree type, tree *ops)
2840 vno->opcode = code;
2841 vno->length = length;
2842 vno->type = type;
2843 memcpy (&vno->op[0], ops, sizeof (tree) * length);
2846 /* Initialize VNO from OP. */
2848 static void
2849 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
2851 unsigned i;
2853 vno->opcode = TREE_CODE (op);
2854 vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
2855 vno->type = TREE_TYPE (op);
2856 for (i = 0; i < vno->length; ++i)
2857 vno->op[i] = TREE_OPERAND (op, i);
2860 /* Return the number of operands for a vn_nary ops structure from STMT. */
2862 static unsigned int
2863 vn_nary_length_from_stmt (gimple *stmt)
2865 switch (gimple_assign_rhs_code (stmt))
2867 case REALPART_EXPR:
2868 case IMAGPART_EXPR:
2869 case VIEW_CONVERT_EXPR:
2870 return 1;
2872 case BIT_FIELD_REF:
2873 return 3;
2875 case CONSTRUCTOR:
2876 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2878 default:
2879 return gimple_num_ops (stmt) - 1;
2883 /* Initialize VNO from STMT. */
2885 static void
2886 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple *stmt)
2888 unsigned i;
2890 vno->opcode = gimple_assign_rhs_code (stmt);
2891 vno->type = gimple_expr_type (stmt);
2892 switch (vno->opcode)
2894 case REALPART_EXPR:
2895 case IMAGPART_EXPR:
2896 case VIEW_CONVERT_EXPR:
2897 vno->length = 1;
2898 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2899 break;
2901 case BIT_FIELD_REF:
2902 vno->length = 3;
2903 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2904 vno->op[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 1);
2905 vno->op[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
2906 break;
2908 case CONSTRUCTOR:
2909 vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2910 for (i = 0; i < vno->length; ++i)
2911 vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value;
2912 break;
2914 default:
2915 gcc_checking_assert (!gimple_assign_single_p (stmt));
2916 vno->length = gimple_num_ops (stmt) - 1;
2917 for (i = 0; i < vno->length; ++i)
2918 vno->op[i] = gimple_op (stmt, i + 1);
2922 /* Compute the hashcode for VNO and look for it in the hash table;
2923 return the resulting value number if it exists in the hash table.
2924 Return NULL_TREE if it does not exist in the hash table or if the
2925 result field of the operation is NULL. VNRESULT will contain the
2926 vn_nary_op_t from the hashtable if it exists. */
2928 static tree
2929 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
2931 vn_nary_op_s **slot;
2933 if (vnresult)
2934 *vnresult = NULL;
2936 vno->hashcode = vn_nary_op_compute_hash (vno);
2937 slot = valid_info->nary->find_slot_with_hash (vno, vno->hashcode, NO_INSERT);
2938 if (!slot)
2939 return NULL_TREE;
2940 if (vnresult)
2941 *vnresult = *slot;
2942 return (*slot)->predicated_values ? NULL_TREE : (*slot)->u.result;
2945 /* Lookup a n-ary operation by its pieces and return the resulting value
2946 number if it exists in the hash table. Return NULL_TREE if it does
2947 not exist in the hash table or if the result field of the operation
2948 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2949 if it exists. */
2951 tree
2952 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2953 tree type, tree *ops, vn_nary_op_t *vnresult)
2955 vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s,
2956 sizeof_vn_nary_op (length));
2957 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2958 return vn_nary_op_lookup_1 (vno1, vnresult);
2961 /* Lookup OP in the current hash table, and return the resulting value
2962 number if it exists in the hash table. Return NULL_TREE if it does
2963 not exist in the hash table or if the result field of the operation
2964 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2965 if it exists. */
2967 tree
2968 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2970 vn_nary_op_t vno1
2971 = XALLOCAVAR (struct vn_nary_op_s,
2972 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op))));
2973 init_vn_nary_op_from_op (vno1, op);
2974 return vn_nary_op_lookup_1 (vno1, vnresult);
2977 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2978 value number if it exists in the hash table. Return NULL_TREE if
2979 it does not exist in the hash table. VNRESULT will contain the
2980 vn_nary_op_t from the hashtable if it exists. */
2982 tree
2983 vn_nary_op_lookup_stmt (gimple *stmt, vn_nary_op_t *vnresult)
2985 vn_nary_op_t vno1
2986 = XALLOCAVAR (struct vn_nary_op_s,
2987 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt)));
2988 init_vn_nary_op_from_stmt (vno1, stmt);
2989 return vn_nary_op_lookup_1 (vno1, vnresult);
2992 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2994 static vn_nary_op_t
2995 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2997 return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
3000 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
3001 obstack. */
3003 static vn_nary_op_t
3004 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
3006 vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length, &vn_tables_obstack);
3008 vno1->value_id = value_id;
3009 vno1->length = length;
3010 vno1->predicated_values = 0;
3011 vno1->u.result = result;
3013 return vno1;
3016 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
3017 VNO->HASHCODE first. */
3019 static vn_nary_op_t
3020 vn_nary_op_insert_into (vn_nary_op_t vno, vn_nary_op_table_type *table,
3021 bool compute_hash)
3023 vn_nary_op_s **slot;
3025 if (compute_hash)
3027 vno->hashcode = vn_nary_op_compute_hash (vno);
3028 gcc_assert (! vno->predicated_values
3029 || (! vno->u.values->next
3030 && vno->u.values->n == 1));
3033 slot = table->find_slot_with_hash (vno, vno->hashcode, INSERT);
3034 vno->unwind_to = *slot;
3035 if (*slot)
3037 /* Prefer non-predicated values.
3038 ??? Only if those are constant, otherwise, with constant predicated
3039 value, turn them into predicated values with entry-block validity
3040 (??? but we always find the first valid result currently). */
3041 if ((*slot)->predicated_values
3042 && ! vno->predicated_values)
3044 /* ??? We cannot remove *slot from the unwind stack list.
3045 For the moment we deal with this by skipping not found
3046 entries but this isn't ideal ... */
3047 *slot = vno;
3048 /* ??? Maintain a stack of states we can unwind in
3049 vn_nary_op_s? But how far do we unwind? In reality
3050 we need to push change records somewhere... Or not
3051 unwind vn_nary_op_s and linking them but instead
3052 unwind the results "list", linking that, which also
3053 doesn't move on hashtable resize. */
3054 /* We can also have a ->unwind_to recording *slot there.
3055 That way we can make u.values a fixed size array with
3056 recording the number of entries but of course we then
3057 have always N copies for each unwind_to-state. Or we
3058 make sure to only ever append and each unwinding will
3059 pop off one entry (but how to deal with predicated
3060 replaced with non-predicated here?) */
3061 vno->next = last_inserted_nary;
3062 last_inserted_nary = vno;
3063 return vno;
3065 else if (vno->predicated_values
3066 && ! (*slot)->predicated_values)
3067 return *slot;
3068 else if (vno->predicated_values
3069 && (*slot)->predicated_values)
3071 /* ??? Factor this all into a insert_single_predicated_value
3072 routine. */
3073 gcc_assert (!vno->u.values->next && vno->u.values->n == 1);
3074 basic_block vno_bb
3075 = BASIC_BLOCK_FOR_FN (cfun, vno->u.values->valid_dominated_by_p[0]);
3076 vn_pval *nval = vno->u.values;
3077 vn_pval **next = &vno->u.values;
3078 bool found = false;
3079 for (vn_pval *val = (*slot)->u.values; val; val = val->next)
3081 if (expressions_equal_p (val->result, vno->u.values->result))
3083 found = true;
3084 for (unsigned i = 0; i < val->n; ++i)
3086 basic_block val_bb
3087 = BASIC_BLOCK_FOR_FN (cfun,
3088 val->valid_dominated_by_p[i]);
3089 if (dominated_by_p (CDI_DOMINATORS, vno_bb, val_bb))
3090 /* Value registered with more generic predicate. */
3091 return *slot;
3092 else if (dominated_by_p (CDI_DOMINATORS, val_bb, vno_bb))
3093 /* Shouldn't happen, we insert in RPO order. */
3094 gcc_unreachable ();
3096 /* Append value. */
3097 *next = (vn_pval *) obstack_alloc (&vn_tables_obstack,
3098 sizeof (vn_pval)
3099 + val->n * sizeof (int));
3100 (*next)->next = NULL;
3101 (*next)->result = val->result;
3102 (*next)->n = val->n + 1;
3103 memcpy ((*next)->valid_dominated_by_p,
3104 val->valid_dominated_by_p,
3105 val->n * sizeof (int));
3106 (*next)->valid_dominated_by_p[val->n] = vno_bb->index;
3107 next = &(*next)->next;
3108 if (dump_file && (dump_flags & TDF_DETAILS))
3109 fprintf (dump_file, "Appending predicate to value.\n");
3110 continue;
3112 /* Copy other predicated values. */
3113 *next = (vn_pval *) obstack_alloc (&vn_tables_obstack,
3114 sizeof (vn_pval)
3115 + (val->n-1) * sizeof (int));
3116 memcpy (*next, val, sizeof (vn_pval) + (val->n-1) * sizeof (int));
3117 (*next)->next = NULL;
3118 next = &(*next)->next;
3120 if (!found)
3121 *next = nval;
3123 *slot = vno;
3124 vno->next = last_inserted_nary;
3125 last_inserted_nary = vno;
3126 return vno;
3129 /* While we do not want to insert things twice it's awkward to
3130 avoid it in the case where visit_nary_op pattern-matches stuff
3131 and ends up simplifying the replacement to itself. We then
3132 get two inserts, one from visit_nary_op and one from
3133 vn_nary_build_or_lookup.
3134 So allow inserts with the same value number. */
3135 if ((*slot)->u.result == vno->u.result)
3136 return *slot;
3139 /* ??? There's also optimistic vs. previous commited state merging
3140 that is problematic for the case of unwinding. */
3142 /* ??? We should return NULL if we do not use 'vno' and have the
3143 caller release it. */
3144 gcc_assert (!*slot);
3146 *slot = vno;
3147 vno->next = last_inserted_nary;
3148 last_inserted_nary = vno;
3149 return vno;
3152 /* Insert a n-ary operation into the current hash table using it's
3153 pieces. Return the vn_nary_op_t structure we created and put in
3154 the hashtable. */
3156 vn_nary_op_t
3157 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
3158 tree type, tree *ops,
3159 tree result, unsigned int value_id)
3161 vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id);
3162 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
3163 return vn_nary_op_insert_into (vno1, valid_info->nary, true);
3166 static vn_nary_op_t
3167 vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
3168 tree type, tree *ops,
3169 tree result, unsigned int value_id,
3170 edge pred_e)
3172 /* ??? Currently tracking BBs. */
3173 if (! single_pred_p (pred_e->dest))
3175 /* Never record for backedges. */
3176 if (pred_e->flags & EDGE_DFS_BACK)
3177 return NULL;
3178 edge_iterator ei;
3179 edge e;
3180 int cnt = 0;
3181 /* Ignore backedges. */
3182 FOR_EACH_EDGE (e, ei, pred_e->dest->preds)
3183 if (! dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
3184 cnt++;
3185 if (cnt != 1)
3186 return NULL;
3188 if (dump_file && (dump_flags & TDF_DETAILS)
3189 /* ??? Fix dumping, but currently we only get comparisons. */
3190 && TREE_CODE_CLASS (code) == tcc_comparison)
3192 fprintf (dump_file, "Recording on edge %d->%d ", pred_e->src->index,
3193 pred_e->dest->index);
3194 print_generic_expr (dump_file, ops[0], TDF_SLIM);
3195 fprintf (dump_file, " %s ", get_tree_code_name (code));
3196 print_generic_expr (dump_file, ops[1], TDF_SLIM);
3197 fprintf (dump_file, " == %s\n",
3198 integer_zerop (result) ? "false" : "true");
3200 vn_nary_op_t vno1 = alloc_vn_nary_op (length, NULL_TREE, value_id);
3201 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
3202 vno1->predicated_values = 1;
3203 vno1->u.values = (vn_pval *) obstack_alloc (&vn_tables_obstack,
3204 sizeof (vn_pval));
3205 vno1->u.values->next = NULL;
3206 vno1->u.values->result = result;
3207 vno1->u.values->n = 1;
3208 vno1->u.values->valid_dominated_by_p[0] = pred_e->dest->index;
3209 return vn_nary_op_insert_into (vno1, valid_info->nary, true);
3212 static bool
3213 dominated_by_p_w_unex (basic_block bb1, basic_block bb2);
3215 static tree
3216 vn_nary_op_get_predicated_value (vn_nary_op_t vno, basic_block bb)
3218 if (! vno->predicated_values)
3219 return vno->u.result;
3220 for (vn_pval *val = vno->u.values; val; val = val->next)
3221 for (unsigned i = 0; i < val->n; ++i)
3222 if (dominated_by_p_w_unex (bb,
3223 BASIC_BLOCK_FOR_FN
3224 (cfun, val->valid_dominated_by_p[i])))
3225 return val->result;
3226 return NULL_TREE;
3229 /* Insert OP into the current hash table with a value number of
3230 RESULT. Return the vn_nary_op_t structure we created and put in
3231 the hashtable. */
3233 vn_nary_op_t
3234 vn_nary_op_insert (tree op, tree result)
3236 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
3237 vn_nary_op_t vno1;
3239 vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
3240 init_vn_nary_op_from_op (vno1, op);
3241 return vn_nary_op_insert_into (vno1, valid_info->nary, true);
3244 /* Insert the rhs of STMT into the current hash table with a value number of
3245 RESULT. */
3247 static vn_nary_op_t
3248 vn_nary_op_insert_stmt (gimple *stmt, tree result)
3250 vn_nary_op_t vno1
3251 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt),
3252 result, VN_INFO (result)->value_id);
3253 init_vn_nary_op_from_stmt (vno1, stmt);
3254 return vn_nary_op_insert_into (vno1, valid_info->nary, true);
3257 /* Compute a hashcode for PHI operation VP1 and return it. */
3259 static inline hashval_t
3260 vn_phi_compute_hash (vn_phi_t vp1)
3262 inchash::hash hstate (EDGE_COUNT (vp1->block->preds) > 2
3263 ? vp1->block->index : EDGE_COUNT (vp1->block->preds));
3264 tree phi1op;
3265 tree type;
3266 edge e;
3267 edge_iterator ei;
3269 /* If all PHI arguments are constants we need to distinguish
3270 the PHI node via its type. */
3271 type = vp1->type;
3272 hstate.merge_hash (vn_hash_type (type));
3274 FOR_EACH_EDGE (e, ei, vp1->block->preds)
3276 /* Don't hash backedge values they need to be handled as VN_TOP
3277 for optimistic value-numbering. */
3278 if (e->flags & EDGE_DFS_BACK)
3279 continue;
3281 phi1op = vp1->phiargs[e->dest_idx];
3282 if (phi1op == VN_TOP)
3283 continue;
3284 inchash::add_expr (phi1op, hstate);
3287 return hstate.end ();
3291 /* Return true if COND1 and COND2 represent the same condition, set
3292 *INVERTED_P if one needs to be inverted to make it the same as
3293 the other. */
3295 static bool
3296 cond_stmts_equal_p (gcond *cond1, tree lhs1, tree rhs1,
3297 gcond *cond2, tree lhs2, tree rhs2, bool *inverted_p)
3299 enum tree_code code1 = gimple_cond_code (cond1);
3300 enum tree_code code2 = gimple_cond_code (cond2);
3302 *inverted_p = false;
3303 if (code1 == code2)
3305 else if (code1 == swap_tree_comparison (code2))
3306 std::swap (lhs2, rhs2);
3307 else if (code1 == invert_tree_comparison (code2, HONOR_NANS (lhs2)))
3308 *inverted_p = true;
3309 else if (code1 == invert_tree_comparison
3310 (swap_tree_comparison (code2), HONOR_NANS (lhs2)))
3312 std::swap (lhs2, rhs2);
3313 *inverted_p = true;
3315 else
3316 return false;
3318 return ((expressions_equal_p (lhs1, lhs2)
3319 && expressions_equal_p (rhs1, rhs2))
3320 || (commutative_tree_code (code1)
3321 && expressions_equal_p (lhs1, rhs2)
3322 && expressions_equal_p (rhs1, lhs2)));
3325 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
3327 static int
3328 vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2)
3330 if (vp1->hashcode != vp2->hashcode)
3331 return false;
3333 if (vp1->block != vp2->block)
3335 if (EDGE_COUNT (vp1->block->preds) != EDGE_COUNT (vp2->block->preds))
3336 return false;
3338 switch (EDGE_COUNT (vp1->block->preds))
3340 case 1:
3341 /* Single-arg PHIs are just copies. */
3342 break;
3344 case 2:
3346 /* Rule out backedges into the PHI. */
3347 if (vp1->block->loop_father->header == vp1->block
3348 || vp2->block->loop_father->header == vp2->block)
3349 return false;
3351 /* If the PHI nodes do not have compatible types
3352 they are not the same. */
3353 if (!types_compatible_p (vp1->type, vp2->type))
3354 return false;
3356 basic_block idom1
3357 = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
3358 basic_block idom2
3359 = get_immediate_dominator (CDI_DOMINATORS, vp2->block);
3360 /* If the immediate dominator end in switch stmts multiple
3361 values may end up in the same PHI arg via intermediate
3362 CFG merges. */
3363 if (EDGE_COUNT (idom1->succs) != 2
3364 || EDGE_COUNT (idom2->succs) != 2)
3365 return false;
3367 /* Verify the controlling stmt is the same. */
3368 gcond *last1 = safe_dyn_cast <gcond *> (last_stmt (idom1));
3369 gcond *last2 = safe_dyn_cast <gcond *> (last_stmt (idom2));
3370 if (! last1 || ! last2)
3371 return false;
3372 bool inverted_p;
3373 if (! cond_stmts_equal_p (last1, vp1->cclhs, vp1->ccrhs,
3374 last2, vp2->cclhs, vp2->ccrhs,
3375 &inverted_p))
3376 return false;
3378 /* Get at true/false controlled edges into the PHI. */
3379 edge te1, te2, fe1, fe2;
3380 if (! extract_true_false_controlled_edges (idom1, vp1->block,
3381 &te1, &fe1)
3382 || ! extract_true_false_controlled_edges (idom2, vp2->block,
3383 &te2, &fe2))
3384 return false;
3386 /* Swap edges if the second condition is the inverted of the
3387 first. */
3388 if (inverted_p)
3389 std::swap (te2, fe2);
3391 /* ??? Handle VN_TOP specially. */
3392 if (! expressions_equal_p (vp1->phiargs[te1->dest_idx],
3393 vp2->phiargs[te2->dest_idx])
3394 || ! expressions_equal_p (vp1->phiargs[fe1->dest_idx],
3395 vp2->phiargs[fe2->dest_idx]))
3396 return false;
3398 return true;
3401 default:
3402 return false;
3406 /* If the PHI nodes do not have compatible types
3407 they are not the same. */
3408 if (!types_compatible_p (vp1->type, vp2->type))
3409 return false;
3411 /* Any phi in the same block will have it's arguments in the
3412 same edge order, because of how we store phi nodes. */
3413 for (unsigned i = 0; i < EDGE_COUNT (vp1->block->preds); ++i)
3415 tree phi1op = vp1->phiargs[i];
3416 tree phi2op = vp2->phiargs[i];
3417 if (phi1op == VN_TOP || phi2op == VN_TOP)
3418 continue;
3419 if (!expressions_equal_p (phi1op, phi2op))
3420 return false;
3423 return true;
3426 /* Lookup PHI in the current hash table, and return the resulting
3427 value number if it exists in the hash table. Return NULL_TREE if
3428 it does not exist in the hash table. */
3430 static tree
3431 vn_phi_lookup (gimple *phi, bool backedges_varying_p)
3433 vn_phi_s **slot;
3434 struct vn_phi_s *vp1;
3435 edge e;
3436 edge_iterator ei;
3438 vp1 = XALLOCAVAR (struct vn_phi_s,
3439 sizeof (struct vn_phi_s)
3440 + (gimple_phi_num_args (phi) - 1) * sizeof (tree));
3442 /* Canonicalize the SSA_NAME's to their value number. */
3443 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
3445 tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
3446 if (TREE_CODE (def) == SSA_NAME
3447 && (!backedges_varying_p || !(e->flags & EDGE_DFS_BACK)))
3448 def = SSA_VAL (def);
3449 vp1->phiargs[e->dest_idx] = def;
3451 vp1->type = TREE_TYPE (gimple_phi_result (phi));
3452 vp1->block = gimple_bb (phi);
3453 /* Extract values of the controlling condition. */
3454 vp1->cclhs = NULL_TREE;
3455 vp1->ccrhs = NULL_TREE;
3456 basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
3457 if (EDGE_COUNT (idom1->succs) == 2)
3458 if (gcond *last1 = safe_dyn_cast <gcond *> (last_stmt (idom1)))
3460 /* ??? We want to use SSA_VAL here. But possibly not
3461 allow VN_TOP. */
3462 vp1->cclhs = vn_valueize (gimple_cond_lhs (last1));
3463 vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1));
3465 vp1->hashcode = vn_phi_compute_hash (vp1);
3466 slot = valid_info->phis->find_slot_with_hash (vp1, vp1->hashcode, NO_INSERT);
3467 if (!slot)
3468 return NULL_TREE;
3469 return (*slot)->result;
3472 /* Insert PHI into the current hash table with a value number of
3473 RESULT. */
3475 static vn_phi_t
3476 vn_phi_insert (gimple *phi, tree result, bool backedges_varying_p)
3478 vn_phi_s **slot;
3479 vn_phi_t vp1 = (vn_phi_t) obstack_alloc (&vn_tables_obstack,
3480 sizeof (vn_phi_s)
3481 + ((gimple_phi_num_args (phi) - 1)
3482 * sizeof (tree)));
3483 edge e;
3484 edge_iterator ei;
3486 /* Canonicalize the SSA_NAME's to their value number. */
3487 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
3489 tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
3490 if (TREE_CODE (def) == SSA_NAME
3491 && (!backedges_varying_p || !(e->flags & EDGE_DFS_BACK)))
3492 def = SSA_VAL (def);
3493 vp1->phiargs[e->dest_idx] = def;
3495 vp1->value_id = VN_INFO (result)->value_id;
3496 vp1->type = TREE_TYPE (gimple_phi_result (phi));
3497 vp1->block = gimple_bb (phi);
3498 /* Extract values of the controlling condition. */
3499 vp1->cclhs = NULL_TREE;
3500 vp1->ccrhs = NULL_TREE;
3501 basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
3502 if (EDGE_COUNT (idom1->succs) == 2)
3503 if (gcond *last1 = safe_dyn_cast <gcond *> (last_stmt (idom1)))
3505 /* ??? We want to use SSA_VAL here. But possibly not
3506 allow VN_TOP. */
3507 vp1->cclhs = vn_valueize (gimple_cond_lhs (last1));
3508 vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1));
3510 vp1->result = result;
3511 vp1->hashcode = vn_phi_compute_hash (vp1);
3513 slot = valid_info->phis->find_slot_with_hash (vp1, vp1->hashcode, INSERT);
3514 gcc_assert (!*slot);
3516 *slot = vp1;
3517 vp1->next = last_inserted_phi;
3518 last_inserted_phi = vp1;
3519 return vp1;
3523 /* Return true if BB1 is dominated by BB2 taking into account edges
3524 that are not executable. */
3526 static bool
3527 dominated_by_p_w_unex (basic_block bb1, basic_block bb2)
3529 edge_iterator ei;
3530 edge e;
3532 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
3533 return true;
3535 /* Before iterating we'd like to know if there exists a
3536 (executable) path from bb2 to bb1 at all, if not we can
3537 directly return false. For now simply iterate once. */
3539 /* Iterate to the single executable bb1 predecessor. */
3540 if (EDGE_COUNT (bb1->preds) > 1)
3542 edge prede = NULL;
3543 FOR_EACH_EDGE (e, ei, bb1->preds)
3544 if (e->flags & EDGE_EXECUTABLE)
3546 if (prede)
3548 prede = NULL;
3549 break;
3551 prede = e;
3553 if (prede)
3555 bb1 = prede->src;
3557 /* Re-do the dominance check with changed bb1. */
3558 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
3559 return true;
3563 /* Iterate to the single executable bb2 successor. */
3564 edge succe = NULL;
3565 FOR_EACH_EDGE (e, ei, bb2->succs)
3566 if (e->flags & EDGE_EXECUTABLE)
3568 if (succe)
3570 succe = NULL;
3571 break;
3573 succe = e;
3575 if (succe)
3577 /* Verify the reached block is only reached through succe.
3578 If there is only one edge we can spare us the dominator
3579 check and iterate directly. */
3580 if (EDGE_COUNT (succe->dest->preds) > 1)
3582 FOR_EACH_EDGE (e, ei, succe->dest->preds)
3583 if (e != succe
3584 && (e->flags & EDGE_EXECUTABLE))
3586 succe = NULL;
3587 break;
3590 if (succe)
3592 bb2 = succe->dest;
3594 /* Re-do the dominance check with changed bb2. */
3595 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
3596 return true;
3600 /* We could now iterate updating bb1 / bb2. */
3601 return false;
3604 /* Set the value number of FROM to TO, return true if it has changed
3605 as a result. */
3607 static inline bool
3608 set_ssa_val_to (tree from, tree to)
3610 vn_ssa_aux_t from_info = VN_INFO (from);
3611 tree currval = from_info->valnum; // SSA_VAL (from)
3612 poly_int64 toff, coff;
3614 /* The only thing we allow as value numbers are ssa_names
3615 and invariants. So assert that here. We don't allow VN_TOP
3616 as visiting a stmt should produce a value-number other than
3617 that.
3618 ??? Still VN_TOP can happen for unreachable code, so force
3619 it to varying in that case. Not all code is prepared to
3620 get VN_TOP on valueization. */
3621 if (to == VN_TOP)
3623 /* ??? When iterating and visiting PHI <undef, backedge-value>
3624 for the first time we rightfully get VN_TOP and we need to
3625 preserve that to optimize for example gcc.dg/tree-ssa/ssa-sccvn-2.c.
3626 With SCCVN we were simply lucky we iterated the other PHI
3627 cycles first and thus visited the backedge-value DEF. */
3628 if (currval == VN_TOP)
3629 goto set_and_exit;
3630 if (dump_file && (dump_flags & TDF_DETAILS))
3631 fprintf (dump_file, "Forcing value number to varying on "
3632 "receiving VN_TOP\n");
3633 to = from;
3636 gcc_checking_assert (to != NULL_TREE
3637 && ((TREE_CODE (to) == SSA_NAME
3638 && (to == from || SSA_VAL (to) == to))
3639 || is_gimple_min_invariant (to)));
3641 if (from != to)
3643 if (currval == from)
3645 if (dump_file && (dump_flags & TDF_DETAILS))
3647 fprintf (dump_file, "Not changing value number of ");
3648 print_generic_expr (dump_file, from);
3649 fprintf (dump_file, " from VARYING to ");
3650 print_generic_expr (dump_file, to);
3651 fprintf (dump_file, "\n");
3653 return false;
3655 else if (currval != VN_TOP
3656 && ! is_gimple_min_invariant (currval)
3657 && ! ssa_undefined_value_p (currval, false)
3658 && is_gimple_min_invariant (to))
3660 if (dump_file && (dump_flags & TDF_DETAILS))
3662 fprintf (dump_file, "Forcing VARYING instead of changing "
3663 "value number of ");
3664 print_generic_expr (dump_file, from);
3665 fprintf (dump_file, " from ");
3666 print_generic_expr (dump_file, currval);
3667 fprintf (dump_file, " (non-constant) to ");
3668 print_generic_expr (dump_file, to);
3669 fprintf (dump_file, " (constant)\n");
3671 to = from;
3673 else if (TREE_CODE (to) == SSA_NAME
3674 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
3675 to = from;
3678 set_and_exit:
3679 if (dump_file && (dump_flags & TDF_DETAILS))
3681 fprintf (dump_file, "Setting value number of ");
3682 print_generic_expr (dump_file, from);
3683 fprintf (dump_file, " to ");
3684 print_generic_expr (dump_file, to);
3687 if (currval != to
3688 && !operand_equal_p (currval, to, 0)
3689 /* Different undefined SSA names are not actually different. See
3690 PR82320 for a testcase were we'd otherwise not terminate iteration. */
3691 && !(TREE_CODE (currval) == SSA_NAME
3692 && TREE_CODE (to) == SSA_NAME
3693 && ssa_undefined_value_p (currval, false)
3694 && ssa_undefined_value_p (to, false))
3695 /* ??? For addresses involving volatile objects or types operand_equal_p
3696 does not reliably detect ADDR_EXPRs as equal. We know we are only
3697 getting invariant gimple addresses here, so can use
3698 get_addr_base_and_unit_offset to do this comparison. */
3699 && !(TREE_CODE (currval) == ADDR_EXPR
3700 && TREE_CODE (to) == ADDR_EXPR
3701 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval, 0), &coff)
3702 == get_addr_base_and_unit_offset (TREE_OPERAND (to, 0), &toff))
3703 && known_eq (coff, toff)))
3705 if (dump_file && (dump_flags & TDF_DETAILS))
3706 fprintf (dump_file, " (changed)\n");
3707 from_info->valnum = to;
3708 return true;
3710 if (dump_file && (dump_flags & TDF_DETAILS))
3711 fprintf (dump_file, "\n");
3712 return false;
3715 /* Set all definitions in STMT to value number to themselves.
3716 Return true if a value number changed. */
3718 static bool
3719 defs_to_varying (gimple *stmt)
3721 bool changed = false;
3722 ssa_op_iter iter;
3723 def_operand_p defp;
3725 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
3727 tree def = DEF_FROM_PTR (defp);
3728 changed |= set_ssa_val_to (def, def);
3730 return changed;
3733 /* Visit a copy between LHS and RHS, return true if the value number
3734 changed. */
3736 static bool
3737 visit_copy (tree lhs, tree rhs)
3739 /* Valueize. */
3740 rhs = SSA_VAL (rhs);
3742 return set_ssa_val_to (lhs, rhs);
3745 /* Lookup a value for OP in type WIDE_TYPE where the value in type of OP
3746 is the same. */
3748 static tree
3749 valueized_wider_op (tree wide_type, tree op)
3751 if (TREE_CODE (op) == SSA_NAME)
3752 op = vn_valueize (op);
3754 /* Either we have the op widened available. */
3755 tree ops[3] = {};
3756 ops[0] = op;
3757 tree tem = vn_nary_op_lookup_pieces (1, NOP_EXPR,
3758 wide_type, ops, NULL);
3759 if (tem)
3760 return tem;
3762 /* Or the op is truncated from some existing value. */
3763 if (TREE_CODE (op) == SSA_NAME)
3765 gimple *def = SSA_NAME_DEF_STMT (op);
3766 if (is_gimple_assign (def)
3767 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
3769 tem = gimple_assign_rhs1 (def);
3770 if (useless_type_conversion_p (wide_type, TREE_TYPE (tem)))
3772 if (TREE_CODE (tem) == SSA_NAME)
3773 tem = vn_valueize (tem);
3774 return tem;
3779 /* For constants simply extend it. */
3780 if (TREE_CODE (op) == INTEGER_CST)
3781 return wide_int_to_tree (wide_type, wi::to_wide (op));
3783 return NULL_TREE;
3786 /* Visit a nary operator RHS, value number it, and return true if the
3787 value number of LHS has changed as a result. */
3789 static bool
3790 visit_nary_op (tree lhs, gassign *stmt)
3792 vn_nary_op_t vnresult;
3793 tree result = vn_nary_op_lookup_stmt (stmt, &vnresult);
3794 if (! result && vnresult)
3795 result = vn_nary_op_get_predicated_value (vnresult, gimple_bb (stmt));
3796 if (result)
3797 return set_ssa_val_to (lhs, result);
3799 /* Do some special pattern matching for redundancies of operations
3800 in different types. */
3801 enum tree_code code = gimple_assign_rhs_code (stmt);
3802 tree type = TREE_TYPE (lhs);
3803 tree rhs1 = gimple_assign_rhs1 (stmt);
3804 switch (code)
3806 CASE_CONVERT:
3807 /* Match arithmetic done in a different type where we can easily
3808 substitute the result from some earlier sign-changed or widened
3809 operation. */
3810 if (INTEGRAL_TYPE_P (type)
3811 && TREE_CODE (rhs1) == SSA_NAME
3812 /* We only handle sign-changes or zero-extension -> & mask. */
3813 && ((TYPE_UNSIGNED (TREE_TYPE (rhs1))
3814 && TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (rhs1)))
3815 || TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (rhs1))))
3817 gassign *def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (rhs1));
3818 if (def
3819 && (gimple_assign_rhs_code (def) == PLUS_EXPR
3820 || gimple_assign_rhs_code (def) == MINUS_EXPR
3821 || gimple_assign_rhs_code (def) == MULT_EXPR))
3823 tree ops[3] = {};
3824 /* Either we have the op widened available. */
3825 ops[0] = valueized_wider_op (type,
3826 gimple_assign_rhs1 (def));
3827 if (ops[0])
3828 ops[1] = valueized_wider_op (type,
3829 gimple_assign_rhs2 (def));
3830 if (ops[0] && ops[1])
3832 ops[0] = vn_nary_op_lookup_pieces
3833 (2, gimple_assign_rhs_code (def), type, ops, NULL);
3834 /* We have wider operation available. */
3835 if (ops[0])
3837 unsigned lhs_prec = TYPE_PRECISION (type);
3838 unsigned rhs_prec = TYPE_PRECISION (TREE_TYPE (rhs1));
3839 if (lhs_prec == rhs_prec)
3841 gimple_match_op match_op (gimple_match_cond::UNCOND,
3842 NOP_EXPR, type, ops[0]);
3843 result = vn_nary_build_or_lookup (&match_op);
3844 if (result)
3846 bool changed = set_ssa_val_to (lhs, result);
3847 vn_nary_op_insert_stmt (stmt, result);
3848 return changed;
3851 else
3853 tree mask = wide_int_to_tree
3854 (type, wi::mask (rhs_prec, false, lhs_prec));
3855 gimple_match_op match_op (gimple_match_cond::UNCOND,
3856 BIT_AND_EXPR,
3857 TREE_TYPE (lhs),
3858 ops[0], mask);
3859 result = vn_nary_build_or_lookup (&match_op);
3860 if (result)
3862 bool changed = set_ssa_val_to (lhs, result);
3863 vn_nary_op_insert_stmt (stmt, result);
3864 return changed;
3871 default:;
3874 bool changed = set_ssa_val_to (lhs, lhs);
3875 vn_nary_op_insert_stmt (stmt, lhs);
3876 return changed;
3879 /* Visit a call STMT storing into LHS. Return true if the value number
3880 of the LHS has changed as a result. */
3882 static bool
3883 visit_reference_op_call (tree lhs, gcall *stmt)
3885 bool changed = false;
3886 struct vn_reference_s vr1;
3887 vn_reference_t vnresult = NULL;
3888 tree vdef = gimple_vdef (stmt);
3890 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
3891 if (lhs && TREE_CODE (lhs) != SSA_NAME)
3892 lhs = NULL_TREE;
3894 vn_reference_lookup_call (stmt, &vnresult, &vr1);
3895 if (vnresult)
3897 if (vnresult->result_vdef && vdef)
3898 changed |= set_ssa_val_to (vdef, vnresult->result_vdef);
3899 else if (vdef)
3900 /* If the call was discovered to be pure or const reflect
3901 that as far as possible. */
3902 changed |= set_ssa_val_to (vdef, vuse_ssa_val (gimple_vuse (stmt)));
3904 if (!vnresult->result && lhs)
3905 vnresult->result = lhs;
3907 if (vnresult->result && lhs)
3908 changed |= set_ssa_val_to (lhs, vnresult->result);
3910 else
3912 vn_reference_t vr2;
3913 vn_reference_s **slot;
3914 tree vdef_val = vdef;
3915 if (vdef)
3917 /* If we value numbered an indirect functions function to
3918 one not clobbering memory value number its VDEF to its
3919 VUSE. */
3920 tree fn = gimple_call_fn (stmt);
3921 if (fn && TREE_CODE (fn) == SSA_NAME)
3923 fn = SSA_VAL (fn);
3924 if (TREE_CODE (fn) == ADDR_EXPR
3925 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
3926 && (flags_from_decl_or_type (TREE_OPERAND (fn, 0))
3927 & (ECF_CONST | ECF_PURE)))
3928 vdef_val = vuse_ssa_val (gimple_vuse (stmt));
3930 changed |= set_ssa_val_to (vdef, vdef_val);
3932 if (lhs)
3933 changed |= set_ssa_val_to (lhs, lhs);
3934 vr2 = XOBNEW (&vn_tables_obstack, vn_reference_s);
3935 vr2->vuse = vr1.vuse;
3936 /* As we are not walking the virtual operand chain we know the
3937 shared_lookup_references are still original so we can re-use
3938 them here. */
3939 vr2->operands = vr1.operands.copy ();
3940 vr2->type = vr1.type;
3941 vr2->set = vr1.set;
3942 vr2->hashcode = vr1.hashcode;
3943 vr2->result = lhs;
3944 vr2->result_vdef = vdef_val;
3945 slot = valid_info->references->find_slot_with_hash (vr2, vr2->hashcode,
3946 INSERT);
3947 gcc_assert (!*slot);
3948 *slot = vr2;
3949 vr2->next = last_inserted_ref;
3950 last_inserted_ref = vr2;
3953 return changed;
3956 /* Visit a load from a reference operator RHS, part of STMT, value number it,
3957 and return true if the value number of the LHS has changed as a result. */
3959 static bool
3960 visit_reference_op_load (tree lhs, tree op, gimple *stmt)
3962 bool changed = false;
3963 tree last_vuse;
3964 tree result;
3966 last_vuse = gimple_vuse (stmt);
3967 last_vuse_ptr = &last_vuse;
3968 result = vn_reference_lookup (op, gimple_vuse (stmt),
3969 default_vn_walk_kind, NULL, true);
3970 last_vuse_ptr = NULL;
3972 /* We handle type-punning through unions by value-numbering based
3973 on offset and size of the access. Be prepared to handle a
3974 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
3975 if (result
3976 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
3978 /* We will be setting the value number of lhs to the value number
3979 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
3980 So first simplify and lookup this expression to see if it
3981 is already available. */
3982 gimple_match_op res_op (gimple_match_cond::UNCOND,
3983 VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
3984 result = vn_nary_build_or_lookup (&res_op);
3985 /* When building the conversion fails avoid inserting the reference
3986 again. */
3987 if (!result)
3988 return set_ssa_val_to (lhs, lhs);
3991 if (result)
3992 changed = set_ssa_val_to (lhs, result);
3993 else
3995 changed = set_ssa_val_to (lhs, lhs);
3996 vn_reference_insert (op, lhs, last_vuse, NULL_TREE);
3999 return changed;
4003 /* Visit a store to a reference operator LHS, part of STMT, value number it,
4004 and return true if the value number of the LHS has changed as a result. */
4006 static bool
4007 visit_reference_op_store (tree lhs, tree op, gimple *stmt)
4009 bool changed = false;
4010 vn_reference_t vnresult = NULL;
4011 tree assign;
4012 bool resultsame = false;
4013 tree vuse = gimple_vuse (stmt);
4014 tree vdef = gimple_vdef (stmt);
4016 if (TREE_CODE (op) == SSA_NAME)
4017 op = SSA_VAL (op);
4019 /* First we want to lookup using the *vuses* from the store and see
4020 if there the last store to this location with the same address
4021 had the same value.
4023 The vuses represent the memory state before the store. If the
4024 memory state, address, and value of the store is the same as the
4025 last store to this location, then this store will produce the
4026 same memory state as that store.
4028 In this case the vdef versions for this store are value numbered to those
4029 vuse versions, since they represent the same memory state after
4030 this store.
4032 Otherwise, the vdefs for the store are used when inserting into
4033 the table, since the store generates a new memory state. */
4035 vn_reference_lookup (lhs, vuse, VN_NOWALK, &vnresult, false);
4036 if (vnresult
4037 && vnresult->result)
4039 tree result = vnresult->result;
4040 gcc_checking_assert (TREE_CODE (result) != SSA_NAME
4041 || result == SSA_VAL (result));
4042 resultsame = expressions_equal_p (result, op);
4043 if (resultsame)
4045 /* If the TBAA state isn't compatible for downstream reads
4046 we cannot value-number the VDEFs the same. */
4047 alias_set_type set = get_alias_set (lhs);
4048 if (vnresult->set != set
4049 && ! alias_set_subset_of (set, vnresult->set))
4050 resultsame = false;
4054 if (!resultsame)
4056 /* Only perform the following when being called from PRE
4057 which embeds tail merging. */
4058 if (default_vn_walk_kind == VN_WALK)
4060 assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
4061 vn_reference_lookup (assign, vuse, VN_NOWALK, &vnresult, false);
4062 if (vnresult)
4064 VN_INFO (vdef)->visited = true;
4065 return set_ssa_val_to (vdef, vnresult->result_vdef);
4069 if (dump_file && (dump_flags & TDF_DETAILS))
4071 fprintf (dump_file, "No store match\n");
4072 fprintf (dump_file, "Value numbering store ");
4073 print_generic_expr (dump_file, lhs);
4074 fprintf (dump_file, " to ");
4075 print_generic_expr (dump_file, op);
4076 fprintf (dump_file, "\n");
4078 /* Have to set value numbers before insert, since insert is
4079 going to valueize the references in-place. */
4080 if (vdef)
4081 changed |= set_ssa_val_to (vdef, vdef);
4083 /* Do not insert structure copies into the tables. */
4084 if (is_gimple_min_invariant (op)
4085 || is_gimple_reg (op))
4086 vn_reference_insert (lhs, op, vdef, NULL);
4088 /* Only perform the following when being called from PRE
4089 which embeds tail merging. */
4090 if (default_vn_walk_kind == VN_WALK)
4092 assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
4093 vn_reference_insert (assign, lhs, vuse, vdef);
4096 else
4098 /* We had a match, so value number the vdef to have the value
4099 number of the vuse it came from. */
4101 if (dump_file && (dump_flags & TDF_DETAILS))
4102 fprintf (dump_file, "Store matched earlier value, "
4103 "value numbering store vdefs to matching vuses.\n");
4105 changed |= set_ssa_val_to (vdef, SSA_VAL (vuse));
4108 return changed;
4111 /* Visit and value number PHI, return true if the value number
4112 changed. When BACKEDGES_VARYING_P is true then assume all
4113 backedge values are varying. When INSERTED is not NULL then
4114 this is just a ahead query for a possible iteration, set INSERTED
4115 to true if we'd insert into the hashtable. */
4117 static bool
4118 visit_phi (gimple *phi, bool *inserted, bool backedges_varying_p)
4120 tree result, sameval = VN_TOP, seen_undef = NULL_TREE;
4121 tree backedge_val = NULL_TREE;
4122 bool seen_non_backedge = false;
4123 tree sameval_base = NULL_TREE;
4124 poly_int64 soff, doff;
4125 unsigned n_executable = 0;
4126 edge_iterator ei;
4127 edge e;
4129 /* TODO: We could check for this in initialization, and replace this
4130 with a gcc_assert. */
4131 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
4132 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
4134 /* We track whether a PHI was CSEd to to avoid excessive iterations
4135 that would be necessary only because the PHI changed arguments
4136 but not value. */
4137 if (!inserted)
4138 gimple_set_plf (phi, GF_PLF_1, false);
4140 /* See if all non-TOP arguments have the same value. TOP is
4141 equivalent to everything, so we can ignore it. */
4142 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
4143 if (e->flags & EDGE_EXECUTABLE)
4145 tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4147 ++n_executable;
4148 if (TREE_CODE (def) == SSA_NAME)
4150 if (!backedges_varying_p || !(e->flags & EDGE_DFS_BACK))
4151 def = SSA_VAL (def);
4152 if (e->flags & EDGE_DFS_BACK)
4153 backedge_val = def;
4155 if (!(e->flags & EDGE_DFS_BACK))
4156 seen_non_backedge = true;
4157 if (def == VN_TOP)
4159 /* Ignore undefined defs for sameval but record one. */
4160 else if (TREE_CODE (def) == SSA_NAME
4161 && ! virtual_operand_p (def)
4162 && ssa_undefined_value_p (def, false))
4163 seen_undef = def;
4164 else if (sameval == VN_TOP)
4165 sameval = def;
4166 else if (!expressions_equal_p (def, sameval))
4168 /* We know we're arriving only with invariant addresses here,
4169 try harder comparing them. We can do some caching here
4170 which we cannot do in expressions_equal_p. */
4171 if (TREE_CODE (def) == ADDR_EXPR
4172 && TREE_CODE (sameval) == ADDR_EXPR
4173 && sameval_base != (void *)-1)
4175 if (!sameval_base)
4176 sameval_base = get_addr_base_and_unit_offset
4177 (TREE_OPERAND (sameval, 0), &soff);
4178 if (!sameval_base)
4179 sameval_base = (tree)(void *)-1;
4180 else if ((get_addr_base_and_unit_offset
4181 (TREE_OPERAND (def, 0), &doff) == sameval_base)
4182 && known_eq (soff, doff))
4183 continue;
4185 sameval = NULL_TREE;
4186 break;
4190 /* If the value we want to use is flowing over the backedge and we
4191 should take it as VARYING but it has a non-VARYING value drop to
4192 VARYING.
4193 If we value-number a virtual operand never value-number to the
4194 value from the backedge as that confuses the alias-walking code.
4195 See gcc.dg/torture/pr87176.c. If the value is the same on a
4196 non-backedge everything is OK though. */
4197 bool visited_p;
4198 if ((backedge_val
4199 && !seen_non_backedge
4200 && TREE_CODE (backedge_val) == SSA_NAME
4201 && sameval == backedge_val
4202 && (SSA_NAME_IS_VIRTUAL_OPERAND (backedge_val)
4203 || SSA_VAL (backedge_val) != backedge_val))
4204 /* Do not value-number a virtual operand to sth not visited though
4205 given that allows us to escape a region in alias walking. */
4206 || (sameval
4207 && TREE_CODE (sameval) == SSA_NAME
4208 && SSA_NAME_IS_VIRTUAL_OPERAND (sameval)
4209 && (SSA_VAL (sameval, &visited_p), !visited_p)))
4210 /* Note this just drops to VARYING without inserting the PHI into
4211 the hashes. */
4212 result = PHI_RESULT (phi);
4213 /* If none of the edges was executable keep the value-number at VN_TOP,
4214 if only a single edge is exectuable use its value. */
4215 else if (n_executable <= 1)
4216 result = seen_undef ? seen_undef : sameval;
4217 /* If we saw only undefined values and VN_TOP use one of the
4218 undefined values. */
4219 else if (sameval == VN_TOP)
4220 result = seen_undef ? seen_undef : sameval;
4221 /* First see if it is equivalent to a phi node in this block. We prefer
4222 this as it allows IV elimination - see PRs 66502 and 67167. */
4223 else if ((result = vn_phi_lookup (phi, backedges_varying_p)))
4225 if (!inserted
4226 && TREE_CODE (result) == SSA_NAME
4227 && gimple_code (SSA_NAME_DEF_STMT (result)) == GIMPLE_PHI)
4229 gimple_set_plf (SSA_NAME_DEF_STMT (result), GF_PLF_1, true);
4230 if (dump_file && (dump_flags & TDF_DETAILS))
4232 fprintf (dump_file, "Marking CSEd to PHI node ");
4233 print_gimple_expr (dump_file, SSA_NAME_DEF_STMT (result),
4234 0, TDF_SLIM);
4235 fprintf (dump_file, "\n");
4239 /* If all values are the same use that, unless we've seen undefined
4240 values as well and the value isn't constant.
4241 CCP/copyprop have the same restriction to not remove uninit warnings. */
4242 else if (sameval
4243 && (! seen_undef || is_gimple_min_invariant (sameval)))
4244 result = sameval;
4245 else
4247 result = PHI_RESULT (phi);
4248 /* Only insert PHIs that are varying, for constant value numbers
4249 we mess up equivalences otherwise as we are only comparing
4250 the immediate controlling predicates. */
4251 vn_phi_insert (phi, result, backedges_varying_p);
4252 if (inserted)
4253 *inserted = true;
4256 return set_ssa_val_to (PHI_RESULT (phi), result);
4259 /* Try to simplify RHS using equivalences and constant folding. */
4261 static tree
4262 try_to_simplify (gassign *stmt)
4264 enum tree_code code = gimple_assign_rhs_code (stmt);
4265 tree tem;
4267 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
4268 in this case, there is no point in doing extra work. */
4269 if (code == SSA_NAME)
4270 return NULL_TREE;
4272 /* First try constant folding based on our current lattice. */
4273 mprts_hook = vn_lookup_simplify_result;
4274 tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize, vn_valueize);
4275 mprts_hook = NULL;
4276 if (tem
4277 && (TREE_CODE (tem) == SSA_NAME
4278 || is_gimple_min_invariant (tem)))
4279 return tem;
4281 return NULL_TREE;
4284 /* Visit and value number STMT, return true if the value number
4285 changed. */
4287 static bool
4288 visit_stmt (gimple *stmt, bool backedges_varying_p = false)
4290 bool changed = false;
4292 if (dump_file && (dump_flags & TDF_DETAILS))
4294 fprintf (dump_file, "Value numbering stmt = ");
4295 print_gimple_stmt (dump_file, stmt, 0);
4298 if (gimple_code (stmt) == GIMPLE_PHI)
4299 changed = visit_phi (stmt, NULL, backedges_varying_p);
4300 else if (gimple_has_volatile_ops (stmt))
4301 changed = defs_to_varying (stmt);
4302 else if (gassign *ass = dyn_cast <gassign *> (stmt))
4304 enum tree_code code = gimple_assign_rhs_code (ass);
4305 tree lhs = gimple_assign_lhs (ass);
4306 tree rhs1 = gimple_assign_rhs1 (ass);
4307 tree simplified;
4309 /* Shortcut for copies. Simplifying copies is pointless,
4310 since we copy the expression and value they represent. */
4311 if (code == SSA_NAME
4312 && TREE_CODE (lhs) == SSA_NAME)
4314 changed = visit_copy (lhs, rhs1);
4315 goto done;
4317 simplified = try_to_simplify (ass);
4318 if (simplified)
4320 if (dump_file && (dump_flags & TDF_DETAILS))
4322 fprintf (dump_file, "RHS ");
4323 print_gimple_expr (dump_file, ass, 0);
4324 fprintf (dump_file, " simplified to ");
4325 print_generic_expr (dump_file, simplified);
4326 fprintf (dump_file, "\n");
4329 /* Setting value numbers to constants will occasionally
4330 screw up phi congruence because constants are not
4331 uniquely associated with a single ssa name that can be
4332 looked up. */
4333 if (simplified
4334 && is_gimple_min_invariant (simplified)
4335 && TREE_CODE (lhs) == SSA_NAME)
4337 changed = set_ssa_val_to (lhs, simplified);
4338 goto done;
4340 else if (simplified
4341 && TREE_CODE (simplified) == SSA_NAME
4342 && TREE_CODE (lhs) == SSA_NAME)
4344 changed = visit_copy (lhs, simplified);
4345 goto done;
4348 if ((TREE_CODE (lhs) == SSA_NAME
4349 /* We can substitute SSA_NAMEs that are live over
4350 abnormal edges with their constant value. */
4351 && !(gimple_assign_copy_p (ass)
4352 && is_gimple_min_invariant (rhs1))
4353 && !(simplified
4354 && is_gimple_min_invariant (simplified))
4355 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
4356 /* Stores or copies from SSA_NAMEs that are live over
4357 abnormal edges are a problem. */
4358 || (code == SSA_NAME
4359 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
4360 changed = defs_to_varying (ass);
4361 else if (REFERENCE_CLASS_P (lhs)
4362 || DECL_P (lhs))
4363 changed = visit_reference_op_store (lhs, rhs1, ass);
4364 else if (TREE_CODE (lhs) == SSA_NAME)
4366 if ((gimple_assign_copy_p (ass)
4367 && is_gimple_min_invariant (rhs1))
4368 || (simplified
4369 && is_gimple_min_invariant (simplified)))
4371 if (simplified)
4372 changed = set_ssa_val_to (lhs, simplified);
4373 else
4374 changed = set_ssa_val_to (lhs, rhs1);
4376 else
4378 /* Visit the original statement. */
4379 switch (vn_get_stmt_kind (ass))
4381 case VN_NARY:
4382 changed = visit_nary_op (lhs, ass);
4383 break;
4384 case VN_REFERENCE:
4385 changed = visit_reference_op_load (lhs, rhs1, ass);
4386 break;
4387 default:
4388 changed = defs_to_varying (ass);
4389 break;
4393 else
4394 changed = defs_to_varying (ass);
4396 else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
4398 tree lhs = gimple_call_lhs (call_stmt);
4399 if (lhs && TREE_CODE (lhs) == SSA_NAME)
4401 /* Try constant folding based on our current lattice. */
4402 tree simplified = gimple_fold_stmt_to_constant_1 (call_stmt,
4403 vn_valueize);
4404 if (simplified)
4406 if (dump_file && (dump_flags & TDF_DETAILS))
4408 fprintf (dump_file, "call ");
4409 print_gimple_expr (dump_file, call_stmt, 0);
4410 fprintf (dump_file, " simplified to ");
4411 print_generic_expr (dump_file, simplified);
4412 fprintf (dump_file, "\n");
4415 /* Setting value numbers to constants will occasionally
4416 screw up phi congruence because constants are not
4417 uniquely associated with a single ssa name that can be
4418 looked up. */
4419 if (simplified
4420 && is_gimple_min_invariant (simplified))
4422 changed = set_ssa_val_to (lhs, simplified);
4423 if (gimple_vdef (call_stmt))
4424 changed |= set_ssa_val_to (gimple_vdef (call_stmt),
4425 SSA_VAL (gimple_vuse (call_stmt)));
4426 goto done;
4428 else if (simplified
4429 && TREE_CODE (simplified) == SSA_NAME)
4431 changed = visit_copy (lhs, simplified);
4432 if (gimple_vdef (call_stmt))
4433 changed |= set_ssa_val_to (gimple_vdef (call_stmt),
4434 SSA_VAL (gimple_vuse (call_stmt)));
4435 goto done;
4437 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
4439 changed = defs_to_varying (call_stmt);
4440 goto done;
4444 /* Pick up flags from a devirtualization target. */
4445 tree fn = gimple_call_fn (stmt);
4446 int extra_fnflags = 0;
4447 if (fn && TREE_CODE (fn) == SSA_NAME)
4449 fn = SSA_VAL (fn);
4450 if (TREE_CODE (fn) == ADDR_EXPR
4451 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
4452 extra_fnflags = flags_from_decl_or_type (TREE_OPERAND (fn, 0));
4454 if (!gimple_call_internal_p (call_stmt)
4455 && (/* Calls to the same function with the same vuse
4456 and the same operands do not necessarily return the same
4457 value, unless they're pure or const. */
4458 ((gimple_call_flags (call_stmt) | extra_fnflags)
4459 & (ECF_PURE | ECF_CONST))
4460 /* If calls have a vdef, subsequent calls won't have
4461 the same incoming vuse. So, if 2 calls with vdef have the
4462 same vuse, we know they're not subsequent.
4463 We can value number 2 calls to the same function with the
4464 same vuse and the same operands which are not subsequent
4465 the same, because there is no code in the program that can
4466 compare the 2 values... */
4467 || (gimple_vdef (call_stmt)
4468 /* ... unless the call returns a pointer which does
4469 not alias with anything else. In which case the
4470 information that the values are distinct are encoded
4471 in the IL. */
4472 && !(gimple_call_return_flags (call_stmt) & ERF_NOALIAS)
4473 /* Only perform the following when being called from PRE
4474 which embeds tail merging. */
4475 && default_vn_walk_kind == VN_WALK)))
4476 changed = visit_reference_op_call (lhs, call_stmt);
4477 else
4478 changed = defs_to_varying (call_stmt);
4480 else
4481 changed = defs_to_varying (stmt);
4482 done:
4483 return changed;
4487 /* Allocate a value number table. */
4489 static void
4490 allocate_vn_table (vn_tables_t table, unsigned size)
4492 table->phis = new vn_phi_table_type (size);
4493 table->nary = new vn_nary_op_table_type (size);
4494 table->references = new vn_reference_table_type (size);
4497 /* Free a value number table. */
4499 static void
4500 free_vn_table (vn_tables_t table)
4502 /* Walk over elements and release vectors. */
4503 vn_reference_iterator_type hir;
4504 vn_reference_t vr;
4505 FOR_EACH_HASH_TABLE_ELEMENT (*table->references, vr, vn_reference_t, hir)
4506 vr->operands.release ();
4507 delete table->phis;
4508 table->phis = NULL;
4509 delete table->nary;
4510 table->nary = NULL;
4511 delete table->references;
4512 table->references = NULL;
4515 /* Set *ID according to RESULT. */
4517 static void
4518 set_value_id_for_result (tree result, unsigned int *id)
4520 if (result && TREE_CODE (result) == SSA_NAME)
4521 *id = VN_INFO (result)->value_id;
4522 else if (result && is_gimple_min_invariant (result))
4523 *id = get_or_alloc_constant_value_id (result);
4524 else
4525 *id = get_next_value_id ();
4528 /* Set the value ids in the valid hash tables. */
4530 static void
4531 set_hashtable_value_ids (void)
4533 vn_nary_op_iterator_type hin;
4534 vn_phi_iterator_type hip;
4535 vn_reference_iterator_type hir;
4536 vn_nary_op_t vno;
4537 vn_reference_t vr;
4538 vn_phi_t vp;
4540 /* Now set the value ids of the things we had put in the hash
4541 table. */
4543 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->nary, vno, vn_nary_op_t, hin)
4544 if (! vno->predicated_values)
4545 set_value_id_for_result (vno->u.result, &vno->value_id);
4547 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->phis, vp, vn_phi_t, hip)
4548 set_value_id_for_result (vp->result, &vp->value_id);
4550 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->references, vr, vn_reference_t,
4551 hir)
4552 set_value_id_for_result (vr->result, &vr->value_id);
4555 /* Return the maximum value id we have ever seen. */
4557 unsigned int
4558 get_max_value_id (void)
4560 return next_value_id;
4563 /* Return the next unique value id. */
4565 unsigned int
4566 get_next_value_id (void)
4568 return next_value_id++;
4572 /* Compare two expressions E1 and E2 and return true if they are equal. */
4574 bool
4575 expressions_equal_p (tree e1, tree e2)
4577 /* The obvious case. */
4578 if (e1 == e2)
4579 return true;
4581 /* If either one is VN_TOP consider them equal. */
4582 if (e1 == VN_TOP || e2 == VN_TOP)
4583 return true;
4585 /* If only one of them is null, they cannot be equal. */
4586 if (!e1 || !e2)
4587 return false;
4589 /* Now perform the actual comparison. */
4590 if (TREE_CODE (e1) == TREE_CODE (e2)
4591 && operand_equal_p (e1, e2, OEP_PURE_SAME))
4592 return true;
4594 return false;
4598 /* Return true if the nary operation NARY may trap. This is a copy
4599 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4601 bool
4602 vn_nary_may_trap (vn_nary_op_t nary)
4604 tree type;
4605 tree rhs2 = NULL_TREE;
4606 bool honor_nans = false;
4607 bool honor_snans = false;
4608 bool fp_operation = false;
4609 bool honor_trapv = false;
4610 bool handled, ret;
4611 unsigned i;
4613 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
4614 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
4615 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
4617 type = nary->type;
4618 fp_operation = FLOAT_TYPE_P (type);
4619 if (fp_operation)
4621 honor_nans = flag_trapping_math && !flag_finite_math_only;
4622 honor_snans = flag_signaling_nans != 0;
4624 else if (INTEGRAL_TYPE_P (type)
4625 && TYPE_OVERFLOW_TRAPS (type))
4626 honor_trapv = true;
4628 if (nary->length >= 2)
4629 rhs2 = nary->op[1];
4630 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
4631 honor_trapv,
4632 honor_nans, honor_snans, rhs2,
4633 &handled);
4634 if (handled
4635 && ret)
4636 return true;
4638 for (i = 0; i < nary->length; ++i)
4639 if (tree_could_trap_p (nary->op[i]))
4640 return true;
4642 return false;
4646 class eliminate_dom_walker : public dom_walker
4648 public:
4649 eliminate_dom_walker (cdi_direction, bitmap);
4650 ~eliminate_dom_walker ();
4652 virtual edge before_dom_children (basic_block);
4653 virtual void after_dom_children (basic_block);
4655 virtual tree eliminate_avail (basic_block, tree op);
4656 virtual void eliminate_push_avail (basic_block, tree op);
4657 tree eliminate_insert (basic_block, gimple_stmt_iterator *gsi, tree val);
4659 void eliminate_stmt (basic_block, gimple_stmt_iterator *);
4661 unsigned eliminate_cleanup (bool region_p = false);
4663 bool do_pre;
4664 unsigned int el_todo;
4665 unsigned int eliminations;
4666 unsigned int insertions;
4668 /* SSA names that had their defs inserted by PRE if do_pre. */
4669 bitmap inserted_exprs;
4671 /* Blocks with statements that have had their EH properties changed. */
4672 bitmap need_eh_cleanup;
4674 /* Blocks with statements that have had their AB properties changed. */
4675 bitmap need_ab_cleanup;
4677 /* Local state for the eliminate domwalk. */
4678 auto_vec<gimple *> to_remove;
4679 auto_vec<gimple *> to_fixup;
4680 auto_vec<tree> avail;
4681 auto_vec<tree> avail_stack;
4684 eliminate_dom_walker::eliminate_dom_walker (cdi_direction direction,
4685 bitmap inserted_exprs_)
4686 : dom_walker (direction), do_pre (inserted_exprs_ != NULL),
4687 el_todo (0), eliminations (0), insertions (0),
4688 inserted_exprs (inserted_exprs_)
4690 need_eh_cleanup = BITMAP_ALLOC (NULL);
4691 need_ab_cleanup = BITMAP_ALLOC (NULL);
4694 eliminate_dom_walker::~eliminate_dom_walker ()
4696 BITMAP_FREE (need_eh_cleanup);
4697 BITMAP_FREE (need_ab_cleanup);
4700 /* Return a leader for OP that is available at the current point of the
4701 eliminate domwalk. */
4703 tree
4704 eliminate_dom_walker::eliminate_avail (basic_block, tree op)
4706 tree valnum = VN_INFO (op)->valnum;
4707 if (TREE_CODE (valnum) == SSA_NAME)
4709 if (SSA_NAME_IS_DEFAULT_DEF (valnum))
4710 return valnum;
4711 if (avail.length () > SSA_NAME_VERSION (valnum))
4712 return avail[SSA_NAME_VERSION (valnum)];
4714 else if (is_gimple_min_invariant (valnum))
4715 return valnum;
4716 return NULL_TREE;
4719 /* At the current point of the eliminate domwalk make OP available. */
4721 void
4722 eliminate_dom_walker::eliminate_push_avail (basic_block, tree op)
4724 tree valnum = VN_INFO (op)->valnum;
4725 if (TREE_CODE (valnum) == SSA_NAME)
4727 if (avail.length () <= SSA_NAME_VERSION (valnum))
4728 avail.safe_grow_cleared (SSA_NAME_VERSION (valnum) + 1);
4729 tree pushop = op;
4730 if (avail[SSA_NAME_VERSION (valnum)])
4731 pushop = avail[SSA_NAME_VERSION (valnum)];
4732 avail_stack.safe_push (pushop);
4733 avail[SSA_NAME_VERSION (valnum)] = op;
4737 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
4738 the leader for the expression if insertion was successful. */
4740 tree
4741 eliminate_dom_walker::eliminate_insert (basic_block bb,
4742 gimple_stmt_iterator *gsi, tree val)
4744 /* We can insert a sequence with a single assignment only. */
4745 gimple_seq stmts = VN_INFO (val)->expr;
4746 if (!gimple_seq_singleton_p (stmts))
4747 return NULL_TREE;
4748 gassign *stmt = dyn_cast <gassign *> (gimple_seq_first_stmt (stmts));
4749 if (!stmt
4750 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
4751 && gimple_assign_rhs_code (stmt) != VIEW_CONVERT_EXPR
4752 && gimple_assign_rhs_code (stmt) != BIT_FIELD_REF
4753 && (gimple_assign_rhs_code (stmt) != BIT_AND_EXPR
4754 || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)))
4755 return NULL_TREE;
4757 tree op = gimple_assign_rhs1 (stmt);
4758 if (gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
4759 || gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
4760 op = TREE_OPERAND (op, 0);
4761 tree leader = TREE_CODE (op) == SSA_NAME ? eliminate_avail (bb, op) : op;
4762 if (!leader)
4763 return NULL_TREE;
4765 tree res;
4766 stmts = NULL;
4767 if (gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
4768 res = gimple_build (&stmts, BIT_FIELD_REF,
4769 TREE_TYPE (val), leader,
4770 TREE_OPERAND (gimple_assign_rhs1 (stmt), 1),
4771 TREE_OPERAND (gimple_assign_rhs1 (stmt), 2));
4772 else if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR)
4773 res = gimple_build (&stmts, BIT_AND_EXPR,
4774 TREE_TYPE (val), leader, gimple_assign_rhs2 (stmt));
4775 else
4776 res = gimple_build (&stmts, gimple_assign_rhs_code (stmt),
4777 TREE_TYPE (val), leader);
4778 if (TREE_CODE (res) != SSA_NAME
4779 || SSA_NAME_IS_DEFAULT_DEF (res)
4780 || gimple_bb (SSA_NAME_DEF_STMT (res)))
4782 gimple_seq_discard (stmts);
4784 /* During propagation we have to treat SSA info conservatively
4785 and thus we can end up simplifying the inserted expression
4786 at elimination time to sth not defined in stmts. */
4787 /* But then this is a redundancy we failed to detect. Which means
4788 res now has two values. That doesn't play well with how
4789 we track availability here, so give up. */
4790 if (dump_file && (dump_flags & TDF_DETAILS))
4792 if (TREE_CODE (res) == SSA_NAME)
4793 res = eliminate_avail (bb, res);
4794 if (res)
4796 fprintf (dump_file, "Failed to insert expression for value ");
4797 print_generic_expr (dump_file, val);
4798 fprintf (dump_file, " which is really fully redundant to ");
4799 print_generic_expr (dump_file, res);
4800 fprintf (dump_file, "\n");
4804 return NULL_TREE;
4806 else
4808 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
4809 VN_INFO (res)->valnum = val;
4810 VN_INFO (res)->visited = true;
4813 insertions++;
4814 if (dump_file && (dump_flags & TDF_DETAILS))
4816 fprintf (dump_file, "Inserted ");
4817 print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (res), 0);
4820 return res;
4823 void
4824 eliminate_dom_walker::eliminate_stmt (basic_block b, gimple_stmt_iterator *gsi)
4826 tree sprime = NULL_TREE;
4827 gimple *stmt = gsi_stmt (*gsi);
4828 tree lhs = gimple_get_lhs (stmt);
4829 if (lhs && TREE_CODE (lhs) == SSA_NAME
4830 && !gimple_has_volatile_ops (stmt)
4831 /* See PR43491. Do not replace a global register variable when
4832 it is a the RHS of an assignment. Do replace local register
4833 variables since gcc does not guarantee a local variable will
4834 be allocated in register.
4835 ??? The fix isn't effective here. This should instead
4836 be ensured by not value-numbering them the same but treating
4837 them like volatiles? */
4838 && !(gimple_assign_single_p (stmt)
4839 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
4840 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))
4841 && is_global_var (gimple_assign_rhs1 (stmt)))))
4843 sprime = eliminate_avail (b, lhs);
4844 if (!sprime)
4846 /* If there is no existing usable leader but SCCVN thinks
4847 it has an expression it wants to use as replacement,
4848 insert that. */
4849 tree val = VN_INFO (lhs)->valnum;
4850 if (val != VN_TOP
4851 && TREE_CODE (val) == SSA_NAME
4852 && VN_INFO (val)->needs_insertion
4853 && VN_INFO (val)->expr != NULL
4854 && (sprime = eliminate_insert (b, gsi, val)) != NULL_TREE)
4855 eliminate_push_avail (b, sprime);
4858 /* If this now constitutes a copy duplicate points-to
4859 and range info appropriately. This is especially
4860 important for inserted code. See tree-ssa-copy.c
4861 for similar code. */
4862 if (sprime
4863 && TREE_CODE (sprime) == SSA_NAME)
4865 basic_block sprime_b = gimple_bb (SSA_NAME_DEF_STMT (sprime));
4866 if (POINTER_TYPE_P (TREE_TYPE (lhs))
4867 && SSA_NAME_PTR_INFO (lhs)
4868 && ! SSA_NAME_PTR_INFO (sprime))
4870 duplicate_ssa_name_ptr_info (sprime,
4871 SSA_NAME_PTR_INFO (lhs));
4872 if (b != sprime_b)
4873 mark_ptr_info_alignment_unknown
4874 (SSA_NAME_PTR_INFO (sprime));
4876 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4877 && SSA_NAME_RANGE_INFO (lhs)
4878 && ! SSA_NAME_RANGE_INFO (sprime)
4879 && b == sprime_b)
4880 duplicate_ssa_name_range_info (sprime,
4881 SSA_NAME_RANGE_TYPE (lhs),
4882 SSA_NAME_RANGE_INFO (lhs));
4885 /* Inhibit the use of an inserted PHI on a loop header when
4886 the address of the memory reference is a simple induction
4887 variable. In other cases the vectorizer won't do anything
4888 anyway (either it's loop invariant or a complicated
4889 expression). */
4890 if (sprime
4891 && TREE_CODE (sprime) == SSA_NAME
4892 && do_pre
4893 && (flag_tree_loop_vectorize || flag_tree_parallelize_loops > 1)
4894 && loop_outer (b->loop_father)
4895 && has_zero_uses (sprime)
4896 && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))
4897 && gimple_assign_load_p (stmt))
4899 gimple *def_stmt = SSA_NAME_DEF_STMT (sprime);
4900 basic_block def_bb = gimple_bb (def_stmt);
4901 if (gimple_code (def_stmt) == GIMPLE_PHI
4902 && def_bb->loop_father->header == def_bb)
4904 loop_p loop = def_bb->loop_father;
4905 ssa_op_iter iter;
4906 tree op;
4907 bool found = false;
4908 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
4910 affine_iv iv;
4911 def_bb = gimple_bb (SSA_NAME_DEF_STMT (op));
4912 if (def_bb
4913 && flow_bb_inside_loop_p (loop, def_bb)
4914 && simple_iv (loop, loop, op, &iv, true))
4916 found = true;
4917 break;
4920 if (found)
4922 if (dump_file && (dump_flags & TDF_DETAILS))
4924 fprintf (dump_file, "Not replacing ");
4925 print_gimple_expr (dump_file, stmt, 0);
4926 fprintf (dump_file, " with ");
4927 print_generic_expr (dump_file, sprime);
4928 fprintf (dump_file, " which would add a loop"
4929 " carried dependence to loop %d\n",
4930 loop->num);
4932 /* Don't keep sprime available. */
4933 sprime = NULL_TREE;
4938 if (sprime)
4940 /* If we can propagate the value computed for LHS into
4941 all uses don't bother doing anything with this stmt. */
4942 if (may_propagate_copy (lhs, sprime))
4944 /* Mark it for removal. */
4945 to_remove.safe_push (stmt);
4947 /* ??? Don't count copy/constant propagations. */
4948 if (gimple_assign_single_p (stmt)
4949 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
4950 || gimple_assign_rhs1 (stmt) == sprime))
4951 return;
4953 if (dump_file && (dump_flags & TDF_DETAILS))
4955 fprintf (dump_file, "Replaced ");
4956 print_gimple_expr (dump_file, stmt, 0);
4957 fprintf (dump_file, " with ");
4958 print_generic_expr (dump_file, sprime);
4959 fprintf (dump_file, " in all uses of ");
4960 print_gimple_stmt (dump_file, stmt, 0);
4963 eliminations++;
4964 return;
4967 /* If this is an assignment from our leader (which
4968 happens in the case the value-number is a constant)
4969 then there is nothing to do. */
4970 if (gimple_assign_single_p (stmt)
4971 && sprime == gimple_assign_rhs1 (stmt))
4972 return;
4974 /* Else replace its RHS. */
4975 bool can_make_abnormal_goto
4976 = is_gimple_call (stmt)
4977 && stmt_can_make_abnormal_goto (stmt);
4979 if (dump_file && (dump_flags & TDF_DETAILS))
4981 fprintf (dump_file, "Replaced ");
4982 print_gimple_expr (dump_file, stmt, 0);
4983 fprintf (dump_file, " with ");
4984 print_generic_expr (dump_file, sprime);
4985 fprintf (dump_file, " in ");
4986 print_gimple_stmt (dump_file, stmt, 0);
4989 eliminations++;
4990 gimple *orig_stmt = stmt;
4991 if (!useless_type_conversion_p (TREE_TYPE (lhs),
4992 TREE_TYPE (sprime)))
4993 sprime = fold_convert (TREE_TYPE (lhs), sprime);
4994 tree vdef = gimple_vdef (stmt);
4995 tree vuse = gimple_vuse (stmt);
4996 propagate_tree_value_into_stmt (gsi, sprime);
4997 stmt = gsi_stmt (*gsi);
4998 update_stmt (stmt);
4999 /* In case the VDEF on the original stmt was released, value-number
5000 it to the VUSE. This is to make vuse_ssa_val able to skip
5001 released virtual operands. */
5002 if (vdef != gimple_vdef (stmt))
5004 gcc_assert (SSA_NAME_IN_FREE_LIST (vdef));
5005 VN_INFO (vdef)->valnum = vuse;
5008 /* If we removed EH side-effects from the statement, clean
5009 its EH information. */
5010 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
5012 bitmap_set_bit (need_eh_cleanup,
5013 gimple_bb (stmt)->index);
5014 if (dump_file && (dump_flags & TDF_DETAILS))
5015 fprintf (dump_file, " Removed EH side-effects.\n");
5018 /* Likewise for AB side-effects. */
5019 if (can_make_abnormal_goto
5020 && !stmt_can_make_abnormal_goto (stmt))
5022 bitmap_set_bit (need_ab_cleanup,
5023 gimple_bb (stmt)->index);
5024 if (dump_file && (dump_flags & TDF_DETAILS))
5025 fprintf (dump_file, " Removed AB side-effects.\n");
5028 return;
5032 /* If the statement is a scalar store, see if the expression
5033 has the same value number as its rhs. If so, the store is
5034 dead. */
5035 if (gimple_assign_single_p (stmt)
5036 && !gimple_has_volatile_ops (stmt)
5037 && !is_gimple_reg (gimple_assign_lhs (stmt))
5038 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
5039 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
5041 tree val;
5042 tree rhs = gimple_assign_rhs1 (stmt);
5043 vn_reference_t vnresult;
5044 val = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_WALKREWRITE,
5045 &vnresult, false);
5046 if (TREE_CODE (rhs) == SSA_NAME)
5047 rhs = VN_INFO (rhs)->valnum;
5048 if (val
5049 && operand_equal_p (val, rhs, 0))
5051 /* We can only remove the later store if the former aliases
5052 at least all accesses the later one does or if the store
5053 was to readonly memory storing the same value. */
5054 alias_set_type set = get_alias_set (lhs);
5055 if (! vnresult
5056 || vnresult->set == set
5057 || alias_set_subset_of (set, vnresult->set))
5059 if (dump_file && (dump_flags & TDF_DETAILS))
5061 fprintf (dump_file, "Deleted redundant store ");
5062 print_gimple_stmt (dump_file, stmt, 0);
5065 /* Queue stmt for removal. */
5066 to_remove.safe_push (stmt);
5067 return;
5072 /* If this is a control statement value numbering left edges
5073 unexecuted on force the condition in a way consistent with
5074 that. */
5075 if (gcond *cond = dyn_cast <gcond *> (stmt))
5077 if ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE)
5078 ^ (EDGE_SUCC (b, 1)->flags & EDGE_EXECUTABLE))
5080 if (dump_file && (dump_flags & TDF_DETAILS))
5082 fprintf (dump_file, "Removing unexecutable edge from ");
5083 print_gimple_stmt (dump_file, stmt, 0);
5085 if (((EDGE_SUCC (b, 0)->flags & EDGE_TRUE_VALUE) != 0)
5086 == ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE) != 0))
5087 gimple_cond_make_true (cond);
5088 else
5089 gimple_cond_make_false (cond);
5090 update_stmt (cond);
5091 el_todo |= TODO_cleanup_cfg;
5092 return;
5096 bool can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt);
5097 bool was_noreturn = (is_gimple_call (stmt)
5098 && gimple_call_noreturn_p (stmt));
5099 tree vdef = gimple_vdef (stmt);
5100 tree vuse = gimple_vuse (stmt);
5102 /* If we didn't replace the whole stmt (or propagate the result
5103 into all uses), replace all uses on this stmt with their
5104 leaders. */
5105 bool modified = false;
5106 use_operand_p use_p;
5107 ssa_op_iter iter;
5108 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
5110 tree use = USE_FROM_PTR (use_p);
5111 /* ??? The call code above leaves stmt operands un-updated. */
5112 if (TREE_CODE (use) != SSA_NAME)
5113 continue;
5114 tree sprime;
5115 if (SSA_NAME_IS_DEFAULT_DEF (use))
5116 /* ??? For default defs BB shouldn't matter, but we have to
5117 solve the inconsistency between rpo eliminate and
5118 dom eliminate avail valueization first. */
5119 sprime = eliminate_avail (b, use);
5120 else
5121 /* Look for sth available at the definition block of the argument.
5122 This avoids inconsistencies between availability there which
5123 decides if the stmt can be removed and availability at the
5124 use site. The SSA property ensures that things available
5125 at the definition are also available at uses. */
5126 sprime = eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (use)), use);
5127 if (sprime && sprime != use
5128 && may_propagate_copy (use, sprime)
5129 /* We substitute into debug stmts to avoid excessive
5130 debug temporaries created by removed stmts, but we need
5131 to avoid doing so for inserted sprimes as we never want
5132 to create debug temporaries for them. */
5133 && (!inserted_exprs
5134 || TREE_CODE (sprime) != SSA_NAME
5135 || !is_gimple_debug (stmt)
5136 || !bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))))
5138 propagate_value (use_p, sprime);
5139 modified = true;
5143 /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
5144 into which is a requirement for the IPA devirt machinery. */
5145 gimple *old_stmt = stmt;
5146 if (modified)
5148 /* If a formerly non-invariant ADDR_EXPR is turned into an
5149 invariant one it was on a separate stmt. */
5150 if (gimple_assign_single_p (stmt)
5151 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
5152 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
5153 gimple_stmt_iterator prev = *gsi;
5154 gsi_prev (&prev);
5155 if (fold_stmt (gsi))
5157 /* fold_stmt may have created new stmts inbetween
5158 the previous stmt and the folded stmt. Mark
5159 all defs created there as varying to not confuse
5160 the SCCVN machinery as we're using that even during
5161 elimination. */
5162 if (gsi_end_p (prev))
5163 prev = gsi_start_bb (b);
5164 else
5165 gsi_next (&prev);
5166 if (gsi_stmt (prev) != gsi_stmt (*gsi))
5169 tree def;
5170 ssa_op_iter dit;
5171 FOR_EACH_SSA_TREE_OPERAND (def, gsi_stmt (prev),
5172 dit, SSA_OP_ALL_DEFS)
5173 /* As existing DEFs may move between stmts
5174 only process new ones. */
5175 if (! has_VN_INFO (def))
5177 VN_INFO (def)->valnum = def;
5178 VN_INFO (def)->visited = true;
5180 if (gsi_stmt (prev) == gsi_stmt (*gsi))
5181 break;
5182 gsi_next (&prev);
5184 while (1);
5186 stmt = gsi_stmt (*gsi);
5187 /* In case we folded the stmt away schedule the NOP for removal. */
5188 if (gimple_nop_p (stmt))
5189 to_remove.safe_push (stmt);
5192 /* Visit indirect calls and turn them into direct calls if
5193 possible using the devirtualization machinery. Do this before
5194 checking for required EH/abnormal/noreturn cleanup as devird
5195 may expose more of those. */
5196 if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
5198 tree fn = gimple_call_fn (call_stmt);
5199 if (fn
5200 && flag_devirtualize
5201 && virtual_method_call_p (fn))
5203 tree otr_type = obj_type_ref_class (fn);
5204 unsigned HOST_WIDE_INT otr_tok
5205 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn));
5206 tree instance;
5207 ipa_polymorphic_call_context context (current_function_decl,
5208 fn, stmt, &instance);
5209 context.get_dynamic_type (instance, OBJ_TYPE_REF_OBJECT (fn),
5210 otr_type, stmt);
5211 bool final;
5212 vec <cgraph_node *> targets
5213 = possible_polymorphic_call_targets (obj_type_ref_class (fn),
5214 otr_tok, context, &final);
5215 if (dump_file)
5216 dump_possible_polymorphic_call_targets (dump_file,
5217 obj_type_ref_class (fn),
5218 otr_tok, context);
5219 if (final && targets.length () <= 1 && dbg_cnt (devirt))
5221 tree fn;
5222 if (targets.length () == 1)
5223 fn = targets[0]->decl;
5224 else
5225 fn = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
5226 if (dump_enabled_p ())
5228 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
5229 "converting indirect call to "
5230 "function %s\n",
5231 lang_hooks.decl_printable_name (fn, 2));
5233 gimple_call_set_fndecl (call_stmt, fn);
5234 /* If changing the call to __builtin_unreachable
5235 or similar noreturn function, adjust gimple_call_fntype
5236 too. */
5237 if (gimple_call_noreturn_p (call_stmt)
5238 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn)))
5239 && TYPE_ARG_TYPES (TREE_TYPE (fn))
5240 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn)))
5241 == void_type_node))
5242 gimple_call_set_fntype (call_stmt, TREE_TYPE (fn));
5243 maybe_remove_unused_call_args (cfun, call_stmt);
5244 modified = true;
5249 if (modified)
5251 /* When changing a call into a noreturn call, cfg cleanup
5252 is needed to fix up the noreturn call. */
5253 if (!was_noreturn
5254 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
5255 to_fixup.safe_push (stmt);
5256 /* When changing a condition or switch into one we know what
5257 edge will be executed, schedule a cfg cleanup. */
5258 if ((gimple_code (stmt) == GIMPLE_COND
5259 && (gimple_cond_true_p (as_a <gcond *> (stmt))
5260 || gimple_cond_false_p (as_a <gcond *> (stmt))))
5261 || (gimple_code (stmt) == GIMPLE_SWITCH
5262 && TREE_CODE (gimple_switch_index
5263 (as_a <gswitch *> (stmt))) == INTEGER_CST))
5264 el_todo |= TODO_cleanup_cfg;
5265 /* If we removed EH side-effects from the statement, clean
5266 its EH information. */
5267 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
5269 bitmap_set_bit (need_eh_cleanup,
5270 gimple_bb (stmt)->index);
5271 if (dump_file && (dump_flags & TDF_DETAILS))
5272 fprintf (dump_file, " Removed EH side-effects.\n");
5274 /* Likewise for AB side-effects. */
5275 if (can_make_abnormal_goto
5276 && !stmt_can_make_abnormal_goto (stmt))
5278 bitmap_set_bit (need_ab_cleanup,
5279 gimple_bb (stmt)->index);
5280 if (dump_file && (dump_flags & TDF_DETAILS))
5281 fprintf (dump_file, " Removed AB side-effects.\n");
5283 update_stmt (stmt);
5284 /* In case the VDEF on the original stmt was released, value-number
5285 it to the VUSE. This is to make vuse_ssa_val able to skip
5286 released virtual operands. */
5287 if (vdef && SSA_NAME_IN_FREE_LIST (vdef))
5288 VN_INFO (vdef)->valnum = vuse;
5291 /* Make new values available - for fully redundant LHS we
5292 continue with the next stmt above and skip this. */
5293 def_operand_p defp;
5294 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_DEF)
5295 eliminate_push_avail (b, DEF_FROM_PTR (defp));
5298 /* Perform elimination for the basic-block B during the domwalk. */
5300 edge
5301 eliminate_dom_walker::before_dom_children (basic_block b)
5303 /* Mark new bb. */
5304 avail_stack.safe_push (NULL_TREE);
5306 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
5307 if (!(b->flags & BB_EXECUTABLE))
5308 return NULL;
5310 vn_context_bb = b;
5312 for (gphi_iterator gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
5314 gphi *phi = gsi.phi ();
5315 tree res = PHI_RESULT (phi);
5317 if (virtual_operand_p (res))
5319 gsi_next (&gsi);
5320 continue;
5323 tree sprime = eliminate_avail (b, res);
5324 if (sprime
5325 && sprime != res)
5327 if (dump_file && (dump_flags & TDF_DETAILS))
5329 fprintf (dump_file, "Replaced redundant PHI node defining ");
5330 print_generic_expr (dump_file, res);
5331 fprintf (dump_file, " with ");
5332 print_generic_expr (dump_file, sprime);
5333 fprintf (dump_file, "\n");
5336 /* If we inserted this PHI node ourself, it's not an elimination. */
5337 if (! inserted_exprs
5338 || ! bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
5339 eliminations++;
5341 /* If we will propagate into all uses don't bother to do
5342 anything. */
5343 if (may_propagate_copy (res, sprime))
5345 /* Mark the PHI for removal. */
5346 to_remove.safe_push (phi);
5347 gsi_next (&gsi);
5348 continue;
5351 remove_phi_node (&gsi, false);
5353 if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
5354 sprime = fold_convert (TREE_TYPE (res), sprime);
5355 gimple *stmt = gimple_build_assign (res, sprime);
5356 gimple_stmt_iterator gsi2 = gsi_after_labels (b);
5357 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
5358 continue;
5361 eliminate_push_avail (b, res);
5362 gsi_next (&gsi);
5365 for (gimple_stmt_iterator gsi = gsi_start_bb (b);
5366 !gsi_end_p (gsi);
5367 gsi_next (&gsi))
5368 eliminate_stmt (b, &gsi);
5370 /* Replace destination PHI arguments. */
5371 edge_iterator ei;
5372 edge e;
5373 FOR_EACH_EDGE (e, ei, b->succs)
5374 if (e->flags & EDGE_EXECUTABLE)
5375 for (gphi_iterator gsi = gsi_start_phis (e->dest);
5376 !gsi_end_p (gsi);
5377 gsi_next (&gsi))
5379 gphi *phi = gsi.phi ();
5380 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
5381 tree arg = USE_FROM_PTR (use_p);
5382 if (TREE_CODE (arg) != SSA_NAME
5383 || virtual_operand_p (arg))
5384 continue;
5385 tree sprime = eliminate_avail (b, arg);
5386 if (sprime && may_propagate_copy (arg, sprime))
5387 propagate_value (use_p, sprime);
5390 vn_context_bb = NULL;
5392 return NULL;
5395 /* Make no longer available leaders no longer available. */
5397 void
5398 eliminate_dom_walker::after_dom_children (basic_block)
5400 tree entry;
5401 while ((entry = avail_stack.pop ()) != NULL_TREE)
5403 tree valnum = VN_INFO (entry)->valnum;
5404 tree old = avail[SSA_NAME_VERSION (valnum)];
5405 if (old == entry)
5406 avail[SSA_NAME_VERSION (valnum)] = NULL_TREE;
5407 else
5408 avail[SSA_NAME_VERSION (valnum)] = entry;
5412 /* Remove queued stmts and perform delayed cleanups. */
5414 unsigned
5415 eliminate_dom_walker::eliminate_cleanup (bool region_p)
5417 statistics_counter_event (cfun, "Eliminated", eliminations);
5418 statistics_counter_event (cfun, "Insertions", insertions);
5420 /* We cannot remove stmts during BB walk, especially not release SSA
5421 names there as this confuses the VN machinery. The stmts ending
5422 up in to_remove are either stores or simple copies.
5423 Remove stmts in reverse order to make debug stmt creation possible. */
5424 while (!to_remove.is_empty ())
5426 bool do_release_defs = true;
5427 gimple *stmt = to_remove.pop ();
5429 /* When we are value-numbering a region we do not require exit PHIs to
5430 be present so we have to make sure to deal with uses outside of the
5431 region of stmts that we thought are eliminated.
5432 ??? Note we may be confused by uses in dead regions we didn't run
5433 elimination on. Rather than checking individual uses we accept
5434 dead copies to be generated here (gcc.c-torture/execute/20060905-1.c
5435 contains such example). */
5436 if (region_p)
5438 if (gphi *phi = dyn_cast <gphi *> (stmt))
5440 tree lhs = gimple_phi_result (phi);
5441 if (!has_zero_uses (lhs))
5443 if (dump_file && (dump_flags & TDF_DETAILS))
5444 fprintf (dump_file, "Keeping eliminated stmt live "
5445 "as copy because of out-of-region uses\n");
5446 tree sprime = eliminate_avail (gimple_bb (stmt), lhs);
5447 gimple *copy = gimple_build_assign (lhs, sprime);
5448 gimple_stmt_iterator gsi
5449 = gsi_after_labels (gimple_bb (stmt));
5450 gsi_insert_before (&gsi, copy, GSI_SAME_STMT);
5451 do_release_defs = false;
5454 else if (tree lhs = gimple_get_lhs (stmt))
5455 if (TREE_CODE (lhs) == SSA_NAME
5456 && !has_zero_uses (lhs))
5458 if (dump_file && (dump_flags & TDF_DETAILS))
5459 fprintf (dump_file, "Keeping eliminated stmt live "
5460 "as copy because of out-of-region uses\n");
5461 tree sprime = eliminate_avail (gimple_bb (stmt), lhs);
5462 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
5463 if (is_gimple_assign (stmt))
5465 gimple_assign_set_rhs_from_tree (&gsi, sprime);
5466 stmt = gsi_stmt (gsi);
5467 update_stmt (stmt);
5468 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
5469 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
5470 continue;
5472 else
5474 gimple *copy = gimple_build_assign (lhs, sprime);
5475 gsi_insert_before (&gsi, copy, GSI_SAME_STMT);
5476 do_release_defs = false;
5481 if (dump_file && (dump_flags & TDF_DETAILS))
5483 fprintf (dump_file, "Removing dead stmt ");
5484 print_gimple_stmt (dump_file, stmt, 0, TDF_NONE);
5487 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
5488 if (gimple_code (stmt) == GIMPLE_PHI)
5489 remove_phi_node (&gsi, do_release_defs);
5490 else
5492 basic_block bb = gimple_bb (stmt);
5493 unlink_stmt_vdef (stmt);
5494 if (gsi_remove (&gsi, true))
5495 bitmap_set_bit (need_eh_cleanup, bb->index);
5496 if (is_gimple_call (stmt) && stmt_can_make_abnormal_goto (stmt))
5497 bitmap_set_bit (need_ab_cleanup, bb->index);
5498 if (do_release_defs)
5499 release_defs (stmt);
5502 /* Removing a stmt may expose a forwarder block. */
5503 el_todo |= TODO_cleanup_cfg;
5506 /* Fixup stmts that became noreturn calls. This may require splitting
5507 blocks and thus isn't possible during the dominator walk. Do this
5508 in reverse order so we don't inadvertedly remove a stmt we want to
5509 fixup by visiting a dominating now noreturn call first. */
5510 while (!to_fixup.is_empty ())
5512 gimple *stmt = to_fixup.pop ();
5514 if (dump_file && (dump_flags & TDF_DETAILS))
5516 fprintf (dump_file, "Fixing up noreturn call ");
5517 print_gimple_stmt (dump_file, stmt, 0);
5520 if (fixup_noreturn_call (stmt))
5521 el_todo |= TODO_cleanup_cfg;
5524 bool do_eh_cleanup = !bitmap_empty_p (need_eh_cleanup);
5525 bool do_ab_cleanup = !bitmap_empty_p (need_ab_cleanup);
5527 if (do_eh_cleanup)
5528 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
5530 if (do_ab_cleanup)
5531 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
5533 if (do_eh_cleanup || do_ab_cleanup)
5534 el_todo |= TODO_cleanup_cfg;
5536 return el_todo;
5539 /* Eliminate fully redundant computations. */
5541 unsigned
5542 eliminate_with_rpo_vn (bitmap inserted_exprs)
5544 eliminate_dom_walker walker (CDI_DOMINATORS, inserted_exprs);
5546 walker.walk (cfun->cfg->x_entry_block_ptr);
5547 return walker.eliminate_cleanup ();
5550 static unsigned
5551 do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
5552 bool iterate, bool eliminate);
5554 void
5555 run_rpo_vn (vn_lookup_kind kind)
5557 default_vn_walk_kind = kind;
5558 do_rpo_vn (cfun, NULL, NULL, true, false);
5560 /* ??? Prune requirement of these. */
5561 constant_to_value_id = new hash_table<vn_constant_hasher> (23);
5562 constant_value_ids = BITMAP_ALLOC (NULL);
5564 /* Initialize the value ids and prune out remaining VN_TOPs
5565 from dead code. */
5566 tree name;
5567 unsigned i;
5568 FOR_EACH_SSA_NAME (i, name, cfun)
5570 vn_ssa_aux_t info = VN_INFO (name);
5571 if (!info->visited
5572 || info->valnum == VN_TOP)
5573 info->valnum = name;
5574 if (info->valnum == name)
5575 info->value_id = get_next_value_id ();
5576 else if (is_gimple_min_invariant (info->valnum))
5577 info->value_id = get_or_alloc_constant_value_id (info->valnum);
5580 /* Propagate. */
5581 FOR_EACH_SSA_NAME (i, name, cfun)
5583 vn_ssa_aux_t info = VN_INFO (name);
5584 if (TREE_CODE (info->valnum) == SSA_NAME
5585 && info->valnum != name
5586 && info->value_id != VN_INFO (info->valnum)->value_id)
5587 info->value_id = VN_INFO (info->valnum)->value_id;
5590 set_hashtable_value_ids ();
5592 if (dump_file && (dump_flags & TDF_DETAILS))
5594 fprintf (dump_file, "Value numbers:\n");
5595 FOR_EACH_SSA_NAME (i, name, cfun)
5597 if (VN_INFO (name)->visited
5598 && SSA_VAL (name) != name)
5600 print_generic_expr (dump_file, name);
5601 fprintf (dump_file, " = ");
5602 print_generic_expr (dump_file, SSA_VAL (name));
5603 fprintf (dump_file, " (%04d)\n", VN_INFO (name)->value_id);
5609 /* Free VN associated data structures. */
5611 void
5612 free_rpo_vn (void)
5614 free_vn_table (valid_info);
5615 XDELETE (valid_info);
5616 obstack_free (&vn_tables_obstack, NULL);
5617 obstack_free (&vn_tables_insert_obstack, NULL);
5619 vn_ssa_aux_iterator_type it;
5620 vn_ssa_aux_t info;
5621 FOR_EACH_HASH_TABLE_ELEMENT (*vn_ssa_aux_hash, info, vn_ssa_aux_t, it)
5622 if (info->needs_insertion)
5623 release_ssa_name (info->name);
5624 obstack_free (&vn_ssa_aux_obstack, NULL);
5625 delete vn_ssa_aux_hash;
5627 delete constant_to_value_id;
5628 constant_to_value_id = NULL;
5629 BITMAP_FREE (constant_value_ids);
5632 /* Adaptor to the elimination engine using RPO availability. */
5634 class rpo_elim : public eliminate_dom_walker
5636 public:
5637 rpo_elim(basic_block entry_)
5638 : eliminate_dom_walker (CDI_DOMINATORS, NULL), entry (entry_) {}
5639 ~rpo_elim();
5641 virtual tree eliminate_avail (basic_block, tree op);
5643 virtual void eliminate_push_avail (basic_block, tree);
5645 basic_block entry;
5646 /* Instead of having a local availability lattice for each
5647 basic-block and availability at X defined as union of
5648 the local availabilities at X and its dominators we're
5649 turning this upside down and track availability per
5650 value given values are usually made available at very
5651 few points (at least one).
5652 So we have a value -> vec<location, leader> map where
5653 LOCATION is specifying the basic-block LEADER is made
5654 available for VALUE. We push to this vector in RPO
5655 order thus for iteration we can simply pop the last
5656 entries.
5657 LOCATION is the basic-block index and LEADER is its
5658 SSA name version. */
5659 /* ??? We'd like to use auto_vec here with embedded storage
5660 but that doesn't play well until we can provide move
5661 constructors and use std::move on hash-table expansion.
5662 So for now this is a bit more expensive than necessary.
5663 We eventually want to switch to a chaining scheme like
5664 for hashtable entries for unwinding which would make
5665 making the vector part of the vn_ssa_aux structure possible. */
5666 typedef hash_map<tree, vec<std::pair<int, int> > > rpo_avail_t;
5667 rpo_avail_t m_rpo_avail;
5670 /* Global RPO state for access from hooks. */
5671 static rpo_elim *rpo_avail;
5673 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
5675 static tree
5676 vn_lookup_simplify_result (gimple_match_op *res_op)
5678 if (!res_op->code.is_tree_code ())
5679 return NULL_TREE;
5680 tree *ops = res_op->ops;
5681 unsigned int length = res_op->num_ops;
5682 if (res_op->code == CONSTRUCTOR
5683 /* ??? We're arriving here with SCCVNs view, decomposed CONSTRUCTOR
5684 and GIMPLEs / match-and-simplifies, CONSTRUCTOR as GENERIC tree. */
5685 && TREE_CODE (res_op->ops[0]) == CONSTRUCTOR)
5687 length = CONSTRUCTOR_NELTS (res_op->ops[0]);
5688 ops = XALLOCAVEC (tree, length);
5689 for (unsigned i = 0; i < length; ++i)
5690 ops[i] = CONSTRUCTOR_ELT (res_op->ops[0], i)->value;
5692 vn_nary_op_t vnresult = NULL;
5693 tree res = vn_nary_op_lookup_pieces (length, (tree_code) res_op->code,
5694 res_op->type, ops, &vnresult);
5695 /* If this is used from expression simplification make sure to
5696 return an available expression. */
5697 if (res && TREE_CODE (res) == SSA_NAME && mprts_hook && rpo_avail)
5698 res = rpo_avail->eliminate_avail (vn_context_bb, res);
5699 return res;
5702 rpo_elim::~rpo_elim ()
5704 /* Release the avail vectors. */
5705 for (rpo_avail_t::iterator i = m_rpo_avail.begin ();
5706 i != m_rpo_avail.end (); ++i)
5707 (*i).second.release ();
5710 /* Return a leader for OPs value that is valid at BB. */
5712 tree
5713 rpo_elim::eliminate_avail (basic_block bb, tree op)
5715 bool visited;
5716 tree valnum = SSA_VAL (op, &visited);
5717 /* If we didn't visit OP then it must be defined outside of the
5718 region we process and also dominate it. So it is available. */
5719 if (!visited)
5720 return op;
5721 if (TREE_CODE (valnum) == SSA_NAME)
5723 if (SSA_NAME_IS_DEFAULT_DEF (valnum))
5724 return valnum;
5725 vec<std::pair<int, int> > *av = m_rpo_avail.get (valnum);
5726 if (!av || av->is_empty ())
5727 return NULL_TREE;
5728 int i = av->length () - 1;
5729 if ((*av)[i].first == bb->index)
5730 /* On tramp3d 90% of the cases are here. */
5731 return ssa_name ((*av)[i].second);
5734 basic_block abb = BASIC_BLOCK_FOR_FN (cfun, (*av)[i].first);
5735 /* ??? During elimination we have to use availability at the
5736 definition site of a use we try to replace. This
5737 is required to not run into inconsistencies because
5738 of dominated_by_p_w_unex behavior and removing a definition
5739 while not replacing all uses.
5740 ??? We could try to consistently walk dominators
5741 ignoring non-executable regions. The nearest common
5742 dominator of bb and abb is where we can stop walking. We
5743 may also be able to "pre-compute" (bits of) the next immediate
5744 (non-)dominator during the RPO walk when marking edges as
5745 executable. */
5746 if (dominated_by_p_w_unex (bb, abb))
5748 tree leader = ssa_name ((*av)[i].second);
5749 /* Prevent eliminations that break loop-closed SSA. */
5750 if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
5751 && ! SSA_NAME_IS_DEFAULT_DEF (leader)
5752 && ! flow_bb_inside_loop_p (gimple_bb (SSA_NAME_DEF_STMT
5753 (leader))->loop_father,
5754 bb))
5755 return NULL_TREE;
5756 if (dump_file && (dump_flags & TDF_DETAILS))
5758 print_generic_expr (dump_file, leader);
5759 fprintf (dump_file, " is available for ");
5760 print_generic_expr (dump_file, valnum);
5761 fprintf (dump_file, "\n");
5763 /* On tramp3d 99% of the _remaining_ cases succeed at
5764 the first enty. */
5765 return leader;
5767 /* ??? Can we somehow skip to the immediate dominator
5768 RPO index (bb_to_rpo)? Again, maybe not worth, on
5769 tramp3d the worst number of elements in the vector is 9. */
5771 while (--i >= 0);
5773 else if (valnum != VN_TOP)
5774 /* valnum is is_gimple_min_invariant. */
5775 return valnum;
5776 return NULL_TREE;
5779 /* Make LEADER a leader for its value at BB. */
5781 void
5782 rpo_elim::eliminate_push_avail (basic_block bb, tree leader)
5784 tree valnum = VN_INFO (leader)->valnum;
5785 if (valnum == VN_TOP)
5786 return;
5787 if (dump_file && (dump_flags & TDF_DETAILS))
5789 fprintf (dump_file, "Making available beyond BB%d ", bb->index);
5790 print_generic_expr (dump_file, leader);
5791 fprintf (dump_file, " for value ");
5792 print_generic_expr (dump_file, valnum);
5793 fprintf (dump_file, "\n");
5795 bool existed;
5796 vec<std::pair<int, int> > &av = m_rpo_avail.get_or_insert (valnum, &existed);
5797 if (!existed)
5799 new (&av) vec<std::pair<int, int> >;
5800 av = vNULL;
5801 av.reserve_exact (2);
5803 av.safe_push (std::make_pair (bb->index, SSA_NAME_VERSION (leader)));
5806 /* Valueization hook for RPO VN plus required state. */
5808 tree
5809 rpo_vn_valueize (tree name)
5811 if (TREE_CODE (name) == SSA_NAME)
5813 vn_ssa_aux_t val = VN_INFO (name);
5814 if (val)
5816 tree tem = val->valnum;
5817 if (tem != VN_TOP && tem != name)
5819 if (TREE_CODE (tem) != SSA_NAME)
5820 return tem;
5821 /* For all values we only valueize to an available leader
5822 which means we can use SSA name info without restriction. */
5823 tem = rpo_avail->eliminate_avail (vn_context_bb, tem);
5824 if (tem)
5825 return tem;
5829 return name;
5832 /* Insert on PRED_E predicates derived from CODE OPS being true besides the
5833 inverted condition. */
5835 static void
5836 insert_related_predicates_on_edge (enum tree_code code, tree *ops, edge pred_e)
5838 switch (code)
5840 case LT_EXPR:
5841 /* a < b -> a {!,<}= b */
5842 vn_nary_op_insert_pieces_predicated (2, NE_EXPR, boolean_type_node,
5843 ops, boolean_true_node, 0, pred_e);
5844 vn_nary_op_insert_pieces_predicated (2, LE_EXPR, boolean_type_node,
5845 ops, boolean_true_node, 0, pred_e);
5846 /* a < b -> ! a {>,=} b */
5847 vn_nary_op_insert_pieces_predicated (2, GT_EXPR, boolean_type_node,
5848 ops, boolean_false_node, 0, pred_e);
5849 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR, boolean_type_node,
5850 ops, boolean_false_node, 0, pred_e);
5851 break;
5852 case GT_EXPR:
5853 /* a > b -> a {!,>}= b */
5854 vn_nary_op_insert_pieces_predicated (2, NE_EXPR, boolean_type_node,
5855 ops, boolean_true_node, 0, pred_e);
5856 vn_nary_op_insert_pieces_predicated (2, GE_EXPR, boolean_type_node,
5857 ops, boolean_true_node, 0, pred_e);
5858 /* a > b -> ! a {<,=} b */
5859 vn_nary_op_insert_pieces_predicated (2, LT_EXPR, boolean_type_node,
5860 ops, boolean_false_node, 0, pred_e);
5861 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR, boolean_type_node,
5862 ops, boolean_false_node, 0, pred_e);
5863 break;
5864 case EQ_EXPR:
5865 /* a == b -> ! a {<,>} b */
5866 vn_nary_op_insert_pieces_predicated (2, LT_EXPR, boolean_type_node,
5867 ops, boolean_false_node, 0, pred_e);
5868 vn_nary_op_insert_pieces_predicated (2, GT_EXPR, boolean_type_node,
5869 ops, boolean_false_node, 0, pred_e);
5870 break;
5871 case LE_EXPR:
5872 case GE_EXPR:
5873 case NE_EXPR:
5874 /* Nothing besides inverted condition. */
5875 break;
5876 default:;
5880 /* Main stmt worker for RPO VN, process BB. */
5882 static unsigned
5883 process_bb (rpo_elim &avail, basic_block bb,
5884 bool bb_visited, bool iterate_phis, bool iterate, bool eliminate,
5885 bool do_region, bitmap exit_bbs)
5887 unsigned todo = 0;
5888 edge_iterator ei;
5889 edge e;
5891 vn_context_bb = bb;
5893 /* If we are in loop-closed SSA preserve this state. This is
5894 relevant when called on regions from outside of FRE/PRE. */
5895 bool lc_phi_nodes = false;
5896 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
5897 FOR_EACH_EDGE (e, ei, bb->preds)
5898 if (e->src->loop_father != e->dest->loop_father
5899 && flow_loop_nested_p (e->dest->loop_father,
5900 e->src->loop_father))
5902 lc_phi_nodes = true;
5903 break;
5906 /* Value-number all defs in the basic-block. */
5907 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5908 gsi_next (&gsi))
5910 gphi *phi = gsi.phi ();
5911 tree res = PHI_RESULT (phi);
5912 vn_ssa_aux_t res_info = VN_INFO (res);
5913 if (!bb_visited)
5915 gcc_assert (!res_info->visited);
5916 res_info->valnum = VN_TOP;
5917 res_info->visited = true;
5920 /* When not iterating force backedge values to varying. */
5921 visit_stmt (phi, !iterate_phis);
5922 if (virtual_operand_p (res))
5923 continue;
5925 /* Eliminate */
5926 /* The interesting case is gcc.dg/tree-ssa/pr22230.c for correctness
5927 how we handle backedges and availability.
5928 And gcc.dg/tree-ssa/ssa-sccvn-2.c for optimization. */
5929 tree val = res_info->valnum;
5930 if (res != val && !iterate && eliminate)
5932 if (tree leader = avail.eliminate_avail (bb, res))
5934 if (leader != res
5935 /* Preserve loop-closed SSA form. */
5936 && (! lc_phi_nodes
5937 || is_gimple_min_invariant (leader)))
5939 if (dump_file && (dump_flags & TDF_DETAILS))
5941 fprintf (dump_file, "Replaced redundant PHI node "
5942 "defining ");
5943 print_generic_expr (dump_file, res);
5944 fprintf (dump_file, " with ");
5945 print_generic_expr (dump_file, leader);
5946 fprintf (dump_file, "\n");
5948 avail.eliminations++;
5950 if (may_propagate_copy (res, leader))
5952 /* Schedule for removal. */
5953 avail.to_remove.safe_push (phi);
5954 continue;
5956 /* ??? Else generate a copy stmt. */
5960 /* Only make defs available that not already are. But make
5961 sure loop-closed SSA PHI node defs are picked up for
5962 downstream uses. */
5963 if (lc_phi_nodes
5964 || res == val
5965 || ! avail.eliminate_avail (bb, res))
5966 avail.eliminate_push_avail (bb, res);
5969 /* For empty BBs mark outgoing edges executable. For non-empty BBs
5970 we do this when processing the last stmt as we have to do this
5971 before elimination which otherwise forces GIMPLE_CONDs to
5972 if (1 != 0) style when seeing non-executable edges. */
5973 if (gsi_end_p (gsi_start_bb (bb)))
5975 FOR_EACH_EDGE (e, ei, bb->succs)
5977 if (!(e->flags & EDGE_EXECUTABLE))
5979 if (dump_file && (dump_flags & TDF_DETAILS))
5980 fprintf (dump_file,
5981 "marking outgoing edge %d -> %d executable\n",
5982 e->src->index, e->dest->index);
5983 e->flags |= EDGE_EXECUTABLE;
5984 e->dest->flags |= BB_EXECUTABLE;
5986 else if (!(e->dest->flags & BB_EXECUTABLE))
5988 if (dump_file && (dump_flags & TDF_DETAILS))
5989 fprintf (dump_file,
5990 "marking destination block %d reachable\n",
5991 e->dest->index);
5992 e->dest->flags |= BB_EXECUTABLE;
5996 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
5997 !gsi_end_p (gsi); gsi_next (&gsi))
5999 ssa_op_iter i;
6000 tree op;
6001 if (!bb_visited)
6003 FOR_EACH_SSA_TREE_OPERAND (op, gsi_stmt (gsi), i, SSA_OP_ALL_DEFS)
6005 vn_ssa_aux_t op_info = VN_INFO (op);
6006 gcc_assert (!op_info->visited);
6007 op_info->valnum = VN_TOP;
6008 op_info->visited = true;
6011 /* We somehow have to deal with uses that are not defined
6012 in the processed region. Forcing unvisited uses to
6013 varying here doesn't play well with def-use following during
6014 expression simplification, so we deal with this by checking
6015 the visited flag in SSA_VAL. */
6018 visit_stmt (gsi_stmt (gsi));
6020 gimple *last = gsi_stmt (gsi);
6021 e = NULL;
6022 switch (gimple_code (last))
6024 case GIMPLE_SWITCH:
6025 e = find_taken_edge (bb, vn_valueize (gimple_switch_index
6026 (as_a <gswitch *> (last))));
6027 break;
6028 case GIMPLE_COND:
6030 tree lhs = vn_valueize (gimple_cond_lhs (last));
6031 tree rhs = vn_valueize (gimple_cond_rhs (last));
6032 tree val = gimple_simplify (gimple_cond_code (last),
6033 boolean_type_node, lhs, rhs,
6034 NULL, vn_valueize);
6035 /* If the condition didn't simplfy see if we have recorded
6036 an expression from sofar taken edges. */
6037 if (! val || TREE_CODE (val) != INTEGER_CST)
6039 vn_nary_op_t vnresult;
6040 tree ops[2];
6041 ops[0] = lhs;
6042 ops[1] = rhs;
6043 val = vn_nary_op_lookup_pieces (2, gimple_cond_code (last),
6044 boolean_type_node, ops,
6045 &vnresult);
6046 /* Did we get a predicated value? */
6047 if (! val && vnresult && vnresult->predicated_values)
6049 val = vn_nary_op_get_predicated_value (vnresult, bb);
6050 if (val && dump_file && (dump_flags & TDF_DETAILS))
6052 fprintf (dump_file, "Got predicated value ");
6053 print_generic_expr (dump_file, val, TDF_NONE);
6054 fprintf (dump_file, " for ");
6055 print_gimple_stmt (dump_file, last, TDF_SLIM);
6059 if (val)
6060 e = find_taken_edge (bb, val);
6061 if (! e)
6063 /* If we didn't manage to compute the taken edge then
6064 push predicated expressions for the condition itself
6065 and related conditions to the hashtables. This allows
6066 simplification of redundant conditions which is
6067 important as early cleanup. */
6068 edge true_e, false_e;
6069 extract_true_false_edges_from_block (bb, &true_e, &false_e);
6070 enum tree_code code = gimple_cond_code (last);
6071 enum tree_code icode
6072 = invert_tree_comparison (code, HONOR_NANS (lhs));
6073 tree ops[2];
6074 ops[0] = lhs;
6075 ops[1] = rhs;
6076 if (do_region
6077 && bitmap_bit_p (exit_bbs, true_e->dest->index))
6078 true_e = NULL;
6079 if (do_region
6080 && bitmap_bit_p (exit_bbs, false_e->dest->index))
6081 false_e = NULL;
6082 if (true_e)
6083 vn_nary_op_insert_pieces_predicated
6084 (2, code, boolean_type_node, ops,
6085 boolean_true_node, 0, true_e);
6086 if (false_e)
6087 vn_nary_op_insert_pieces_predicated
6088 (2, code, boolean_type_node, ops,
6089 boolean_false_node, 0, false_e);
6090 if (icode != ERROR_MARK)
6092 if (true_e)
6093 vn_nary_op_insert_pieces_predicated
6094 (2, icode, boolean_type_node, ops,
6095 boolean_false_node, 0, true_e);
6096 if (false_e)
6097 vn_nary_op_insert_pieces_predicated
6098 (2, icode, boolean_type_node, ops,
6099 boolean_true_node, 0, false_e);
6101 /* Relax for non-integers, inverted condition handled
6102 above. */
6103 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
6105 if (true_e)
6106 insert_related_predicates_on_edge (code, ops, true_e);
6107 if (false_e)
6108 insert_related_predicates_on_edge (icode, ops, false_e);
6111 break;
6113 case GIMPLE_GOTO:
6114 e = find_taken_edge (bb, vn_valueize (gimple_goto_dest (last)));
6115 break;
6116 default:
6117 e = NULL;
6119 if (e)
6121 todo = TODO_cleanup_cfg;
6122 if (!(e->flags & EDGE_EXECUTABLE))
6124 if (dump_file && (dump_flags & TDF_DETAILS))
6125 fprintf (dump_file,
6126 "marking known outgoing %sedge %d -> %d executable\n",
6127 e->flags & EDGE_DFS_BACK ? "back-" : "",
6128 e->src->index, e->dest->index);
6129 e->flags |= EDGE_EXECUTABLE;
6130 e->dest->flags |= BB_EXECUTABLE;
6132 else if (!(e->dest->flags & BB_EXECUTABLE))
6134 if (dump_file && (dump_flags & TDF_DETAILS))
6135 fprintf (dump_file,
6136 "marking destination block %d reachable\n",
6137 e->dest->index);
6138 e->dest->flags |= BB_EXECUTABLE;
6141 else if (gsi_one_before_end_p (gsi))
6143 FOR_EACH_EDGE (e, ei, bb->succs)
6145 if (!(e->flags & EDGE_EXECUTABLE))
6147 if (dump_file && (dump_flags & TDF_DETAILS))
6148 fprintf (dump_file,
6149 "marking outgoing edge %d -> %d executable\n",
6150 e->src->index, e->dest->index);
6151 e->flags |= EDGE_EXECUTABLE;
6152 e->dest->flags |= BB_EXECUTABLE;
6154 else if (!(e->dest->flags & BB_EXECUTABLE))
6156 if (dump_file && (dump_flags & TDF_DETAILS))
6157 fprintf (dump_file,
6158 "marking destination block %d reachable\n",
6159 e->dest->index);
6160 e->dest->flags |= BB_EXECUTABLE;
6165 /* Eliminate. That also pushes to avail. */
6166 if (eliminate && ! iterate)
6167 avail.eliminate_stmt (bb, &gsi);
6168 else
6169 /* If not eliminating, make all not already available defs
6170 available. */
6171 FOR_EACH_SSA_TREE_OPERAND (op, gsi_stmt (gsi), i, SSA_OP_DEF)
6172 if (! avail.eliminate_avail (bb, op))
6173 avail.eliminate_push_avail (bb, op);
6176 /* Eliminate in destination PHI arguments. Always substitute in dest
6177 PHIs, even for non-executable edges. This handles region
6178 exits PHIs. */
6179 if (!iterate && eliminate)
6180 FOR_EACH_EDGE (e, ei, bb->succs)
6181 for (gphi_iterator gsi = gsi_start_phis (e->dest);
6182 !gsi_end_p (gsi); gsi_next (&gsi))
6184 gphi *phi = gsi.phi ();
6185 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
6186 tree arg = USE_FROM_PTR (use_p);
6187 if (TREE_CODE (arg) != SSA_NAME
6188 || virtual_operand_p (arg))
6189 continue;
6190 tree sprime;
6191 if (SSA_NAME_IS_DEFAULT_DEF (arg))
6193 sprime = SSA_VAL (arg);
6194 gcc_assert (TREE_CODE (sprime) != SSA_NAME
6195 || SSA_NAME_IS_DEFAULT_DEF (sprime));
6197 else
6198 /* Look for sth available at the definition block of the argument.
6199 This avoids inconsistencies between availability there which
6200 decides if the stmt can be removed and availability at the
6201 use site. The SSA property ensures that things available
6202 at the definition are also available at uses. */
6203 sprime = avail.eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (arg)),
6204 arg);
6205 if (sprime
6206 && sprime != arg
6207 && may_propagate_copy (arg, sprime))
6208 propagate_value (use_p, sprime);
6211 vn_context_bb = NULL;
6212 return todo;
6215 /* Unwind state per basic-block. */
6217 struct unwind_state
6219 /* Times this block has been visited. */
6220 unsigned visited;
6221 /* Whether to handle this as iteration point or whether to treat
6222 incoming backedge PHI values as varying. */
6223 bool iterate;
6224 /* Maximum RPO index this block is reachable from. */
6225 int max_rpo;
6226 /* Unwind state. */
6227 void *ob_top;
6228 vn_reference_t ref_top;
6229 vn_phi_t phi_top;
6230 vn_nary_op_t nary_top;
6233 /* Unwind the RPO VN state for iteration. */
6235 static void
6236 do_unwind (unwind_state *to, int rpo_idx, rpo_elim &avail, int *bb_to_rpo)
6238 gcc_assert (to->iterate);
6239 for (; last_inserted_nary != to->nary_top;
6240 last_inserted_nary = last_inserted_nary->next)
6242 vn_nary_op_t *slot;
6243 slot = valid_info->nary->find_slot_with_hash
6244 (last_inserted_nary, last_inserted_nary->hashcode, NO_INSERT);
6245 /* Predication causes the need to restore previous state. */
6246 if ((*slot)->unwind_to)
6247 *slot = (*slot)->unwind_to;
6248 else
6249 valid_info->nary->clear_slot (slot);
6251 for (; last_inserted_phi != to->phi_top;
6252 last_inserted_phi = last_inserted_phi->next)
6254 vn_phi_t *slot;
6255 slot = valid_info->phis->find_slot_with_hash
6256 (last_inserted_phi, last_inserted_phi->hashcode, NO_INSERT);
6257 valid_info->phis->clear_slot (slot);
6259 for (; last_inserted_ref != to->ref_top;
6260 last_inserted_ref = last_inserted_ref->next)
6262 vn_reference_t *slot;
6263 slot = valid_info->references->find_slot_with_hash
6264 (last_inserted_ref, last_inserted_ref->hashcode, NO_INSERT);
6265 (*slot)->operands.release ();
6266 valid_info->references->clear_slot (slot);
6268 obstack_free (&vn_tables_obstack, to->ob_top);
6270 /* Prune [rpo_idx, ] from avail. */
6271 /* ??? This is O(number-of-values-in-region) which is
6272 O(region-size) rather than O(iteration-piece). */
6273 for (rpo_elim::rpo_avail_t::iterator i
6274 = avail.m_rpo_avail.begin ();
6275 i != avail.m_rpo_avail.end (); ++i)
6277 while (! (*i).second.is_empty ())
6279 if (bb_to_rpo[(*i).second.last ().first] < rpo_idx)
6280 break;
6281 (*i).second.pop ();
6286 /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
6287 If ITERATE is true then treat backedges optimistically as not
6288 executed and iterate. If ELIMINATE is true then perform
6289 elimination, otherwise leave that to the caller. */
6291 static unsigned
6292 do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
6293 bool iterate, bool eliminate)
6295 unsigned todo = 0;
6297 /* We currently do not support region-based iteration when
6298 elimination is requested. */
6299 gcc_assert (!entry || !iterate || !eliminate);
6300 /* When iterating we need loop info up-to-date. */
6301 gcc_assert (!iterate || !loops_state_satisfies_p (LOOPS_NEED_FIXUP));
6303 bool do_region = entry != NULL;
6304 if (!do_region)
6306 entry = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fn));
6307 exit_bbs = BITMAP_ALLOC (NULL);
6308 bitmap_set_bit (exit_bbs, EXIT_BLOCK);
6311 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fn) - NUM_FIXED_BLOCKS);
6312 int n = rev_post_order_and_mark_dfs_back_seme
6313 (fn, entry, exit_bbs, !loops_state_satisfies_p (LOOPS_NEED_FIXUP), rpo);
6314 /* rev_post_order_and_mark_dfs_back_seme fills RPO in reverse order. */
6315 for (int i = 0; i < n / 2; ++i)
6316 std::swap (rpo[i], rpo[n-i-1]);
6318 if (!do_region)
6319 BITMAP_FREE (exit_bbs);
6321 int *bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (fn));
6322 for (int i = 0; i < n; ++i)
6323 bb_to_rpo[rpo[i]] = i;
6325 unwind_state *rpo_state = XNEWVEC (unwind_state, n);
6327 rpo_elim avail (entry->dest);
6328 rpo_avail = &avail;
6330 /* Verify we have no extra entries into the region. */
6331 if (flag_checking && do_region)
6333 auto_bb_flag bb_in_region (fn);
6334 for (int i = 0; i < n; ++i)
6336 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
6337 bb->flags |= bb_in_region;
6339 /* We can't merge the first two loops because we cannot rely
6340 on EDGE_DFS_BACK for edges not within the region. But if
6341 we decide to always have the bb_in_region flag we can
6342 do the checking during the RPO walk itself (but then it's
6343 also easy to handle MEME conservatively). */
6344 for (int i = 0; i < n; ++i)
6346 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
6347 edge e;
6348 edge_iterator ei;
6349 FOR_EACH_EDGE (e, ei, bb->preds)
6350 gcc_assert (e == entry || (e->src->flags & bb_in_region));
6352 for (int i = 0; i < n; ++i)
6354 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
6355 bb->flags &= ~bb_in_region;
6359 /* Create the VN state. For the initial size of the various hashtables
6360 use a heuristic based on region size and number of SSA names. */
6361 unsigned region_size = (((unsigned HOST_WIDE_INT)n * num_ssa_names)
6362 / (n_basic_blocks_for_fn (fn) - NUM_FIXED_BLOCKS));
6363 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
6365 vn_ssa_aux_hash = new hash_table <vn_ssa_aux_hasher> (region_size * 2);
6366 gcc_obstack_init (&vn_ssa_aux_obstack);
6368 gcc_obstack_init (&vn_tables_obstack);
6369 gcc_obstack_init (&vn_tables_insert_obstack);
6370 valid_info = XCNEW (struct vn_tables_s);
6371 allocate_vn_table (valid_info, region_size);
6372 last_inserted_ref = NULL;
6373 last_inserted_phi = NULL;
6374 last_inserted_nary = NULL;
6376 vn_valueize = rpo_vn_valueize;
6378 /* Initialize the unwind state and edge/BB executable state. */
6379 bool need_max_rpo_iterate = false;
6380 for (int i = 0; i < n; ++i)
6382 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
6383 rpo_state[i].visited = 0;
6384 rpo_state[i].max_rpo = i;
6385 bb->flags &= ~BB_EXECUTABLE;
6386 bool has_backedges = false;
6387 edge e;
6388 edge_iterator ei;
6389 FOR_EACH_EDGE (e, ei, bb->preds)
6391 if (e->flags & EDGE_DFS_BACK)
6392 has_backedges = true;
6393 e->flags &= ~EDGE_EXECUTABLE;
6394 if (iterate || e == entry)
6395 continue;
6396 if (bb_to_rpo[e->src->index] > i)
6398 rpo_state[i].max_rpo = MAX (rpo_state[i].max_rpo,
6399 bb_to_rpo[e->src->index]);
6400 need_max_rpo_iterate = true;
6402 else
6403 rpo_state[i].max_rpo
6404 = MAX (rpo_state[i].max_rpo,
6405 rpo_state[bb_to_rpo[e->src->index]].max_rpo);
6407 rpo_state[i].iterate = iterate && has_backedges;
6409 entry->flags |= EDGE_EXECUTABLE;
6410 entry->dest->flags |= BB_EXECUTABLE;
6412 /* When there are irreducible regions the simplistic max_rpo computation
6413 above for the case of backedges doesn't work and we need to iterate
6414 until there are no more changes. */
6415 unsigned nit = 0;
6416 while (need_max_rpo_iterate)
6418 nit++;
6419 need_max_rpo_iterate = false;
6420 for (int i = 0; i < n; ++i)
6422 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
6423 edge e;
6424 edge_iterator ei;
6425 FOR_EACH_EDGE (e, ei, bb->preds)
6427 if (e == entry)
6428 continue;
6429 int max_rpo = MAX (rpo_state[i].max_rpo,
6430 rpo_state[bb_to_rpo[e->src->index]].max_rpo);
6431 if (rpo_state[i].max_rpo != max_rpo)
6433 rpo_state[i].max_rpo = max_rpo;
6434 need_max_rpo_iterate = true;
6439 statistics_histogram_event (cfun, "RPO max_rpo iterations", nit);
6441 /* As heuristic to improve compile-time we handle only the N innermost
6442 loops and the outermost one optimistically. */
6443 if (iterate)
6445 loop_p loop;
6446 unsigned max_depth = PARAM_VALUE (PARAM_RPO_VN_MAX_LOOP_DEPTH);
6447 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
6448 if (loop_depth (loop) > max_depth)
6449 for (unsigned i = 2;
6450 i < loop_depth (loop) - max_depth; ++i)
6452 basic_block header = superloop_at_depth (loop, i)->header;
6453 bool non_latch_backedge = false;
6454 edge e;
6455 edge_iterator ei;
6456 FOR_EACH_EDGE (e, ei, header->preds)
6457 if (e->flags & EDGE_DFS_BACK)
6459 /* There can be a non-latch backedge into the header
6460 which is part of an outer irreducible region. We
6461 cannot avoid iterating this block then. */
6462 if (!dominated_by_p (CDI_DOMINATORS,
6463 e->src, e->dest))
6465 if (dump_file && (dump_flags & TDF_DETAILS))
6466 fprintf (dump_file, "non-latch backedge %d -> %d "
6467 "forces iteration of loop %d\n",
6468 e->src->index, e->dest->index, loop->num);
6469 non_latch_backedge = true;
6471 else
6472 e->flags |= EDGE_EXECUTABLE;
6474 rpo_state[bb_to_rpo[header->index]].iterate = non_latch_backedge;
6478 uint64_t nblk = 0;
6479 int idx = 0;
6480 if (iterate)
6481 /* Go and process all blocks, iterating as necessary. */
6484 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[idx]);
6486 /* If the block has incoming backedges remember unwind state. This
6487 is required even for non-executable blocks since in irreducible
6488 regions we might reach them via the backedge and re-start iterating
6489 from there.
6490 Note we can individually mark blocks with incoming backedges to
6491 not iterate where we then handle PHIs conservatively. We do that
6492 heuristically to reduce compile-time for degenerate cases. */
6493 if (rpo_state[idx].iterate)
6495 rpo_state[idx].ob_top = obstack_alloc (&vn_tables_obstack, 0);
6496 rpo_state[idx].ref_top = last_inserted_ref;
6497 rpo_state[idx].phi_top = last_inserted_phi;
6498 rpo_state[idx].nary_top = last_inserted_nary;
6501 if (!(bb->flags & BB_EXECUTABLE))
6503 if (dump_file && (dump_flags & TDF_DETAILS))
6504 fprintf (dump_file, "Block %d: BB%d found not executable\n",
6505 idx, bb->index);
6506 idx++;
6507 continue;
6510 if (dump_file && (dump_flags & TDF_DETAILS))
6511 fprintf (dump_file, "Processing block %d: BB%d\n", idx, bb->index);
6512 nblk++;
6513 todo |= process_bb (avail, bb,
6514 rpo_state[idx].visited != 0,
6515 rpo_state[idx].iterate,
6516 iterate, eliminate, do_region, exit_bbs);
6517 rpo_state[idx].visited++;
6519 /* Verify if changed values flow over executable outgoing backedges
6520 and those change destination PHI values (that's the thing we
6521 can easily verify). Reduce over all such edges to the farthest
6522 away PHI. */
6523 int iterate_to = -1;
6524 edge_iterator ei;
6525 edge e;
6526 FOR_EACH_EDGE (e, ei, bb->succs)
6527 if ((e->flags & (EDGE_DFS_BACK|EDGE_EXECUTABLE))
6528 == (EDGE_DFS_BACK|EDGE_EXECUTABLE)
6529 && rpo_state[bb_to_rpo[e->dest->index]].iterate)
6531 int destidx = bb_to_rpo[e->dest->index];
6532 if (!rpo_state[destidx].visited)
6534 if (dump_file && (dump_flags & TDF_DETAILS))
6535 fprintf (dump_file, "Unvisited destination %d\n",
6536 e->dest->index);
6537 if (iterate_to == -1 || destidx < iterate_to)
6538 iterate_to = destidx;
6539 continue;
6541 if (dump_file && (dump_flags & TDF_DETAILS))
6542 fprintf (dump_file, "Looking for changed values of backedge"
6543 " %d->%d destination PHIs\n",
6544 e->src->index, e->dest->index);
6545 vn_context_bb = e->dest;
6546 gphi_iterator gsi;
6547 for (gsi = gsi_start_phis (e->dest);
6548 !gsi_end_p (gsi); gsi_next (&gsi))
6550 bool inserted = false;
6551 /* While we'd ideally just iterate on value changes
6552 we CSE PHIs and do that even across basic-block
6553 boundaries. So even hashtable state changes can
6554 be important (which is roughly equivalent to
6555 PHI argument value changes). To not excessively
6556 iterate because of that we track whether a PHI
6557 was CSEd to with GF_PLF_1. */
6558 bool phival_changed;
6559 if ((phival_changed = visit_phi (gsi.phi (),
6560 &inserted, false))
6561 || (inserted && gimple_plf (gsi.phi (), GF_PLF_1)))
6563 if (!phival_changed
6564 && dump_file && (dump_flags & TDF_DETAILS))
6565 fprintf (dump_file, "PHI was CSEd and hashtable "
6566 "state (changed)\n");
6567 if (iterate_to == -1 || destidx < iterate_to)
6568 iterate_to = destidx;
6569 break;
6572 vn_context_bb = NULL;
6574 if (iterate_to != -1)
6576 do_unwind (&rpo_state[iterate_to], iterate_to, avail, bb_to_rpo);
6577 idx = iterate_to;
6578 if (dump_file && (dump_flags & TDF_DETAILS))
6579 fprintf (dump_file, "Iterating to %d BB%d\n",
6580 iterate_to, rpo[iterate_to]);
6581 continue;
6584 idx++;
6586 while (idx < n);
6588 else /* !iterate */
6590 /* Process all blocks greedily with a worklist that enforces RPO
6591 processing of reachable blocks. */
6592 auto_bitmap worklist;
6593 bitmap_set_bit (worklist, 0);
6594 while (!bitmap_empty_p (worklist))
6596 int idx = bitmap_first_set_bit (worklist);
6597 bitmap_clear_bit (worklist, idx);
6598 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[idx]);
6599 gcc_assert ((bb->flags & BB_EXECUTABLE)
6600 && !rpo_state[idx].visited);
6602 if (dump_file && (dump_flags & TDF_DETAILS))
6603 fprintf (dump_file, "Processing block %d: BB%d\n", idx, bb->index);
6605 /* When we run into predecessor edges where we cannot trust its
6606 executable state mark them executable so PHI processing will
6607 be conservative.
6608 ??? Do we need to force arguments flowing over that edge
6609 to be varying or will they even always be? */
6610 edge_iterator ei;
6611 edge e;
6612 FOR_EACH_EDGE (e, ei, bb->preds)
6613 if (!(e->flags & EDGE_EXECUTABLE)
6614 && !rpo_state[bb_to_rpo[e->src->index]].visited
6615 && rpo_state[bb_to_rpo[e->src->index]].max_rpo >= (int)idx)
6617 if (dump_file && (dump_flags & TDF_DETAILS))
6618 fprintf (dump_file, "Cannot trust state of predecessor "
6619 "edge %d -> %d, marking executable\n",
6620 e->src->index, e->dest->index);
6621 e->flags |= EDGE_EXECUTABLE;
6624 nblk++;
6625 todo |= process_bb (avail, bb, false, false, false, eliminate,
6626 do_region, exit_bbs);
6627 rpo_state[idx].visited++;
6629 FOR_EACH_EDGE (e, ei, bb->succs)
6630 if ((e->flags & EDGE_EXECUTABLE)
6631 && e->dest->index != EXIT_BLOCK
6632 && (!do_region || !bitmap_bit_p (exit_bbs, e->dest->index))
6633 && !rpo_state[bb_to_rpo[e->dest->index]].visited)
6634 bitmap_set_bit (worklist, bb_to_rpo[e->dest->index]);
6638 /* If statistics or dump file active. */
6639 int nex = 0;
6640 unsigned max_visited = 1;
6641 for (int i = 0; i < n; ++i)
6643 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
6644 if (bb->flags & BB_EXECUTABLE)
6645 nex++;
6646 statistics_histogram_event (cfun, "RPO block visited times",
6647 rpo_state[i].visited);
6648 if (rpo_state[i].visited > max_visited)
6649 max_visited = rpo_state[i].visited;
6651 unsigned nvalues = 0, navail = 0;
6652 for (rpo_elim::rpo_avail_t::iterator i = avail.m_rpo_avail.begin ();
6653 i != avail.m_rpo_avail.end (); ++i)
6655 nvalues++;
6656 navail += (*i).second.length ();
6658 statistics_counter_event (cfun, "RPO blocks", n);
6659 statistics_counter_event (cfun, "RPO blocks visited", nblk);
6660 statistics_counter_event (cfun, "RPO blocks executable", nex);
6661 statistics_histogram_event (cfun, "RPO iterations", 10*nblk / nex);
6662 statistics_histogram_event (cfun, "RPO num values", nvalues);
6663 statistics_histogram_event (cfun, "RPO num avail", navail);
6664 statistics_histogram_event (cfun, "RPO num lattice",
6665 vn_ssa_aux_hash->elements ());
6666 if (dump_file && (dump_flags & (TDF_DETAILS|TDF_STATS)))
6668 fprintf (dump_file, "RPO iteration over %d blocks visited %" PRIu64
6669 " blocks in total discovering %d executable blocks iterating "
6670 "%d.%d times, a block was visited max. %u times\n",
6671 n, nblk, nex,
6672 (int)((10*nblk / nex)/10), (int)((10*nblk / nex)%10),
6673 max_visited);
6674 fprintf (dump_file, "RPO tracked %d values available at %d locations "
6675 "and %" PRIu64 " lattice elements\n",
6676 nvalues, navail, (uint64_t) vn_ssa_aux_hash->elements ());
6679 if (eliminate)
6681 /* When !iterate we already performed elimination during the RPO
6682 walk. */
6683 if (iterate)
6685 /* Elimination for region-based VN needs to be done within the
6686 RPO walk. */
6687 gcc_assert (! do_region);
6688 /* Note we can't use avail.walk here because that gets confused
6689 by the existing availability and it will be less efficient
6690 as well. */
6691 todo |= eliminate_with_rpo_vn (NULL);
6693 else
6694 todo |= avail.eliminate_cleanup (do_region);
6697 vn_valueize = NULL;
6698 rpo_avail = NULL;
6700 XDELETEVEC (bb_to_rpo);
6701 XDELETEVEC (rpo);
6702 XDELETEVEC (rpo_state);
6704 return todo;
6707 /* Region-based entry for RPO VN. Performs value-numbering and elimination
6708 on the SEME region specified by ENTRY and EXIT_BBS. */
6710 unsigned
6711 do_rpo_vn (function *fn, edge entry, bitmap exit_bbs)
6713 default_vn_walk_kind = VN_WALKREWRITE;
6714 unsigned todo = do_rpo_vn (fn, entry, exit_bbs, false, true);
6715 free_rpo_vn ();
6716 return todo;
6720 namespace {
6722 const pass_data pass_data_fre =
6724 GIMPLE_PASS, /* type */
6725 "fre", /* name */
6726 OPTGROUP_NONE, /* optinfo_flags */
6727 TV_TREE_FRE, /* tv_id */
6728 ( PROP_cfg | PROP_ssa ), /* properties_required */
6729 0, /* properties_provided */
6730 0, /* properties_destroyed */
6731 0, /* todo_flags_start */
6732 0, /* todo_flags_finish */
6735 class pass_fre : public gimple_opt_pass
6737 public:
6738 pass_fre (gcc::context *ctxt)
6739 : gimple_opt_pass (pass_data_fre, ctxt)
6742 /* opt_pass methods: */
6743 opt_pass * clone () { return new pass_fre (m_ctxt); }
6744 virtual bool gate (function *) { return flag_tree_fre != 0; }
6745 virtual unsigned int execute (function *);
6747 }; // class pass_fre
6749 unsigned int
6750 pass_fre::execute (function *fun)
6752 unsigned todo = 0;
6754 /* At -O[1g] use the cheap non-iterating mode. */
6755 calculate_dominance_info (CDI_DOMINATORS);
6756 if (optimize > 1)
6757 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
6759 default_vn_walk_kind = VN_WALKREWRITE;
6760 todo = do_rpo_vn (fun, NULL, NULL, optimize > 1, true);
6761 free_rpo_vn ();
6763 if (optimize > 1)
6764 loop_optimizer_finalize ();
6766 return todo;
6769 } // anon namespace
6771 gimple_opt_pass *
6772 make_pass_fre (gcc::context *ctxt)
6774 return new pass_fre (ctxt);
6777 #undef BB_EXECUTABLE