1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
37 #include "tree-iterator.h"
39 #include "alloc-pool.h"
40 #include "tree-pass.h"
43 #include "langhooks.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-sccvn.h"
49 /* This algorithm is based on the SCC algorithm presented by Keith
50 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
51 (http://citeseer.ist.psu.edu/41805.html). In
52 straight line code, it is equivalent to a regular hash based value
53 numbering that is performed in reverse postorder.
55 For code with cycles, there are two alternatives, both of which
56 require keeping the hashtables separate from the actual list of
57 value numbers for SSA names.
59 1. Iterate value numbering in an RPO walk of the blocks, removing
60 all the entries from the hashtable after each iteration (but
61 keeping the SSA name->value number mapping between iterations).
62 Iterate until it does not change.
64 2. Perform value numbering as part of an SCC walk on the SSA graph,
65 iterating only the cycles in the SSA graph until they do not change
66 (using a separate, optimistic hashtable for value numbering the SCC
69 The second is not just faster in practice (because most SSA graph
70 cycles do not involve all the variables in the graph), it also has
73 One of these nice properties is that when we pop an SCC off the
74 stack, we are guaranteed to have processed all the operands coming from
75 *outside of that SCC*, so we do not need to do anything special to
76 ensure they have value numbers.
78 Another nice property is that the SCC walk is done as part of a DFS
79 of the SSA graph, which makes it easy to perform combining and
80 simplifying operations at the same time.
82 The code below is deliberately written in a way that makes it easy
83 to separate the SCC walk from the other work it does.
85 In order to propagate constants through the code, we track which
86 expressions contain constants, and use those while folding. In
87 theory, we could also track expressions whose value numbers are
88 replaced, in case we end up folding based on expression
91 In order to value number memory, we assign value numbers to vuses.
92 This enables us to note that, for example, stores to the same
93 address of the same value from the same starting memory states are
97 1. We can iterate only the changing portions of the SCC's, but
98 I have not seen an SCC big enough for this to be a win.
99 2. If you differentiate between phi nodes for loops and phi nodes
100 for if-then-else, you can properly consider phi nodes in different
101 blocks for equivalence.
102 3. We could value number vuses in more cases, particularly, whole
106 /* The set of hashtables and alloc_pool's for their items. */
108 typedef struct vn_tables_s
113 struct obstack nary_obstack;
114 alloc_pool phis_pool;
115 alloc_pool references_pool;
118 static htab_t constant_to_value_id;
119 static bitmap constant_value_ids;
122 /* Valid hashtables storing information we have proven to be
125 static vn_tables_t valid_info;
127 /* Optimistic hashtables storing information we are making assumptions about
128 during iterations. */
130 static vn_tables_t optimistic_info;
132 /* Pointer to the set of hashtables that is currently being used.
133 Should always point to either the optimistic_info, or the
136 static vn_tables_t current_info;
139 /* Reverse post order index for each basic block. */
141 static int *rpo_numbers;
143 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
145 /* This represents the top of the VN lattice, which is the universal
150 /* Unique counter for our value ids. */
152 static unsigned int next_value_id;
154 /* Next DFS number and the stack for strongly connected component
157 static unsigned int next_dfs_num;
158 static VEC (tree, heap) *sccstack;
160 static bool may_insert;
163 DEF_VEC_P(vn_ssa_aux_t);
164 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
166 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
167 are allocated on an obstack for locality reasons, and to free them
168 without looping over the VEC. */
170 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
171 static struct obstack vn_ssa_aux_obstack;
173 /* Return the value numbering information for a given SSA name. */
178 vn_ssa_aux_t res = VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
179 SSA_NAME_VERSION (name));
184 /* Set the value numbering info for a given SSA name to a given
188 VN_INFO_SET (tree name, vn_ssa_aux_t value)
190 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
191 SSA_NAME_VERSION (name), value);
194 /* Initialize the value numbering info for a given SSA name.
195 This should be called just once for every SSA name. */
198 VN_INFO_GET (tree name)
200 vn_ssa_aux_t newinfo;
202 newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
203 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
204 if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
205 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
206 SSA_NAME_VERSION (name) + 1);
207 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
208 SSA_NAME_VERSION (name), newinfo);
213 /* Get the representative expression for the SSA_NAME NAME. Returns
214 the representative SSA_NAME if there is no expression associated with it. */
217 vn_get_expr_for (tree name)
219 vn_ssa_aux_t vn = VN_INFO (name);
221 tree expr = NULL_TREE;
223 if (vn->valnum == VN_TOP)
226 /* If the value-number is a constant it is the representative
228 if (TREE_CODE (vn->valnum) != SSA_NAME)
231 /* Get to the information of the value of this SSA_NAME. */
232 vn = VN_INFO (vn->valnum);
234 /* If the value-number is a constant it is the representative
236 if (TREE_CODE (vn->valnum) != SSA_NAME)
239 /* Else if we have an expression, return it. */
240 if (vn->expr != NULL_TREE)
243 /* Otherwise use the defining statement to build the expression. */
244 def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
246 /* If the value number is a default-definition or a PHI result
248 if (gimple_nop_p (def_stmt)
249 || gimple_code (def_stmt) == GIMPLE_PHI)
252 if (!is_gimple_assign (def_stmt))
255 /* FIXME tuples. This is incomplete and likely will miss some
257 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)))
260 if ((gimple_assign_rhs_code (def_stmt) == VIEW_CONVERT_EXPR
261 || gimple_assign_rhs_code (def_stmt) == REALPART_EXPR
262 || gimple_assign_rhs_code (def_stmt) == IMAGPART_EXPR)
263 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
264 expr = fold_build1 (gimple_assign_rhs_code (def_stmt),
265 gimple_expr_type (def_stmt),
266 TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0));
270 expr = fold_build1 (gimple_assign_rhs_code (def_stmt),
271 gimple_expr_type (def_stmt),
272 gimple_assign_rhs1 (def_stmt));
276 expr = fold_build2 (gimple_assign_rhs_code (def_stmt),
277 gimple_expr_type (def_stmt),
278 gimple_assign_rhs1 (def_stmt),
279 gimple_assign_rhs2 (def_stmt));
284 if (expr == NULL_TREE)
287 /* Cache the expression. */
294 /* Free a phi operation structure VP. */
299 vn_phi_t phi = (vn_phi_t) vp;
300 VEC_free (tree, heap, phi->phiargs);
303 /* Free a reference operation structure VP. */
306 free_reference (void *vp)
308 vn_reference_t vr = (vn_reference_t) vp;
309 VEC_free (vn_reference_op_s, heap, vr->operands);
312 /* Hash table equality function for vn_constant_t. */
315 vn_constant_eq (const void *p1, const void *p2)
317 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
318 const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
320 if (vc1->hashcode != vc2->hashcode)
323 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
326 /* Hash table hash function for vn_constant_t. */
329 vn_constant_hash (const void *p1)
331 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
332 return vc1->hashcode;
335 /* Lookup a value id for CONSTANT and return it. If it does not
339 get_constant_value_id (tree constant)
342 struct vn_constant_s vc;
344 vc.hashcode = vn_hash_constant_with_type (constant);
345 vc.constant = constant;
346 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
347 vc.hashcode, NO_INSERT);
349 return ((vn_constant_t)*slot)->value_id;
353 /* Lookup a value id for CONSTANT, and if it does not exist, create a
354 new one and return it. If it does exist, return it. */
357 get_or_alloc_constant_value_id (tree constant)
360 vn_constant_t vc = XNEW (struct vn_constant_s);
362 vc->hashcode = vn_hash_constant_with_type (constant);
363 vc->constant = constant;
364 slot = htab_find_slot_with_hash (constant_to_value_id, vc,
365 vc->hashcode, INSERT);
369 return ((vn_constant_t)*slot)->value_id;
371 vc->value_id = get_next_value_id ();
373 bitmap_set_bit (constant_value_ids, vc->value_id);
377 /* Return true if V is a value id for a constant. */
380 value_id_constant_p (unsigned int v)
382 return bitmap_bit_p (constant_value_ids, v);
385 /* Compare two reference operands P1 and P2 for equality. Return true if
386 they are equal, and false otherwise. */
389 vn_reference_op_eq (const void *p1, const void *p2)
391 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
392 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
394 return vro1->opcode == vro2->opcode
395 && types_compatible_p (vro1->type, vro2->type)
396 && expressions_equal_p (vro1->op0, vro2->op0)
397 && expressions_equal_p (vro1->op1, vro2->op1)
398 && expressions_equal_p (vro1->op2, vro2->op2);
401 /* Compute the hash for a reference operand VRO1. */
404 vn_reference_op_compute_hash (const vn_reference_op_t vro1)
406 hashval_t result = 0;
408 result += iterative_hash_expr (vro1->op0, vro1->opcode);
410 result += iterative_hash_expr (vro1->op1, vro1->opcode);
412 result += iterative_hash_expr (vro1->op2, vro1->opcode);
416 /* Return the hashcode for a given reference operation P1. */
419 vn_reference_hash (const void *p1)
421 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
422 return vr1->hashcode;
425 /* Compute a hash for the reference operation VR1 and return it. */
428 vn_reference_compute_hash (const vn_reference_t vr1)
432 vn_reference_op_t vro;
434 result = iterative_hash_expr (vr1->vuse, 0);
435 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
436 result += vn_reference_op_compute_hash (vro);
441 /* Return true if reference operations P1 and P2 are equivalent. This
442 means they have the same set of operands and vuses. */
445 vn_reference_eq (const void *p1, const void *p2)
448 vn_reference_op_t vro;
450 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
451 const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
452 if (vr1->hashcode != vr2->hashcode)
455 /* Early out if this is not a hash collision. */
456 if (vr1->hashcode != vr2->hashcode)
459 /* The VOP needs to be the same. */
460 if (vr1->vuse != vr2->vuse)
463 /* If the operands are the same we are done. */
464 if (vr1->operands == vr2->operands)
467 /* We require that address operands be canonicalized in a way that
468 two memory references will have the same operands if they are
470 if (VEC_length (vn_reference_op_s, vr1->operands)
471 != VEC_length (vn_reference_op_s, vr2->operands))
474 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
475 if (!vn_reference_op_eq (VEC_index (vn_reference_op_s, vr2->operands, i),
482 /* Copy the operations present in load/store REF into RESULT, a vector of
483 vn_reference_op_s's. */
486 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
488 if (TREE_CODE (ref) == TARGET_MEM_REF)
490 vn_reference_op_s temp;
493 base = TMR_SYMBOL (ref) ? TMR_SYMBOL (ref) : TMR_BASE (ref);
495 base = build_int_cst (ptr_type_node, 0);
497 memset (&temp, 0, sizeof (temp));
498 /* We do not care for spurious type qualifications. */
499 temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
500 temp.opcode = TREE_CODE (ref);
501 temp.op0 = TMR_INDEX (ref);
502 temp.op1 = TMR_STEP (ref);
503 temp.op2 = TMR_OFFSET (ref);
504 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
506 memset (&temp, 0, sizeof (temp));
507 temp.type = NULL_TREE;
508 temp.opcode = TREE_CODE (base);
510 temp.op1 = TMR_ORIGINAL (ref);
511 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
515 /* For non-calls, store the information that makes up the address. */
519 vn_reference_op_s temp;
521 memset (&temp, 0, sizeof (temp));
522 /* We do not care for spurious type qualifications. */
523 temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
524 temp.opcode = TREE_CODE (ref);
528 case ALIGN_INDIRECT_REF:
530 /* The only operand is the address, which gets its own
531 vn_reference_op_s structure. */
533 case MISALIGNED_INDIRECT_REF:
534 temp.op0 = TREE_OPERAND (ref, 1);
537 /* Record bits and position. */
538 temp.op0 = TREE_OPERAND (ref, 1);
539 temp.op1 = TREE_OPERAND (ref, 2);
542 /* The field decl is enough to unambiguously specify the field,
543 a matching type is not necessary and a mismatching type
544 is always a spurious difference. */
545 temp.type = NULL_TREE;
546 temp.op0 = TREE_OPERAND (ref, 1);
547 temp.op1 = TREE_OPERAND (ref, 2);
548 /* If this is a reference to a union member, record the union
549 member size as operand. Do so only if we are doing
550 expression insertion (during FRE), as PRE currently gets
551 confused with this. */
553 && temp.op1 == NULL_TREE
554 && TREE_CODE (DECL_CONTEXT (temp.op0)) == UNION_TYPE
555 && integer_zerop (DECL_FIELD_OFFSET (temp.op0))
556 && integer_zerop (DECL_FIELD_BIT_OFFSET (temp.op0))
557 && host_integerp (TYPE_SIZE (TREE_TYPE (temp.op0)), 0))
558 temp.op0 = TYPE_SIZE (TREE_TYPE (temp.op0));
560 case ARRAY_RANGE_REF:
562 /* Record index as operand. */
563 temp.op0 = TREE_OPERAND (ref, 1);
564 /* Record even constant lower bounds. */
565 if (TREE_OPERAND (ref, 2))
566 temp.op1 = TREE_OPERAND (ref, 2);
569 tree domain = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (ref, 0)));
571 && TYPE_MIN_VALUE (domain)
572 && !integer_zerop (TYPE_MIN_VALUE (domain)))
573 temp.op1 = TYPE_MIN_VALUE (domain);
575 temp.op2 = TREE_OPERAND (ref, 3);
593 if (is_gimple_min_invariant (ref))
599 /* These are only interesting for their operands, their
600 existence, and their type. They will never be the last
601 ref in the chain of references (IE they require an
602 operand), so we don't have to put anything
603 for op* as it will be handled by the iteration */
606 case VIEW_CONVERT_EXPR:
611 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
613 if (REFERENCE_CLASS_P (ref)
614 || (TREE_CODE (ref) == ADDR_EXPR
615 && !is_gimple_min_invariant (ref)))
616 ref = TREE_OPERAND (ref, 0);
622 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
623 operands in *OPS, the reference alias set SET and the reference type TYPE.
624 Return true if something useful was produced. */
627 ao_ref_init_from_vn_reference (ao_ref *ref,
628 alias_set_type set, tree type,
629 VEC (vn_reference_op_s, heap) *ops)
631 vn_reference_op_t op;
633 tree base = NULL_TREE;
635 HOST_WIDE_INT offset = 0;
636 HOST_WIDE_INT max_size;
637 HOST_WIDE_INT size = -1;
638 tree size_tree = NULL_TREE;
640 /* First get the final access size from just the outermost expression. */
641 op = VEC_index (vn_reference_op_s, ops, 0);
642 if (op->opcode == COMPONENT_REF)
644 if (TREE_CODE (op->op0) == INTEGER_CST)
647 size_tree = DECL_SIZE (op->op0);
649 else if (op->opcode == BIT_FIELD_REF)
653 enum machine_mode mode = TYPE_MODE (type);
655 size_tree = TYPE_SIZE (type);
657 size = GET_MODE_BITSIZE (mode);
659 if (size_tree != NULL_TREE)
661 if (!host_integerp (size_tree, 1))
664 size = TREE_INT_CST_LOW (size_tree);
667 /* Initially, maxsize is the same as the accessed element size.
668 In the following it will only grow (or become -1). */
671 /* Compute cumulative bit-offset for nested component-refs and array-refs,
672 and find the ultimate containing object. */
673 for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
677 /* These may be in the reference ops, but we cannot do anything
678 sensible with them here. */
683 /* Record the base objects. */
684 case ALIGN_INDIRECT_REF:
686 *op0_p = build1 (op->opcode, op->type, NULL_TREE);
687 op0_p = &TREE_OPERAND (*op0_p, 0);
690 case MISALIGNED_INDIRECT_REF:
691 *op0_p = build2 (MISALIGNED_INDIRECT_REF, op->type,
693 op0_p = &TREE_OPERAND (*op0_p, 0);
705 /* And now the usual component-reference style ops. */
707 offset += tree_low_cst (op->op1, 0);
712 tree field = op->op0;
713 /* We do not have a complete COMPONENT_REF tree here so we
714 cannot use component_ref_field_offset. Do the interesting
717 /* Our union trick, done for offset zero only. */
718 if (TREE_CODE (field) == INTEGER_CST)
721 || !host_integerp (DECL_FIELD_OFFSET (field), 1))
725 offset += (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field))
727 offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
732 case ARRAY_RANGE_REF:
734 /* Same for ARRAY_REFs. We do not have access to the array
735 type here, but we recorded the lower bound in op1. */
737 || !host_integerp (op->op0, 0)
738 || (op->op1 && !host_integerp (op->op1, 0))
739 || !host_integerp (TYPE_SIZE (op->type), 1))
743 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (op->op0);
745 hindex -= TREE_INT_CST_LOW (op->op1);
746 hindex *= TREE_INT_CST_LOW (TYPE_SIZE (op->type));
758 case VIEW_CONVERT_EXPR:
775 if (base == NULL_TREE)
778 ref->ref = NULL_TREE;
780 ref->offset = offset;
782 ref->max_size = max_size;
783 ref->ref_alias_set = set;
784 ref->base_alias_set = -1;
789 /* Copy the operations present in load/store/call REF into RESULT, a vector of
790 vn_reference_op_s's. */
793 copy_reference_ops_from_call (gimple call,
794 VEC(vn_reference_op_s, heap) **result)
796 vn_reference_op_s temp;
799 /* Copy the type, opcode, function being called and static chain. */
800 memset (&temp, 0, sizeof (temp));
801 temp.type = gimple_call_return_type (call);
802 temp.opcode = CALL_EXPR;
803 temp.op0 = gimple_call_fn (call);
804 temp.op1 = gimple_call_chain (call);
805 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
807 /* Copy the call arguments. As they can be references as well,
808 just chain them together. */
809 for (i = 0; i < gimple_call_num_args (call); ++i)
811 tree callarg = gimple_call_arg (call, i);
812 copy_reference_ops_from_ref (callarg, result);
816 /* Create a vector of vn_reference_op_s structures from REF, a
817 REFERENCE_CLASS_P tree. The vector is not shared. */
819 static VEC(vn_reference_op_s, heap) *
820 create_reference_ops_from_ref (tree ref)
822 VEC (vn_reference_op_s, heap) *result = NULL;
824 copy_reference_ops_from_ref (ref, &result);
828 /* Create a vector of vn_reference_op_s structures from CALL, a
829 call statement. The vector is not shared. */
831 static VEC(vn_reference_op_s, heap) *
832 create_reference_ops_from_call (gimple call)
834 VEC (vn_reference_op_s, heap) *result = NULL;
836 copy_reference_ops_from_call (call, &result);
840 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
841 *I_P to point to the last element of the replacement. */
843 vn_reference_fold_indirect (VEC (vn_reference_op_s, heap) **ops,
846 VEC(vn_reference_op_s, heap) *mem = NULL;
847 vn_reference_op_t op;
848 unsigned int i = *i_p;
851 /* Get ops for the addressed object. */
852 op = VEC_index (vn_reference_op_s, *ops, i);
853 /* ??? If this is our usual typeof &ARRAY vs. &ARRAY[0] problem, work
854 around it to avoid later ICEs. */
855 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op->op0, 0))) == ARRAY_TYPE
856 && TREE_CODE (TREE_TYPE (TREE_TYPE (op->op0))) != ARRAY_TYPE)
858 vn_reference_op_s aref;
860 aref.type = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (op->op0)));
861 aref.opcode = ARRAY_REF;
862 aref.op0 = integer_zero_node;
863 if ((dom = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (op->op0, 0))))
864 && TYPE_MIN_VALUE (dom))
865 aref.op0 = TYPE_MIN_VALUE (dom);
866 aref.op1 = NULL_TREE;
867 aref.op2 = NULL_TREE;
868 VEC_safe_push (vn_reference_op_s, heap, mem, &aref);
870 copy_reference_ops_from_ref (TREE_OPERAND (op->op0, 0), &mem);
872 /* Do the replacement - we should have at least one op in mem now. */
873 if (VEC_length (vn_reference_op_s, mem) == 1)
875 VEC_replace (vn_reference_op_s, *ops, i - 1,
876 VEC_index (vn_reference_op_s, mem, 0));
877 VEC_ordered_remove (vn_reference_op_s, *ops, i);
880 else if (VEC_length (vn_reference_op_s, mem) == 2)
882 VEC_replace (vn_reference_op_s, *ops, i - 1,
883 VEC_index (vn_reference_op_s, mem, 0));
884 VEC_replace (vn_reference_op_s, *ops, i,
885 VEC_index (vn_reference_op_s, mem, 1));
887 else if (VEC_length (vn_reference_op_s, mem) > 2)
889 VEC_replace (vn_reference_op_s, *ops, i - 1,
890 VEC_index (vn_reference_op_s, mem, 0));
891 VEC_replace (vn_reference_op_s, *ops, i,
892 VEC_index (vn_reference_op_s, mem, 1));
893 /* ??? There is no VEC_splice. */
894 for (j = 2; VEC_iterate (vn_reference_op_s, mem, j, op); j++)
895 VEC_safe_insert (vn_reference_op_s, heap, *ops, ++i, op);
900 VEC_free (vn_reference_op_s, heap, mem);
904 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
905 structures into their value numbers. This is done in-place, and
906 the vector passed in is returned. */
908 static VEC (vn_reference_op_s, heap) *
909 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
911 vn_reference_op_t vro;
914 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
916 if (vro->opcode == SSA_NAME
917 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
919 vro->op0 = SSA_VAL (vro->op0);
920 /* If it transforms from an SSA_NAME to a constant, update
922 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
923 vro->opcode = TREE_CODE (vro->op0);
924 /* If it transforms from an SSA_NAME to an address, fold with
925 a preceding indirect reference. */
926 if (i > 0 && TREE_CODE (vro->op0) == ADDR_EXPR
927 && VEC_index (vn_reference_op_s,
928 orig, i - 1)->opcode == INDIRECT_REF)
930 vn_reference_fold_indirect (&orig, &i);
934 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
935 vro->op1 = SSA_VAL (vro->op1);
936 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
937 vro->op2 = SSA_VAL (vro->op2);
943 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
945 /* Create a vector of vn_reference_op_s structures from REF, a
946 REFERENCE_CLASS_P tree. The vector is shared among all callers of
949 static VEC(vn_reference_op_s, heap) *
950 valueize_shared_reference_ops_from_ref (tree ref)
954 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
955 copy_reference_ops_from_ref (ref, &shared_lookup_references);
956 shared_lookup_references = valueize_refs (shared_lookup_references);
957 return shared_lookup_references;
960 /* Create a vector of vn_reference_op_s structures from CALL, a
961 call statement. The vector is shared among all callers of
964 static VEC(vn_reference_op_s, heap) *
965 valueize_shared_reference_ops_from_call (gimple call)
969 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
970 copy_reference_ops_from_call (call, &shared_lookup_references);
971 shared_lookup_references = valueize_refs (shared_lookup_references);
972 return shared_lookup_references;
975 /* Lookup a SCCVN reference operation VR in the current hash table.
976 Returns the resulting value number if it exists in the hash table,
977 NULL_TREE otherwise. VNRESULT will be filled in with the actual
978 vn_reference_t stored in the hashtable if something is found. */
981 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
987 slot = htab_find_slot_with_hash (current_info->references, vr,
989 if (!slot && current_info == optimistic_info)
990 slot = htab_find_slot_with_hash (valid_info->references, vr,
995 *vnresult = (vn_reference_t)*slot;
996 return ((vn_reference_t)*slot)->result;
1002 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1003 with the current VUSE and performs the expression lookup. */
1006 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
1008 vn_reference_t vr = (vn_reference_t)vr_;
1012 /* Fixup vuse and hash. */
1013 vr->hashcode = vr->hashcode - iterative_hash_expr (vr->vuse, 0);
1014 vr->vuse = SSA_VAL (vuse);
1015 vr->hashcode = vr->hashcode + iterative_hash_expr (vr->vuse, 0);
1017 hash = vr->hashcode;
1018 slot = htab_find_slot_with_hash (current_info->references, vr,
1020 if (!slot && current_info == optimistic_info)
1021 slot = htab_find_slot_with_hash (valid_info->references, vr,
1029 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1030 from the statement defining VUSE and if not successful tries to
1031 translate *REFP and VR_ through an aggregate copy at the defintion
1035 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_)
1037 vn_reference_t vr = (vn_reference_t)vr_;
1038 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1041 HOST_WIDE_INT offset, size, maxsize;
1043 base = ao_ref_base (ref);
1044 offset = ref->offset;
1046 maxsize = ref->max_size;
1048 /* If we cannot constrain the size of the reference we cannot
1049 test if anything kills it. */
1053 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1054 from that defintion.
1056 if (is_gimple_reg_type (vr->type)
1057 && is_gimple_call (def_stmt)
1058 && (fndecl = gimple_call_fndecl (def_stmt))
1059 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1060 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
1061 && integer_zerop (gimple_call_arg (def_stmt, 1))
1062 && host_integerp (gimple_call_arg (def_stmt, 2), 1)
1063 && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1065 tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1067 HOST_WIDE_INT offset2, size2, maxsize2;
1068 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1069 size2 = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2)) * 8;
1070 if ((unsigned HOST_WIDE_INT)size2 / 8
1071 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2))
1072 && operand_equal_p (base, base2, 0)
1073 && offset2 <= offset
1074 && offset2 + size2 >= offset + maxsize)
1076 tree val = fold_convert (vr->type, integer_zero_node);
1077 unsigned int value_id = get_or_alloc_constant_value_id (val);
1078 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1079 VEC_copy (vn_reference_op_s,
1080 heap, vr->operands),
1085 /* 2) Assignment from an empty CONSTRUCTOR. */
1086 else if (is_gimple_reg_type (vr->type)
1087 && gimple_assign_single_p (def_stmt)
1088 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1089 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1092 HOST_WIDE_INT offset2, size2, maxsize2;
1093 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1094 &offset2, &size2, &maxsize2);
1095 if (operand_equal_p (base, base2, 0)
1096 && offset2 <= offset
1097 && offset2 + size2 >= offset + maxsize)
1099 tree val = fold_convert (vr->type, integer_zero_node);
1100 unsigned int value_id = get_or_alloc_constant_value_id (val);
1101 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1102 VEC_copy (vn_reference_op_s,
1103 heap, vr->operands),
1108 /* For aggregate copies translate the reference through them if
1109 the copy kills ref. */
1110 else if (gimple_assign_single_p (def_stmt)
1111 && (DECL_P (gimple_assign_rhs1 (def_stmt))
1112 || INDIRECT_REF_P (gimple_assign_rhs1 (def_stmt))
1113 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1116 HOST_WIDE_INT offset2, size2, maxsize2;
1118 VEC (vn_reference_op_s, heap) *lhs = NULL, *rhs = NULL;
1119 vn_reference_op_t vro;
1122 /* See if the assignment kills REF. */
1123 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1124 &offset2, &size2, &maxsize2);
1125 if (!operand_equal_p (base, base2, 0)
1127 || offset2 + size2 < offset + maxsize)
1130 /* Find the common base of ref and the lhs. */
1131 copy_reference_ops_from_ref (gimple_assign_lhs (def_stmt), &lhs);
1132 i = VEC_length (vn_reference_op_s, vr->operands) - 1;
1133 j = VEC_length (vn_reference_op_s, lhs) - 1;
1135 && vn_reference_op_eq (VEC_index (vn_reference_op_s,
1137 VEC_index (vn_reference_op_s, lhs, j)))
1142 /* i now points to the first additional op.
1143 ??? LHS may not be completely contained in VR, one or more
1144 VIEW_CONVERT_EXPRs could be in its way. We could at least
1145 try handling outermost VIEW_CONVERT_EXPRs. */
1148 VEC_free (vn_reference_op_s, heap, lhs);
1150 /* Now re-write REF to be based on the rhs of the assignment. */
1151 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1152 /* We need to pre-pend vr->operands[0..i] to rhs. */
1153 if (i + 1 + VEC_length (vn_reference_op_s, rhs)
1154 > VEC_length (vn_reference_op_s, vr->operands))
1156 VEC (vn_reference_op_s, heap) *old = vr->operands;
1157 VEC_safe_grow (vn_reference_op_s, heap, vr->operands,
1158 i + 1 + VEC_length (vn_reference_op_s, rhs));
1159 if (old == shared_lookup_references
1160 && vr->operands != old)
1161 shared_lookup_references = NULL;
1164 VEC_truncate (vn_reference_op_s, vr->operands,
1165 i + 1 + VEC_length (vn_reference_op_s, rhs));
1166 for (j = 0; VEC_iterate (vn_reference_op_s, rhs, j, vro); ++j)
1167 VEC_replace (vn_reference_op_s, vr->operands, i + 1 + j, vro);
1168 VEC_free (vn_reference_op_s, heap, rhs);
1169 vr->hashcode = vn_reference_compute_hash (vr);
1171 /* Adjust *ref from the new operands. */
1172 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1174 gcc_assert (ref->size == r.size);
1177 /* Keep looking for the adjusted *REF / VR pair. */
1181 /* Bail out and stop walking. */
1185 /* Lookup a reference operation by it's parts, in the current hash table.
1186 Returns the resulting value number if it exists in the hash table,
1187 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1188 vn_reference_t stored in the hashtable if something is found. */
1191 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
1192 VEC (vn_reference_op_s, heap) *operands,
1193 vn_reference_t *vnresult, bool maywalk)
1195 struct vn_reference_s vr1;
1202 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1203 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1204 VEC_safe_grow (vn_reference_op_s, heap, shared_lookup_references,
1205 VEC_length (vn_reference_op_s, operands));
1206 memcpy (VEC_address (vn_reference_op_s, shared_lookup_references),
1207 VEC_address (vn_reference_op_s, operands),
1208 sizeof (vn_reference_op_s)
1209 * VEC_length (vn_reference_op_s, operands));
1210 vr1.operands = operands = shared_lookup_references
1211 = valueize_refs (shared_lookup_references);
1214 vr1.hashcode = vn_reference_compute_hash (&vr1);
1215 vn_reference_lookup_1 (&vr1, vnresult);
1222 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
1224 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1225 vn_reference_lookup_2,
1226 vn_reference_lookup_3, &vr1);
1227 if (vr1.operands != operands)
1228 VEC_free (vn_reference_op_s, heap, vr1.operands);
1232 return (*vnresult)->result;
1237 /* Lookup OP in the current hash table, and return the resulting value
1238 number if it exists in the hash table. Return NULL_TREE if it does
1239 not exist in the hash table or if the result field of the structure
1240 was NULL.. VNRESULT will be filled in with the vn_reference_t
1241 stored in the hashtable if one exists. */
1244 vn_reference_lookup (tree op, tree vuse, bool maywalk,
1245 vn_reference_t *vnresult)
1247 VEC (vn_reference_op_s, heap) *operands;
1248 struct vn_reference_s vr1;
1253 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1254 vr1.operands = operands = valueize_shared_reference_ops_from_ref (op);
1255 vr1.type = TREE_TYPE (op);
1256 vr1.set = get_alias_set (op);
1257 vr1.hashcode = vn_reference_compute_hash (&vr1);
1262 vn_reference_t wvnresult;
1264 ao_ref_init (&r, op);
1266 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1267 vn_reference_lookup_2,
1268 vn_reference_lookup_3, &vr1);
1269 if (vr1.operands != operands)
1270 VEC_free (vn_reference_op_s, heap, vr1.operands);
1274 *vnresult = wvnresult;
1275 return wvnresult->result;
1281 return vn_reference_lookup_1 (&vr1, vnresult);
1285 /* Insert OP into the current hash table with a value number of
1286 RESULT, and return the resulting reference structure we created. */
1289 vn_reference_insert (tree op, tree result, tree vuse)
1294 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1295 if (TREE_CODE (result) == SSA_NAME)
1296 vr1->value_id = VN_INFO (result)->value_id;
1298 vr1->value_id = get_or_alloc_constant_value_id (result);
1299 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1300 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1301 vr1->type = TREE_TYPE (op);
1302 vr1->set = get_alias_set (op);
1303 vr1->hashcode = vn_reference_compute_hash (vr1);
1304 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1306 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1309 /* Because we lookup stores using vuses, and value number failures
1310 using the vdefs (see visit_reference_op_store for how and why),
1311 it's possible that on failure we may try to insert an already
1312 inserted store. This is not wrong, there is no ssa name for a
1313 store that we could use as a differentiator anyway. Thus, unlike
1314 the other lookup functions, you cannot gcc_assert (!*slot)
1317 /* But free the old slot in case of a collision. */
1319 free_reference (*slot);
1325 /* Insert a reference by it's pieces into the current hash table with
1326 a value number of RESULT. Return the resulting reference
1327 structure we created. */
1330 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
1331 VEC (vn_reference_op_s, heap) *operands,
1332 tree result, unsigned int value_id)
1338 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1339 vr1->value_id = value_id;
1340 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1341 vr1->operands = valueize_refs (operands);
1344 vr1->hashcode = vn_reference_compute_hash (vr1);
1345 if (result && TREE_CODE (result) == SSA_NAME)
1346 result = SSA_VAL (result);
1347 vr1->result = result;
1349 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1352 /* At this point we should have all the things inserted that we have
1353 seen before, and we should never try inserting something that
1355 gcc_assert (!*slot);
1357 free_reference (*slot);
1363 /* Compute and return the hash value for nary operation VBO1. */
1366 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1371 for (i = 0; i < vno1->length; ++i)
1372 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1373 vno1->op[i] = SSA_VAL (vno1->op[i]);
1375 if (vno1->length == 2
1376 && commutative_tree_code (vno1->opcode)
1377 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1379 tree temp = vno1->op[0];
1380 vno1->op[0] = vno1->op[1];
1384 for (i = 0; i < vno1->length; ++i)
1385 hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
1390 /* Return the computed hashcode for nary operation P1. */
1393 vn_nary_op_hash (const void *p1)
1395 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1396 return vno1->hashcode;
1399 /* Compare nary operations P1 and P2 and return true if they are
1403 vn_nary_op_eq (const void *p1, const void *p2)
1405 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1406 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1409 if (vno1->hashcode != vno2->hashcode)
1412 if (vno1->opcode != vno2->opcode
1413 || !types_compatible_p (vno1->type, vno2->type))
1416 for (i = 0; i < vno1->length; ++i)
1417 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1423 /* Lookup a n-ary operation by its pieces and return the resulting value
1424 number if it exists in the hash table. Return NULL_TREE if it does
1425 not exist in the hash table or if the result field of the operation
1426 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1430 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
1431 tree type, tree op0, tree op1, tree op2,
1432 tree op3, vn_nary_op_t *vnresult)
1435 struct vn_nary_op_s vno1;
1439 vno1.length = length;
1445 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1446 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1448 if (!slot && current_info == optimistic_info)
1449 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1454 *vnresult = (vn_nary_op_t)*slot;
1455 return ((vn_nary_op_t)*slot)->result;
1458 /* Lookup OP in the current hash table, and return the resulting value
1459 number if it exists in the hash table. Return NULL_TREE if it does
1460 not exist in the hash table or if the result field of the operation
1461 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1465 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
1468 struct vn_nary_op_s vno1;
1473 vno1.opcode = TREE_CODE (op);
1474 vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
1475 vno1.type = TREE_TYPE (op);
1476 for (i = 0; i < vno1.length; ++i)
1477 vno1.op[i] = TREE_OPERAND (op, i);
1478 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1479 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1481 if (!slot && current_info == optimistic_info)
1482 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1487 *vnresult = (vn_nary_op_t)*slot;
1488 return ((vn_nary_op_t)*slot)->result;
1491 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1492 value number if it exists in the hash table. Return NULL_TREE if
1493 it does not exist in the hash table. VNRESULT will contain the
1494 vn_nary_op_t from the hashtable if it exists. */
1497 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
1500 struct vn_nary_op_s vno1;
1505 vno1.opcode = gimple_assign_rhs_code (stmt);
1506 vno1.length = gimple_num_ops (stmt) - 1;
1507 vno1.type = gimple_expr_type (stmt);
1508 for (i = 0; i < vno1.length; ++i)
1509 vno1.op[i] = gimple_op (stmt, i + 1);
1510 if (vno1.opcode == REALPART_EXPR
1511 || vno1.opcode == IMAGPART_EXPR
1512 || vno1.opcode == VIEW_CONVERT_EXPR)
1513 vno1.op[0] = TREE_OPERAND (vno1.op[0], 0);
1514 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1515 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1517 if (!slot && current_info == optimistic_info)
1518 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1523 *vnresult = (vn_nary_op_t)*slot;
1524 return ((vn_nary_op_t)*slot)->result;
1527 /* Insert a n-ary operation into the current hash table using it's
1528 pieces. Return the vn_nary_op_t structure we created and put in
1532 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
1533 tree type, tree op0,
1534 tree op1, tree op2, tree op3,
1536 unsigned int value_id)
1541 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1542 (sizeof (struct vn_nary_op_s)
1543 - sizeof (tree) * (4 - length)));
1544 vno1->value_id = value_id;
1545 vno1->opcode = code;
1546 vno1->length = length;
1556 vno1->result = result;
1557 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1558 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1560 gcc_assert (!*slot);
1567 /* Insert OP into the current hash table with a value number of
1568 RESULT. Return the vn_nary_op_t structure we created and put in
1572 vn_nary_op_insert (tree op, tree result)
1574 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
1579 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1580 (sizeof (struct vn_nary_op_s)
1581 - sizeof (tree) * (4 - length)));
1582 vno1->value_id = VN_INFO (result)->value_id;
1583 vno1->opcode = TREE_CODE (op);
1584 vno1->length = length;
1585 vno1->type = TREE_TYPE (op);
1586 for (i = 0; i < vno1->length; ++i)
1587 vno1->op[i] = TREE_OPERAND (op, i);
1588 vno1->result = result;
1589 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1590 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1592 gcc_assert (!*slot);
1598 /* Insert the rhs of STMT into the current hash table with a value number of
1602 vn_nary_op_insert_stmt (gimple stmt, tree result)
1604 unsigned length = gimple_num_ops (stmt) - 1;
1609 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1610 (sizeof (struct vn_nary_op_s)
1611 - sizeof (tree) * (4 - length)));
1612 vno1->value_id = VN_INFO (result)->value_id;
1613 vno1->opcode = gimple_assign_rhs_code (stmt);
1614 vno1->length = length;
1615 vno1->type = gimple_expr_type (stmt);
1616 for (i = 0; i < vno1->length; ++i)
1617 vno1->op[i] = gimple_op (stmt, i + 1);
1618 if (vno1->opcode == REALPART_EXPR
1619 || vno1->opcode == IMAGPART_EXPR
1620 || vno1->opcode == VIEW_CONVERT_EXPR)
1621 vno1->op[0] = TREE_OPERAND (vno1->op[0], 0);
1622 vno1->result = result;
1623 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1624 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1626 gcc_assert (!*slot);
1632 /* Compute a hashcode for PHI operation VP1 and return it. */
1634 static inline hashval_t
1635 vn_phi_compute_hash (vn_phi_t vp1)
1637 hashval_t result = 0;
1642 result = vp1->block->index;
1644 /* If all PHI arguments are constants we need to distinguish
1645 the PHI node via its type. */
1646 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
1647 result += (INTEGRAL_TYPE_P (type)
1648 + (INTEGRAL_TYPE_P (type)
1649 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
1651 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1653 if (phi1op == VN_TOP)
1655 result += iterative_hash_expr (phi1op, result);
1661 /* Return the computed hashcode for phi operation P1. */
1664 vn_phi_hash (const void *p1)
1666 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1667 return vp1->hashcode;
1670 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1673 vn_phi_eq (const void *p1, const void *p2)
1675 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1676 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
1678 if (vp1->hashcode != vp2->hashcode)
1681 if (vp1->block == vp2->block)
1686 /* If the PHI nodes do not have compatible types
1687 they are not the same. */
1688 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
1689 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
1692 /* Any phi in the same block will have it's arguments in the
1693 same edge order, because of how we store phi nodes. */
1694 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1696 tree phi2op = VEC_index (tree, vp2->phiargs, i);
1697 if (phi1op == VN_TOP || phi2op == VN_TOP)
1699 if (!expressions_equal_p (phi1op, phi2op))
1707 static VEC(tree, heap) *shared_lookup_phiargs;
1709 /* Lookup PHI in the current hash table, and return the resulting
1710 value number if it exists in the hash table. Return NULL_TREE if
1711 it does not exist in the hash table. */
1714 vn_phi_lookup (gimple phi)
1717 struct vn_phi_s vp1;
1720 VEC_truncate (tree, shared_lookup_phiargs, 0);
1722 /* Canonicalize the SSA_NAME's to their value number. */
1723 for (i = 0; i < gimple_phi_num_args (phi); i++)
1725 tree def = PHI_ARG_DEF (phi, i);
1726 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1727 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
1729 vp1.phiargs = shared_lookup_phiargs;
1730 vp1.block = gimple_bb (phi);
1731 vp1.hashcode = vn_phi_compute_hash (&vp1);
1732 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
1734 if (!slot && current_info == optimistic_info)
1735 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
1739 return ((vn_phi_t)*slot)->result;
1742 /* Insert PHI into the current hash table with a value number of
1746 vn_phi_insert (gimple phi, tree result)
1749 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
1751 VEC (tree, heap) *args = NULL;
1753 /* Canonicalize the SSA_NAME's to their value number. */
1754 for (i = 0; i < gimple_phi_num_args (phi); i++)
1756 tree def = PHI_ARG_DEF (phi, i);
1757 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1758 VEC_safe_push (tree, heap, args, def);
1760 vp1->value_id = VN_INFO (result)->value_id;
1761 vp1->phiargs = args;
1762 vp1->block = gimple_bb (phi);
1763 vp1->result = result;
1764 vp1->hashcode = vn_phi_compute_hash (vp1);
1766 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
1769 /* Because we iterate over phi operations more than once, it's
1770 possible the slot might already exist here, hence no assert.*/
1776 /* Print set of components in strongly connected component SCC to OUT. */
1779 print_scc (FILE *out, VEC (tree, heap) *scc)
1784 fprintf (out, "SCC consists of: ");
1785 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1787 print_generic_expr (out, var, 0);
1790 fprintf (out, "\n");
1793 /* Set the value number of FROM to TO, return true if it has changed
1797 set_ssa_val_to (tree from, tree to)
1802 && TREE_CODE (to) == SSA_NAME
1803 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
1806 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1807 and invariants. So assert that here. */
1808 gcc_assert (to != NULL_TREE
1810 || TREE_CODE (to) == SSA_NAME
1811 || is_gimple_min_invariant (to)));
1813 if (dump_file && (dump_flags & TDF_DETAILS))
1815 fprintf (dump_file, "Setting value number of ");
1816 print_generic_expr (dump_file, from, 0);
1817 fprintf (dump_file, " to ");
1818 print_generic_expr (dump_file, to, 0);
1821 currval = SSA_VAL (from);
1823 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
1825 VN_INFO (from)->valnum = to;
1826 if (dump_file && (dump_flags & TDF_DETAILS))
1827 fprintf (dump_file, " (changed)\n");
1830 if (dump_file && (dump_flags & TDF_DETAILS))
1831 fprintf (dump_file, "\n");
1835 /* Set all definitions in STMT to value number to themselves.
1836 Return true if a value number changed. */
1839 defs_to_varying (gimple stmt)
1841 bool changed = false;
1845 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1847 tree def = DEF_FROM_PTR (defp);
1849 VN_INFO (def)->use_processed = true;
1850 changed |= set_ssa_val_to (def, def);
1855 static bool expr_has_constants (tree expr);
1856 static tree valueize_expr (tree expr);
1858 /* Visit a copy between LHS and RHS, return true if the value number
1862 visit_copy (tree lhs, tree rhs)
1864 /* Follow chains of copies to their destination. */
1865 while (TREE_CODE (rhs) == SSA_NAME
1866 && SSA_VAL (rhs) != rhs)
1867 rhs = SSA_VAL (rhs);
1869 /* The copy may have a more interesting constant filled expression
1870 (we don't, since we know our RHS is just an SSA name). */
1871 if (TREE_CODE (rhs) == SSA_NAME)
1873 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1874 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1877 return set_ssa_val_to (lhs, rhs);
1880 /* Visit a unary operator RHS, value number it, and return true if the
1881 value number of LHS has changed as a result. */
1884 visit_unary_op (tree lhs, gimple stmt)
1886 bool changed = false;
1887 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1891 changed = set_ssa_val_to (lhs, result);
1895 changed = set_ssa_val_to (lhs, lhs);
1896 vn_nary_op_insert_stmt (stmt, lhs);
1902 /* Visit a binary operator RHS, value number it, and return true if the
1903 value number of LHS has changed as a result. */
1906 visit_binary_op (tree lhs, gimple stmt)
1908 bool changed = false;
1909 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1913 changed = set_ssa_val_to (lhs, result);
1917 changed = set_ssa_val_to (lhs, lhs);
1918 vn_nary_op_insert_stmt (stmt, lhs);
1924 /* Visit a call STMT storing into LHS. Return true if the value number
1925 of the LHS has changed as a result. */
1928 visit_reference_op_call (tree lhs, gimple stmt)
1930 bool changed = false;
1931 struct vn_reference_s vr1;
1933 tree vuse = gimple_vuse (stmt);
1935 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1936 vr1.operands = valueize_shared_reference_ops_from_call (stmt);
1937 vr1.type = gimple_expr_type (stmt);
1939 vr1.hashcode = vn_reference_compute_hash (&vr1);
1940 result = vn_reference_lookup_1 (&vr1, NULL);
1943 changed = set_ssa_val_to (lhs, result);
1944 if (TREE_CODE (result) == SSA_NAME
1945 && VN_INFO (result)->has_constants)
1946 VN_INFO (lhs)->has_constants = true;
1952 changed = set_ssa_val_to (lhs, lhs);
1953 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
1954 vr2->vuse = vr1.vuse;
1955 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
1956 vr2->type = vr1.type;
1958 vr2->hashcode = vr1.hashcode;
1960 slot = htab_find_slot_with_hash (current_info->references,
1961 vr2, vr2->hashcode, INSERT);
1963 free_reference (*slot);
1970 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1971 and return true if the value number of the LHS has changed as a result. */
1974 visit_reference_op_load (tree lhs, tree op, gimple stmt)
1976 bool changed = false;
1977 tree result = vn_reference_lookup (op, gimple_vuse (stmt), true, NULL);
1979 /* We handle type-punning through unions by value-numbering based
1980 on offset and size of the access. Be prepared to handle a
1981 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1983 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
1985 /* We will be setting the value number of lhs to the value number
1986 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1987 So first simplify and lookup this expression to see if it
1988 is already available. */
1989 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
1990 if ((CONVERT_EXPR_P (val)
1991 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
1992 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
1994 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
1995 if ((CONVERT_EXPR_P (tem)
1996 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
1997 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
1998 TREE_TYPE (val), tem)))
2002 if (!is_gimple_min_invariant (val)
2003 && TREE_CODE (val) != SSA_NAME)
2004 result = vn_nary_op_lookup (val, NULL);
2005 /* If the expression is not yet available, value-number lhs to
2006 a new SSA_NAME we create. */
2007 if (!result && may_insert)
2009 result = make_ssa_name (SSA_NAME_VAR (lhs), NULL);
2010 /* Initialize value-number information properly. */
2011 VN_INFO_GET (result)->valnum = result;
2012 VN_INFO (result)->value_id = get_next_value_id ();
2013 VN_INFO (result)->expr = val;
2014 VN_INFO (result)->has_constants = expr_has_constants (val);
2015 VN_INFO (result)->needs_insertion = true;
2016 /* As all "inserted" statements are singleton SCCs, insert
2017 to the valid table. This is strictly needed to
2018 avoid re-generating new value SSA_NAMEs for the same
2019 expression during SCC iteration over and over (the
2020 optimistic table gets cleared after each iteration).
2021 We do not need to insert into the optimistic table, as
2022 lookups there will fall back to the valid table. */
2023 if (current_info == optimistic_info)
2025 current_info = valid_info;
2026 vn_nary_op_insert (val, result);
2027 current_info = optimistic_info;
2030 vn_nary_op_insert (val, result);
2031 if (dump_file && (dump_flags & TDF_DETAILS))
2033 fprintf (dump_file, "Inserting name ");
2034 print_generic_expr (dump_file, result, 0);
2035 fprintf (dump_file, " for expression ");
2036 print_generic_expr (dump_file, val, 0);
2037 fprintf (dump_file, "\n");
2044 changed = set_ssa_val_to (lhs, result);
2045 if (TREE_CODE (result) == SSA_NAME
2046 && VN_INFO (result)->has_constants)
2048 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
2049 VN_INFO (lhs)->has_constants = true;
2054 changed = set_ssa_val_to (lhs, lhs);
2055 vn_reference_insert (op, lhs, gimple_vuse (stmt));
2062 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2063 and return true if the value number of the LHS has changed as a result. */
2066 visit_reference_op_store (tree lhs, tree op, gimple stmt)
2068 bool changed = false;
2070 bool resultsame = false;
2072 /* First we want to lookup using the *vuses* from the store and see
2073 if there the last store to this location with the same address
2076 The vuses represent the memory state before the store. If the
2077 memory state, address, and value of the store is the same as the
2078 last store to this location, then this store will produce the
2079 same memory state as that store.
2081 In this case the vdef versions for this store are value numbered to those
2082 vuse versions, since they represent the same memory state after
2085 Otherwise, the vdefs for the store are used when inserting into
2086 the table, since the store generates a new memory state. */
2088 result = vn_reference_lookup (lhs, gimple_vuse (stmt), false, NULL);
2092 if (TREE_CODE (result) == SSA_NAME)
2093 result = SSA_VAL (result);
2094 if (TREE_CODE (op) == SSA_NAME)
2096 resultsame = expressions_equal_p (result, op);
2099 if (!result || !resultsame)
2103 if (dump_file && (dump_flags & TDF_DETAILS))
2105 fprintf (dump_file, "No store match\n");
2106 fprintf (dump_file, "Value numbering store ");
2107 print_generic_expr (dump_file, lhs, 0);
2108 fprintf (dump_file, " to ");
2109 print_generic_expr (dump_file, op, 0);
2110 fprintf (dump_file, "\n");
2112 /* Have to set value numbers before insert, since insert is
2113 going to valueize the references in-place. */
2114 if ((vdef = gimple_vdef (stmt)))
2116 VN_INFO (vdef)->use_processed = true;
2117 changed |= set_ssa_val_to (vdef, vdef);
2120 /* Do not insert structure copies into the tables. */
2121 if (is_gimple_min_invariant (op)
2122 || is_gimple_reg (op))
2123 vn_reference_insert (lhs, op, vdef);
2127 /* We had a match, so value number the vdef to have the value
2128 number of the vuse it came from. */
2131 if (dump_file && (dump_flags & TDF_DETAILS))
2132 fprintf (dump_file, "Store matched earlier value,"
2133 "value numbering store vdefs to matching vuses.\n");
2135 def = gimple_vdef (stmt);
2136 use = gimple_vuse (stmt);
2138 VN_INFO (def)->use_processed = true;
2139 changed |= set_ssa_val_to (def, SSA_VAL (use));
2145 /* Visit and value number PHI, return true if the value number
2149 visit_phi (gimple phi)
2151 bool changed = false;
2153 tree sameval = VN_TOP;
2154 bool allsame = true;
2157 /* TODO: We could check for this in init_sccvn, and replace this
2158 with a gcc_assert. */
2159 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
2160 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2162 /* See if all non-TOP arguments have the same value. TOP is
2163 equivalent to everything, so we can ignore it. */
2164 for (i = 0; i < gimple_phi_num_args (phi); i++)
2166 tree def = PHI_ARG_DEF (phi, i);
2168 if (TREE_CODE (def) == SSA_NAME)
2169 def = SSA_VAL (def);
2172 if (sameval == VN_TOP)
2178 if (!expressions_equal_p (def, sameval))
2186 /* If all value numbered to the same value, the phi node has that
2190 if (is_gimple_min_invariant (sameval))
2192 VN_INFO (PHI_RESULT (phi))->has_constants = true;
2193 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2197 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2198 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2201 if (TREE_CODE (sameval) == SSA_NAME)
2202 return visit_copy (PHI_RESULT (phi), sameval);
2204 return set_ssa_val_to (PHI_RESULT (phi), sameval);
2207 /* Otherwise, see if it is equivalent to a phi node in this block. */
2208 result = vn_phi_lookup (phi);
2211 if (TREE_CODE (result) == SSA_NAME)
2212 changed = visit_copy (PHI_RESULT (phi), result);
2214 changed = set_ssa_val_to (PHI_RESULT (phi), result);
2218 vn_phi_insert (phi, PHI_RESULT (phi));
2219 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2220 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
2221 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2227 /* Return true if EXPR contains constants. */
2230 expr_has_constants (tree expr)
2232 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2235 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
2238 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
2239 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
2240 /* Constants inside reference ops are rarely interesting, but
2241 it can take a lot of looking to find them. */
2243 case tcc_declaration:
2246 return is_gimple_min_invariant (expr);
2251 /* Return true if STMT contains constants. */
2254 stmt_has_constants (gimple stmt)
2256 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2259 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2261 case GIMPLE_UNARY_RHS:
2262 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2264 case GIMPLE_BINARY_RHS:
2265 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2266 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
2267 case GIMPLE_SINGLE_RHS:
2268 /* Constants inside reference ops are rarely interesting, but
2269 it can take a lot of looking to find them. */
2270 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2277 /* Replace SSA_NAMES in expr with their value numbers, and return the
2279 This is performed in place. */
2282 valueize_expr (tree expr)
2284 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2287 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2288 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2289 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2292 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2293 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2294 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2295 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
2296 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
2297 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
2305 /* Simplify the binary expression RHS, and return the result if
2309 simplify_binary_expression (gimple stmt)
2311 tree result = NULL_TREE;
2312 tree op0 = gimple_assign_rhs1 (stmt);
2313 tree op1 = gimple_assign_rhs2 (stmt);
2315 /* This will not catch every single case we could combine, but will
2316 catch those with constants. The goal here is to simultaneously
2317 combine constants between expressions, but avoid infinite
2318 expansion of expressions during simplification. */
2319 if (TREE_CODE (op0) == SSA_NAME)
2321 if (VN_INFO (op0)->has_constants
2322 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
2323 op0 = valueize_expr (vn_get_expr_for (op0));
2324 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
2325 op0 = SSA_VAL (op0);
2328 if (TREE_CODE (op1) == SSA_NAME)
2330 if (VN_INFO (op1)->has_constants)
2331 op1 = valueize_expr (vn_get_expr_for (op1));
2332 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
2333 op1 = SSA_VAL (op1);
2336 /* Avoid folding if nothing changed. */
2337 if (op0 == gimple_assign_rhs1 (stmt)
2338 && op1 == gimple_assign_rhs2 (stmt))
2341 fold_defer_overflow_warnings ();
2343 result = fold_binary (gimple_assign_rhs_code (stmt),
2344 gimple_expr_type (stmt), op0, op1);
2346 STRIP_USELESS_TYPE_CONVERSION (result);
2348 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2351 /* Make sure result is not a complex expression consisting
2352 of operators of operators (IE (a + b) + (a + c))
2353 Otherwise, we will end up with unbounded expressions if
2354 fold does anything at all. */
2355 if (result && valid_gimple_rhs_p (result))
2361 /* Simplify the unary expression RHS, and return the result if
2365 simplify_unary_expression (gimple stmt)
2367 tree result = NULL_TREE;
2368 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2370 /* We handle some tcc_reference codes here that are all
2371 GIMPLE_ASSIGN_SINGLE codes. */
2372 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2373 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2374 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2375 op0 = TREE_OPERAND (op0, 0);
2377 if (TREE_CODE (op0) != SSA_NAME)
2381 if (VN_INFO (op0)->has_constants)
2382 op0 = valueize_expr (vn_get_expr_for (op0));
2383 else if (gimple_assign_cast_p (stmt)
2384 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2385 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2386 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2388 /* We want to do tree-combining on conversion-like expressions.
2389 Make sure we feed only SSA_NAMEs or constants to fold though. */
2390 tree tem = valueize_expr (vn_get_expr_for (op0));
2391 if (UNARY_CLASS_P (tem)
2392 || BINARY_CLASS_P (tem)
2393 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2394 || TREE_CODE (tem) == SSA_NAME
2395 || is_gimple_min_invariant (tem))
2399 /* Avoid folding if nothing changed, but remember the expression. */
2400 if (op0 == orig_op0)
2403 result = fold_unary_ignore_overflow (gimple_assign_rhs_code (stmt),
2404 gimple_expr_type (stmt), op0);
2407 STRIP_USELESS_TYPE_CONVERSION (result);
2408 if (valid_gimple_rhs_p (result))
2415 /* Try to simplify RHS using equivalences and constant folding. */
2418 try_to_simplify (gimple stmt)
2422 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2423 in this case, there is no point in doing extra work. */
2424 if (gimple_assign_copy_p (stmt)
2425 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2428 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2430 case tcc_declaration:
2431 tem = get_symbol_constant_value (gimple_assign_rhs1 (stmt));
2437 /* Do not do full-blown reference lookup here, but simplify
2438 reads from constant aggregates. */
2439 tem = fold_const_aggregate_ref (gimple_assign_rhs1 (stmt));
2443 /* Fallthrough for some codes that can operate on registers. */
2444 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2445 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2446 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2448 /* We could do a little more with unary ops, if they expand
2449 into binary ops, but it's debatable whether it is worth it. */
2451 return simplify_unary_expression (stmt);
2453 case tcc_comparison:
2455 return simplify_binary_expression (stmt);
2464 /* Visit and value number USE, return true if the value number
2468 visit_use (tree use)
2470 bool changed = false;
2471 gimple stmt = SSA_NAME_DEF_STMT (use);
2473 VN_INFO (use)->use_processed = true;
2475 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
2476 if (dump_file && (dump_flags & TDF_DETAILS)
2477 && !SSA_NAME_IS_DEFAULT_DEF (use))
2479 fprintf (dump_file, "Value numbering ");
2480 print_generic_expr (dump_file, use, 0);
2481 fprintf (dump_file, " stmt = ");
2482 print_gimple_stmt (dump_file, stmt, 0, 0);
2485 /* Handle uninitialized uses. */
2486 if (SSA_NAME_IS_DEFAULT_DEF (use))
2487 changed = set_ssa_val_to (use, use);
2490 if (gimple_code (stmt) == GIMPLE_PHI)
2491 changed = visit_phi (stmt);
2492 else if (!gimple_has_lhs (stmt)
2493 || gimple_has_volatile_ops (stmt)
2494 || stmt_could_throw_p (stmt))
2495 changed = defs_to_varying (stmt);
2496 else if (is_gimple_assign (stmt))
2498 tree lhs = gimple_assign_lhs (stmt);
2501 /* Shortcut for copies. Simplifying copies is pointless,
2502 since we copy the expression and value they represent. */
2503 if (gimple_assign_copy_p (stmt)
2504 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2505 && TREE_CODE (lhs) == SSA_NAME)
2507 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
2510 simplified = try_to_simplify (stmt);
2513 if (dump_file && (dump_flags & TDF_DETAILS))
2515 fprintf (dump_file, "RHS ");
2516 print_gimple_expr (dump_file, stmt, 0, 0);
2517 fprintf (dump_file, " simplified to ");
2518 print_generic_expr (dump_file, simplified, 0);
2519 if (TREE_CODE (lhs) == SSA_NAME)
2520 fprintf (dump_file, " has constants %d\n",
2521 expr_has_constants (simplified));
2523 fprintf (dump_file, "\n");
2526 /* Setting value numbers to constants will occasionally
2527 screw up phi congruence because constants are not
2528 uniquely associated with a single ssa name that can be
2531 && is_gimple_min_invariant (simplified)
2532 && TREE_CODE (lhs) == SSA_NAME)
2534 VN_INFO (lhs)->expr = simplified;
2535 VN_INFO (lhs)->has_constants = true;
2536 changed = set_ssa_val_to (lhs, simplified);
2540 && TREE_CODE (simplified) == SSA_NAME
2541 && TREE_CODE (lhs) == SSA_NAME)
2543 changed = visit_copy (lhs, simplified);
2546 else if (simplified)
2548 if (TREE_CODE (lhs) == SSA_NAME)
2550 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
2551 /* We have to unshare the expression or else
2552 valuizing may change the IL stream. */
2553 VN_INFO (lhs)->expr = unshare_expr (simplified);
2556 else if (stmt_has_constants (stmt)
2557 && TREE_CODE (lhs) == SSA_NAME)
2558 VN_INFO (lhs)->has_constants = true;
2559 else if (TREE_CODE (lhs) == SSA_NAME)
2561 /* We reset expr and constantness here because we may
2562 have been value numbering optimistically, and
2563 iterating. They may become non-constant in this case,
2564 even if they were optimistically constant. */
2566 VN_INFO (lhs)->has_constants = false;
2567 VN_INFO (lhs)->expr = NULL_TREE;
2570 if ((TREE_CODE (lhs) == SSA_NAME
2571 /* We can substitute SSA_NAMEs that are live over
2572 abnormal edges with their constant value. */
2573 && !(gimple_assign_copy_p (stmt)
2574 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2576 && is_gimple_min_invariant (simplified))
2577 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2578 /* Stores or copies from SSA_NAMEs that are live over
2579 abnormal edges are a problem. */
2580 || (gimple_assign_single_p (stmt)
2581 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2582 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))))
2583 changed = defs_to_varying (stmt);
2584 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
2586 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
2588 else if (TREE_CODE (lhs) == SSA_NAME)
2590 if ((gimple_assign_copy_p (stmt)
2591 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2593 && is_gimple_min_invariant (simplified)))
2595 VN_INFO (lhs)->has_constants = true;
2597 changed = set_ssa_val_to (lhs, simplified);
2599 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
2603 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2605 case GIMPLE_UNARY_RHS:
2606 changed = visit_unary_op (lhs, stmt);
2608 case GIMPLE_BINARY_RHS:
2609 changed = visit_binary_op (lhs, stmt);
2611 case GIMPLE_SINGLE_RHS:
2612 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2615 /* VOP-less references can go through unary case. */
2616 if ((gimple_assign_rhs_code (stmt) == REALPART_EXPR
2617 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2618 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR )
2619 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (stmt), 0)) == SSA_NAME)
2621 changed = visit_unary_op (lhs, stmt);
2625 case tcc_declaration:
2626 changed = visit_reference_op_load
2627 (lhs, gimple_assign_rhs1 (stmt), stmt);
2629 case tcc_expression:
2630 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
2632 changed = visit_unary_op (lhs, stmt);
2637 changed = defs_to_varying (stmt);
2641 changed = defs_to_varying (stmt);
2647 changed = defs_to_varying (stmt);
2649 else if (is_gimple_call (stmt))
2651 tree lhs = gimple_call_lhs (stmt);
2653 /* ??? We could try to simplify calls. */
2655 if (stmt_has_constants (stmt)
2656 && TREE_CODE (lhs) == SSA_NAME)
2657 VN_INFO (lhs)->has_constants = true;
2658 else if (TREE_CODE (lhs) == SSA_NAME)
2660 /* We reset expr and constantness here because we may
2661 have been value numbering optimistically, and
2662 iterating. They may become non-constant in this case,
2663 even if they were optimistically constant. */
2664 VN_INFO (lhs)->has_constants = false;
2665 VN_INFO (lhs)->expr = NULL_TREE;
2668 if (TREE_CODE (lhs) == SSA_NAME
2669 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2670 changed = defs_to_varying (stmt);
2671 /* ??? We should handle stores from calls. */
2672 else if (TREE_CODE (lhs) == SSA_NAME)
2674 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2675 changed = visit_reference_op_call (lhs, stmt);
2677 changed = defs_to_varying (stmt);
2680 changed = defs_to_varying (stmt);
2687 /* Compare two operands by reverse postorder index */
2690 compare_ops (const void *pa, const void *pb)
2692 const tree opa = *((const tree *)pa);
2693 const tree opb = *((const tree *)pb);
2694 gimple opstmta = SSA_NAME_DEF_STMT (opa);
2695 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
2699 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
2700 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
2701 else if (gimple_nop_p (opstmta))
2703 else if (gimple_nop_p (opstmtb))
2706 bba = gimple_bb (opstmta);
2707 bbb = gimple_bb (opstmtb);
2710 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
2718 if (gimple_code (opstmta) == GIMPLE_PHI
2719 && gimple_code (opstmtb) == GIMPLE_PHI)
2720 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
2721 else if (gimple_code (opstmta) == GIMPLE_PHI)
2723 else if (gimple_code (opstmtb) == GIMPLE_PHI)
2725 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
2726 return gimple_uid (opstmta) - gimple_uid (opstmtb);
2728 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
2730 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
2733 /* Sort an array containing members of a strongly connected component
2734 SCC so that the members are ordered by RPO number.
2735 This means that when the sort is complete, iterating through the
2736 array will give you the members in RPO order. */
2739 sort_scc (VEC (tree, heap) *scc)
2741 qsort (VEC_address (tree, scc),
2742 VEC_length (tree, scc),
2747 /* Process a strongly connected component in the SSA graph. */
2750 process_scc (VEC (tree, heap) *scc)
2752 /* If the SCC has a single member, just visit it. */
2754 if (VEC_length (tree, scc) == 1)
2756 tree use = VEC_index (tree, scc, 0);
2757 if (!VN_INFO (use)->use_processed)
2764 unsigned int iterations = 0;
2765 bool changed = true;
2767 /* Iterate over the SCC with the optimistic table until it stops
2769 current_info = optimistic_info;
2774 /* As we are value-numbering optimistically we have to
2775 clear the expression tables and the simplified expressions
2776 in each iteration until we converge. */
2777 htab_empty (optimistic_info->nary);
2778 htab_empty (optimistic_info->phis);
2779 htab_empty (optimistic_info->references);
2780 obstack_free (&optimistic_info->nary_obstack, NULL);
2781 gcc_obstack_init (&optimistic_info->nary_obstack);
2782 empty_alloc_pool (optimistic_info->phis_pool);
2783 empty_alloc_pool (optimistic_info->references_pool);
2784 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2785 VN_INFO (var)->expr = NULL_TREE;
2786 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2787 changed |= visit_use (var);
2790 statistics_histogram_event (cfun, "SCC iterations", iterations);
2792 /* Finally, visit the SCC once using the valid table. */
2793 current_info = valid_info;
2794 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2799 DEF_VEC_O(ssa_op_iter);
2800 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
2802 /* Pop the components of the found SCC for NAME off the SCC stack
2803 and process them. Returns true if all went well, false if
2804 we run into resource limits. */
2807 extract_and_process_scc_for_name (tree name)
2809 VEC (tree, heap) *scc = NULL;
2812 /* Found an SCC, pop the components off the SCC stack and
2816 x = VEC_pop (tree, sccstack);
2818 VN_INFO (x)->on_sccstack = false;
2819 VEC_safe_push (tree, heap, scc, x);
2820 } while (x != name);
2822 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2823 if (VEC_length (tree, scc)
2824 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
2827 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
2828 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
2829 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
2833 if (VEC_length (tree, scc) > 1)
2836 if (dump_file && (dump_flags & TDF_DETAILS))
2837 print_scc (dump_file, scc);
2841 VEC_free (tree, heap, scc);
2846 /* Depth first search on NAME to discover and process SCC's in the SSA
2848 Execution of this algorithm relies on the fact that the SCC's are
2849 popped off the stack in topological order.
2850 Returns true if successful, false if we stopped processing SCC's due
2851 to resource constraints. */
2856 VEC(ssa_op_iter, heap) *itervec = NULL;
2857 VEC(tree, heap) *namevec = NULL;
2858 use_operand_p usep = NULL;
2865 VN_INFO (name)->dfsnum = next_dfs_num++;
2866 VN_INFO (name)->visited = true;
2867 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
2869 VEC_safe_push (tree, heap, sccstack, name);
2870 VN_INFO (name)->on_sccstack = true;
2871 defstmt = SSA_NAME_DEF_STMT (name);
2873 /* Recursively DFS on our operands, looking for SCC's. */
2874 if (!gimple_nop_p (defstmt))
2876 /* Push a new iterator. */
2877 if (gimple_code (defstmt) == GIMPLE_PHI)
2878 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
2880 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
2883 clear_and_done_ssa_iter (&iter);
2887 /* If we are done processing uses of a name, go up the stack
2888 of iterators and process SCCs as we found them. */
2889 if (op_iter_done (&iter))
2891 /* See if we found an SCC. */
2892 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
2893 if (!extract_and_process_scc_for_name (name))
2895 VEC_free (tree, heap, namevec);
2896 VEC_free (ssa_op_iter, heap, itervec);
2900 /* Check if we are done. */
2901 if (VEC_empty (tree, namevec))
2903 VEC_free (tree, heap, namevec);
2904 VEC_free (ssa_op_iter, heap, itervec);
2908 /* Restore the last use walker and continue walking there. */
2910 name = VEC_pop (tree, namevec);
2911 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
2912 sizeof (ssa_op_iter));
2913 VEC_pop (ssa_op_iter, itervec);
2914 goto continue_walking;
2917 use = USE_FROM_PTR (usep);
2919 /* Since we handle phi nodes, we will sometimes get
2920 invariants in the use expression. */
2921 if (TREE_CODE (use) == SSA_NAME)
2923 if (! (VN_INFO (use)->visited))
2925 /* Recurse by pushing the current use walking state on
2926 the stack and starting over. */
2927 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
2928 VEC_safe_push(tree, heap, namevec, name);
2933 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
2934 VN_INFO (use)->low);
2936 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
2937 && VN_INFO (use)->on_sccstack)
2939 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
2940 VN_INFO (name)->low);
2944 usep = op_iter_next_use (&iter);
2948 /* Allocate a value number table. */
2951 allocate_vn_table (vn_tables_t table)
2953 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
2954 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
2955 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
2958 gcc_obstack_init (&table->nary_obstack);
2959 table->phis_pool = create_alloc_pool ("VN phis",
2960 sizeof (struct vn_phi_s),
2962 table->references_pool = create_alloc_pool ("VN references",
2963 sizeof (struct vn_reference_s),
2967 /* Free a value number table. */
2970 free_vn_table (vn_tables_t table)
2972 htab_delete (table->phis);
2973 htab_delete (table->nary);
2974 htab_delete (table->references);
2975 obstack_free (&table->nary_obstack, NULL);
2976 free_alloc_pool (table->phis_pool);
2977 free_alloc_pool (table->references_pool);
2985 int *rpo_numbers_temp;
2987 calculate_dominance_info (CDI_DOMINATORS);
2989 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
2992 constant_value_ids = BITMAP_ALLOC (NULL);
2997 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
2998 /* VEC_alloc doesn't actually grow it to the right size, it just
2999 preallocates the space to do so. */
3000 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
3001 gcc_obstack_init (&vn_ssa_aux_obstack);
3003 shared_lookup_phiargs = NULL;
3004 shared_lookup_references = NULL;
3005 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3006 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3007 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
3009 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3010 the i'th block in RPO order is bb. We want to map bb's to RPO
3011 numbers, so we need to rearrange this array. */
3012 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
3013 rpo_numbers[rpo_numbers_temp[j]] = j;
3015 XDELETE (rpo_numbers_temp);
3017 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
3019 /* Create the VN_INFO structures, and initialize value numbers to
3021 for (i = 0; i < num_ssa_names; i++)
3023 tree name = ssa_name (i);
3026 VN_INFO_GET (name)->valnum = VN_TOP;
3027 VN_INFO (name)->expr = NULL_TREE;
3028 VN_INFO (name)->value_id = 0;
3032 renumber_gimple_stmt_uids ();
3034 /* Create the valid and optimistic value numbering tables. */
3035 valid_info = XCNEW (struct vn_tables_s);
3036 allocate_vn_table (valid_info);
3037 optimistic_info = XCNEW (struct vn_tables_s);
3038 allocate_vn_table (optimistic_info);
3046 htab_delete (constant_to_value_id);
3047 BITMAP_FREE (constant_value_ids);
3048 VEC_free (tree, heap, shared_lookup_phiargs);
3049 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
3050 XDELETEVEC (rpo_numbers);
3052 for (i = 0; i < num_ssa_names; i++)
3054 tree name = ssa_name (i);
3056 && VN_INFO (name)->needs_insertion)
3057 release_ssa_name (name);
3059 obstack_free (&vn_ssa_aux_obstack, NULL);
3060 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
3062 VEC_free (tree, heap, sccstack);
3063 free_vn_table (valid_info);
3064 XDELETE (valid_info);
3065 free_vn_table (optimistic_info);
3066 XDELETE (optimistic_info);
3069 /* Set the value ids in the valid hash tables. */
3072 set_hashtable_value_ids (void)
3079 /* Now set the value ids of the things we had put in the hash
3082 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
3083 vno, vn_nary_op_t, hi)
3087 if (TREE_CODE (vno->result) == SSA_NAME)
3088 vno->value_id = VN_INFO (vno->result)->value_id;
3089 else if (is_gimple_min_invariant (vno->result))
3090 vno->value_id = get_or_alloc_constant_value_id (vno->result);
3094 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
3099 if (TREE_CODE (vp->result) == SSA_NAME)
3100 vp->value_id = VN_INFO (vp->result)->value_id;
3101 else if (is_gimple_min_invariant (vp->result))
3102 vp->value_id = get_or_alloc_constant_value_id (vp->result);
3106 FOR_EACH_HTAB_ELEMENT (valid_info->references,
3107 vr, vn_reference_t, hi)
3111 if (TREE_CODE (vr->result) == SSA_NAME)
3112 vr->value_id = VN_INFO (vr->result)->value_id;
3113 else if (is_gimple_min_invariant (vr->result))
3114 vr->value_id = get_or_alloc_constant_value_id (vr->result);
3119 /* Do SCCVN. Returns true if it finished, false if we bailed out
3120 due to resource constraints. */
3123 run_scc_vn (bool may_insert_arg)
3127 bool changed = true;
3129 may_insert = may_insert_arg;
3132 current_info = valid_info;
3134 for (param = DECL_ARGUMENTS (current_function_decl);
3136 param = TREE_CHAIN (param))
3138 if (gimple_default_def (cfun, param) != NULL)
3140 tree def = gimple_default_def (cfun, param);
3141 VN_INFO (def)->valnum = def;
3145 for (i = 1; i < num_ssa_names; ++i)
3147 tree name = ssa_name (i);
3149 && VN_INFO (name)->visited == false
3150 && !has_zero_uses (name))
3159 /* Initialize the value ids. */
3161 for (i = 1; i < num_ssa_names; ++i)
3163 tree name = ssa_name (i);
3167 info = VN_INFO (name);
3168 if (info->valnum == name
3169 || info->valnum == VN_TOP)
3170 info->value_id = get_next_value_id ();
3171 else if (is_gimple_min_invariant (info->valnum))
3172 info->value_id = get_or_alloc_constant_value_id (info->valnum);
3175 /* Propagate until they stop changing. */
3179 for (i = 1; i < num_ssa_names; ++i)
3181 tree name = ssa_name (i);
3185 info = VN_INFO (name);
3186 if (TREE_CODE (info->valnum) == SSA_NAME
3187 && info->valnum != name
3188 && info->value_id != VN_INFO (info->valnum)->value_id)
3191 info->value_id = VN_INFO (info->valnum)->value_id;
3196 set_hashtable_value_ids ();
3198 if (dump_file && (dump_flags & TDF_DETAILS))
3200 fprintf (dump_file, "Value numbers:\n");
3201 for (i = 0; i < num_ssa_names; i++)
3203 tree name = ssa_name (i);
3205 && VN_INFO (name)->visited
3206 && SSA_VAL (name) != name)
3208 print_generic_expr (dump_file, name, 0);
3209 fprintf (dump_file, " = ");
3210 print_generic_expr (dump_file, SSA_VAL (name), 0);
3211 fprintf (dump_file, "\n");
3220 /* Return the maximum value id we have ever seen. */
3223 get_max_value_id (void)
3225 return next_value_id;
3228 /* Return the next unique value id. */
3231 get_next_value_id (void)
3233 return next_value_id++;
3237 /* Compare two expressions E1 and E2 and return true if they are equal. */
3240 expressions_equal_p (tree e1, tree e2)
3242 /* The obvious case. */
3246 /* If only one of them is null, they cannot be equal. */
3250 /* Recurse on elements of lists. */
3251 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
3255 for (lop1 = e1, lop2 = e2;
3257 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
3261 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
3267 /* Now perform the actual comparison. */
3268 if (TREE_CODE (e1) == TREE_CODE (e2)
3269 && operand_equal_p (e1, e2, OEP_PURE_SAME))
3276 /* Return true if the nary operation NARY may trap. This is a copy
3277 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
3280 vn_nary_may_trap (vn_nary_op_t nary)
3284 bool honor_nans = false;
3285 bool honor_snans = false;
3286 bool fp_operation = false;
3287 bool honor_trapv = false;
3291 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
3292 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
3293 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
3296 fp_operation = FLOAT_TYPE_P (type);
3299 honor_nans = flag_trapping_math && !flag_finite_math_only;
3300 honor_snans = flag_signaling_nans != 0;
3302 else if (INTEGRAL_TYPE_P (type)
3303 && TYPE_OVERFLOW_TRAPS (type))
3307 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
3309 honor_nans, honor_snans, rhs2,
3315 for (i = 0; i < nary->length; ++i)
3316 if (tree_could_trap_p (nary->op[i]))