1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
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"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
37 #include "tree-iterator.h"
38 #include "alloc-pool.h"
39 #include "tree-pass.h"
42 #include "langhooks.h"
45 #include "tree-ssa-propagate.h"
46 #include "tree-ssa-sccvn.h"
47 #include "gimple-fold.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;
161 DEF_VEC_P(vn_ssa_aux_t);
162 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
164 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
165 are allocated on an obstack for locality reasons, and to free them
166 without looping over the VEC. */
168 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
169 static struct obstack vn_ssa_aux_obstack;
171 /* Return the value numbering information for a given SSA name. */
176 vn_ssa_aux_t res = VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
177 SSA_NAME_VERSION (name));
178 gcc_checking_assert (res);
182 /* Set the value numbering info for a given SSA name to a given
186 VN_INFO_SET (tree name, vn_ssa_aux_t value)
188 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
189 SSA_NAME_VERSION (name), value);
192 /* Initialize the value numbering info for a given SSA name.
193 This should be called just once for every SSA name. */
196 VN_INFO_GET (tree name)
198 vn_ssa_aux_t newinfo;
200 newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
201 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
202 if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
203 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
204 SSA_NAME_VERSION (name) + 1);
205 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
206 SSA_NAME_VERSION (name), newinfo);
211 /* Get the representative expression for the SSA_NAME NAME. Returns
212 the representative SSA_NAME if there is no expression associated with it. */
215 vn_get_expr_for (tree name)
217 vn_ssa_aux_t vn = VN_INFO (name);
219 tree expr = NULL_TREE;
222 if (vn->valnum == VN_TOP)
225 /* If the value-number is a constant it is the representative
227 if (TREE_CODE (vn->valnum) != SSA_NAME)
230 /* Get to the information of the value of this SSA_NAME. */
231 vn = VN_INFO (vn->valnum);
233 /* If the value-number is a constant it is the representative
235 if (TREE_CODE (vn->valnum) != SSA_NAME)
238 /* Else if we have an expression, return it. */
239 if (vn->expr != NULL_TREE)
242 /* Otherwise use the defining statement to build the expression. */
243 def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
245 /* If the value number is not an assignment use it directly. */
246 if (!is_gimple_assign (def_stmt))
249 /* FIXME tuples. This is incomplete and likely will miss some
251 code = gimple_assign_rhs_code (def_stmt);
252 switch (TREE_CODE_CLASS (code))
255 if ((code == REALPART_EXPR
256 || code == IMAGPART_EXPR
257 || code == VIEW_CONVERT_EXPR)
258 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt),
260 expr = fold_build1 (code,
261 gimple_expr_type (def_stmt),
262 TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0));
266 expr = fold_build1 (code,
267 gimple_expr_type (def_stmt),
268 gimple_assign_rhs1 (def_stmt));
272 expr = fold_build2 (code,
273 gimple_expr_type (def_stmt),
274 gimple_assign_rhs1 (def_stmt),
275 gimple_assign_rhs2 (def_stmt));
278 case tcc_exceptional:
279 if (code == CONSTRUCTOR
281 (TREE_TYPE (gimple_assign_rhs1 (def_stmt))) == VECTOR_TYPE)
282 expr = gimple_assign_rhs1 (def_stmt);
287 if (expr == NULL_TREE)
290 /* Cache the expression. */
297 /* Free a phi operation structure VP. */
302 vn_phi_t phi = (vn_phi_t) vp;
303 VEC_free (tree, heap, phi->phiargs);
306 /* Free a reference operation structure VP. */
309 free_reference (void *vp)
311 vn_reference_t vr = (vn_reference_t) vp;
312 VEC_free (vn_reference_op_s, heap, vr->operands);
315 /* Hash table equality function for vn_constant_t. */
318 vn_constant_eq (const void *p1, const void *p2)
320 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
321 const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
323 if (vc1->hashcode != vc2->hashcode)
326 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
329 /* Hash table hash function for vn_constant_t. */
332 vn_constant_hash (const void *p1)
334 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
335 return vc1->hashcode;
338 /* Lookup a value id for CONSTANT and return it. If it does not
342 get_constant_value_id (tree constant)
345 struct vn_constant_s vc;
347 vc.hashcode = vn_hash_constant_with_type (constant);
348 vc.constant = constant;
349 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
350 vc.hashcode, NO_INSERT);
352 return ((vn_constant_t)*slot)->value_id;
356 /* Lookup a value id for CONSTANT, and if it does not exist, create a
357 new one and return it. If it does exist, return it. */
360 get_or_alloc_constant_value_id (tree constant)
363 struct vn_constant_s vc;
366 vc.hashcode = vn_hash_constant_with_type (constant);
367 vc.constant = constant;
368 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
369 vc.hashcode, INSERT);
371 return ((vn_constant_t)*slot)->value_id;
373 vcp = XNEW (struct vn_constant_s);
374 vcp->hashcode = vc.hashcode;
375 vcp->constant = constant;
376 vcp->value_id = get_next_value_id ();
377 *slot = (void *) vcp;
378 bitmap_set_bit (constant_value_ids, vcp->value_id);
379 return vcp->value_id;
382 /* Return true if V is a value id for a constant. */
385 value_id_constant_p (unsigned int v)
387 return bitmap_bit_p (constant_value_ids, v);
390 /* Compare two reference operands P1 and P2 for equality. Return true if
391 they are equal, and false otherwise. */
394 vn_reference_op_eq (const void *p1, const void *p2)
396 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
397 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
399 return (vro1->opcode == vro2->opcode
400 /* We do not care for differences in type qualification. */
401 && (vro1->type == vro2->type
402 || (vro1->type && vro2->type
403 && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type),
404 TYPE_MAIN_VARIANT (vro2->type))))
405 && expressions_equal_p (vro1->op0, vro2->op0)
406 && expressions_equal_p (vro1->op1, vro2->op1)
407 && expressions_equal_p (vro1->op2, vro2->op2));
410 /* Compute the hash for a reference operand VRO1. */
413 vn_reference_op_compute_hash (const vn_reference_op_t vro1, hashval_t result)
415 result = iterative_hash_hashval_t (vro1->opcode, result);
417 result = iterative_hash_expr (vro1->op0, result);
419 result = iterative_hash_expr (vro1->op1, result);
421 result = iterative_hash_expr (vro1->op2, result);
425 /* Return the hashcode for a given reference operation P1. */
428 vn_reference_hash (const void *p1)
430 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
431 return vr1->hashcode;
434 /* Compute a hash for the reference operation VR1 and return it. */
437 vn_reference_compute_hash (const vn_reference_t vr1)
439 hashval_t result = 0;
441 vn_reference_op_t vro;
442 HOST_WIDE_INT off = -1;
445 FOR_EACH_VEC_ELT (vn_reference_op_s, vr1->operands, i, vro)
447 if (vro->opcode == MEM_REF)
449 else if (vro->opcode != ADDR_EXPR)
461 result = iterative_hash_hashval_t (off, result);
464 && vro->opcode == ADDR_EXPR)
468 tree op = TREE_OPERAND (vro->op0, 0);
469 result = iterative_hash_hashval_t (TREE_CODE (op), result);
470 result = iterative_hash_expr (op, result);
474 result = vn_reference_op_compute_hash (vro, result);
478 result += SSA_NAME_VERSION (vr1->vuse);
483 /* Return true if reference operations P1 and P2 are equivalent. This
484 means they have the same set of operands and vuses. */
487 vn_reference_eq (const void *p1, const void *p2)
491 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
492 const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
493 if (vr1->hashcode != vr2->hashcode)
496 /* Early out if this is not a hash collision. */
497 if (vr1->hashcode != vr2->hashcode)
500 /* The VOP needs to be the same. */
501 if (vr1->vuse != vr2->vuse)
504 /* If the operands are the same we are done. */
505 if (vr1->operands == vr2->operands)
508 if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
511 if (INTEGRAL_TYPE_P (vr1->type)
512 && INTEGRAL_TYPE_P (vr2->type))
514 if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
517 else if (INTEGRAL_TYPE_P (vr1->type)
518 && (TYPE_PRECISION (vr1->type)
519 != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
521 else if (INTEGRAL_TYPE_P (vr2->type)
522 && (TYPE_PRECISION (vr2->type)
523 != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
530 HOST_WIDE_INT off1 = 0, off2 = 0;
531 vn_reference_op_t vro1, vro2;
532 vn_reference_op_s tem1, tem2;
533 bool deref1 = false, deref2 = false;
534 for (; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro1); i++)
536 if (vro1->opcode == MEM_REF)
542 for (; VEC_iterate (vn_reference_op_s, vr2->operands, j, vro2); j++)
544 if (vro2->opcode == MEM_REF)
552 if (deref1 && vro1->opcode == ADDR_EXPR)
554 memset (&tem1, 0, sizeof (tem1));
555 tem1.op0 = TREE_OPERAND (vro1->op0, 0);
556 tem1.type = TREE_TYPE (tem1.op0);
557 tem1.opcode = TREE_CODE (tem1.op0);
561 if (deref2 && vro2->opcode == ADDR_EXPR)
563 memset (&tem2, 0, sizeof (tem2));
564 tem2.op0 = TREE_OPERAND (vro2->op0, 0);
565 tem2.type = TREE_TYPE (tem2.op0);
566 tem2.opcode = TREE_CODE (tem2.op0);
570 if (deref1 != deref2)
572 if (!vn_reference_op_eq (vro1, vro2))
577 while (VEC_length (vn_reference_op_s, vr1->operands) != i
578 || VEC_length (vn_reference_op_s, vr2->operands) != j);
583 /* Copy the operations present in load/store REF into RESULT, a vector of
584 vn_reference_op_s's. */
587 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
589 if (TREE_CODE (ref) == TARGET_MEM_REF)
591 vn_reference_op_s temp;
593 memset (&temp, 0, sizeof (temp));
594 temp.type = TREE_TYPE (ref);
595 temp.opcode = TREE_CODE (ref);
596 temp.op0 = TMR_INDEX (ref);
597 temp.op1 = TMR_STEP (ref);
598 temp.op2 = TMR_OFFSET (ref);
600 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
602 memset (&temp, 0, sizeof (temp));
603 temp.type = NULL_TREE;
604 temp.opcode = ERROR_MARK;
605 temp.op0 = TMR_INDEX2 (ref);
607 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
609 memset (&temp, 0, sizeof (temp));
610 temp.type = NULL_TREE;
611 temp.opcode = TREE_CODE (TMR_BASE (ref));
612 temp.op0 = TMR_BASE (ref);
614 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
618 /* For non-calls, store the information that makes up the address. */
622 vn_reference_op_s temp;
624 memset (&temp, 0, sizeof (temp));
625 temp.type = TREE_TYPE (ref);
626 temp.opcode = TREE_CODE (ref);
632 /* The base address gets its own vn_reference_op_s structure. */
633 temp.op0 = TREE_OPERAND (ref, 1);
634 if (host_integerp (TREE_OPERAND (ref, 1), 0))
635 temp.off = TREE_INT_CST_LOW (TREE_OPERAND (ref, 1));
638 /* Record bits and position. */
639 temp.op0 = TREE_OPERAND (ref, 1);
640 temp.op1 = TREE_OPERAND (ref, 2);
643 /* The field decl is enough to unambiguously specify the field,
644 a matching type is not necessary and a mismatching type
645 is always a spurious difference. */
646 temp.type = NULL_TREE;
647 temp.op0 = TREE_OPERAND (ref, 1);
648 temp.op1 = TREE_OPERAND (ref, 2);
650 tree this_offset = component_ref_field_offset (ref);
652 && TREE_CODE (this_offset) == INTEGER_CST)
654 tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
655 if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0)
658 = double_int_add (tree_to_double_int (this_offset),
660 (tree_to_double_int (bit_offset),
662 ? 3 : exact_log2 (BITS_PER_UNIT),
663 HOST_BITS_PER_DOUBLE_INT, true));
664 if (double_int_fits_in_shwi_p (off))
670 case ARRAY_RANGE_REF:
672 /* Record index as operand. */
673 temp.op0 = TREE_OPERAND (ref, 1);
674 /* Always record lower bounds and element size. */
675 temp.op1 = array_ref_low_bound (ref);
676 temp.op2 = array_ref_element_size (ref);
677 if (TREE_CODE (temp.op0) == INTEGER_CST
678 && TREE_CODE (temp.op1) == INTEGER_CST
679 && TREE_CODE (temp.op2) == INTEGER_CST)
681 double_int off = tree_to_double_int (temp.op0);
682 off = double_int_add (off,
684 (tree_to_double_int (temp.op1)));
685 off = double_int_mul (off, tree_to_double_int (temp.op2));
686 if (double_int_fits_in_shwi_p (off))
691 if (DECL_HARD_REGISTER (ref))
700 /* Canonicalize decls to MEM[&decl] which is what we end up with
701 when valueizing MEM[ptr] with ptr = &decl. */
702 temp.opcode = MEM_REF;
703 temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0);
705 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
706 temp.opcode = ADDR_EXPR;
707 temp.op0 = build_fold_addr_expr (ref);
708 temp.type = TREE_TYPE (temp.op0);
722 if (is_gimple_min_invariant (ref))
728 /* These are only interesting for their operands, their
729 existence, and their type. They will never be the last
730 ref in the chain of references (IE they require an
731 operand), so we don't have to put anything
732 for op* as it will be handled by the iteration */
734 case VIEW_CONVERT_EXPR:
738 /* This is only interesting for its constant offset. */
739 temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
744 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
746 if (REFERENCE_CLASS_P (ref)
747 || (TREE_CODE (ref) == ADDR_EXPR
748 && !is_gimple_min_invariant (ref)))
749 ref = TREE_OPERAND (ref, 0);
755 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
756 operands in *OPS, the reference alias set SET and the reference type TYPE.
757 Return true if something useful was produced. */
760 ao_ref_init_from_vn_reference (ao_ref *ref,
761 alias_set_type set, tree type,
762 VEC (vn_reference_op_s, heap) *ops)
764 vn_reference_op_t op;
766 tree base = NULL_TREE;
768 HOST_WIDE_INT offset = 0;
769 HOST_WIDE_INT max_size;
770 HOST_WIDE_INT size = -1;
771 tree size_tree = NULL_TREE;
772 alias_set_type base_alias_set = -1;
774 /* First get the final access size from just the outermost expression. */
775 op = VEC_index (vn_reference_op_s, ops, 0);
776 if (op->opcode == COMPONENT_REF)
777 size_tree = DECL_SIZE (op->op0);
778 else if (op->opcode == BIT_FIELD_REF)
782 enum machine_mode mode = TYPE_MODE (type);
784 size_tree = TYPE_SIZE (type);
786 size = GET_MODE_BITSIZE (mode);
788 if (size_tree != NULL_TREE)
790 if (!host_integerp (size_tree, 1))
793 size = TREE_INT_CST_LOW (size_tree);
796 /* Initially, maxsize is the same as the accessed element size.
797 In the following it will only grow (or become -1). */
800 /* Compute cumulative bit-offset for nested component-refs and array-refs,
801 and find the ultimate containing object. */
802 FOR_EACH_VEC_ELT (vn_reference_op_s, ops, i, op)
806 /* These may be in the reference ops, but we cannot do anything
807 sensible with them here. */
809 /* Apart from ADDR_EXPR arguments to MEM_REF. */
810 if (base != NULL_TREE
811 && TREE_CODE (base) == MEM_REF
813 && DECL_P (TREE_OPERAND (op->op0, 0)))
815 vn_reference_op_t pop = VEC_index (vn_reference_op_s, ops, i-1);
816 base = TREE_OPERAND (op->op0, 0);
823 offset += pop->off * BITS_PER_UNIT;
831 /* Record the base objects. */
833 base_alias_set = get_deref_alias_set (op->op0);
834 *op0_p = build2 (MEM_REF, op->type,
836 op0_p = &TREE_OPERAND (*op0_p, 0);
847 /* And now the usual component-reference style ops. */
849 offset += tree_low_cst (op->op1, 0);
854 tree field = op->op0;
855 /* We do not have a complete COMPONENT_REF tree here so we
856 cannot use component_ref_field_offset. Do the interesting
860 || !host_integerp (DECL_FIELD_OFFSET (field), 1))
864 offset += (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field))
866 offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
871 case ARRAY_RANGE_REF:
873 /* We recorded the lower bound and the element size. */
874 if (!host_integerp (op->op0, 0)
875 || !host_integerp (op->op1, 0)
876 || !host_integerp (op->op2, 0))
880 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (op->op0);
881 hindex -= TREE_INT_CST_LOW (op->op1);
882 hindex *= TREE_INT_CST_LOW (op->op2);
883 hindex *= BITS_PER_UNIT;
895 case VIEW_CONVERT_EXPR:
912 if (base == NULL_TREE)
915 ref->ref = NULL_TREE;
917 ref->offset = offset;
919 ref->max_size = max_size;
920 ref->ref_alias_set = set;
921 if (base_alias_set != -1)
922 ref->base_alias_set = base_alias_set;
924 ref->base_alias_set = get_alias_set (base);
925 /* We discount volatiles from value-numbering elsewhere. */
926 ref->volatile_p = false;
931 /* Copy the operations present in load/store/call REF into RESULT, a vector of
932 vn_reference_op_s's. */
935 copy_reference_ops_from_call (gimple call,
936 VEC(vn_reference_op_s, heap) **result)
938 vn_reference_op_s temp;
941 /* Copy the type, opcode, function being called and static chain. */
942 memset (&temp, 0, sizeof (temp));
943 temp.type = gimple_call_return_type (call);
944 temp.opcode = CALL_EXPR;
945 temp.op0 = gimple_call_fn (call);
946 temp.op1 = gimple_call_chain (call);
948 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
950 /* Copy the call arguments. As they can be references as well,
951 just chain them together. */
952 for (i = 0; i < gimple_call_num_args (call); ++i)
954 tree callarg = gimple_call_arg (call, i);
955 copy_reference_ops_from_ref (callarg, result);
959 /* Create a vector of vn_reference_op_s structures from REF, a
960 REFERENCE_CLASS_P tree. The vector is not shared. */
962 static VEC(vn_reference_op_s, heap) *
963 create_reference_ops_from_ref (tree ref)
965 VEC (vn_reference_op_s, heap) *result = NULL;
967 copy_reference_ops_from_ref (ref, &result);
971 /* Create a vector of vn_reference_op_s structures from CALL, a
972 call statement. The vector is not shared. */
974 static VEC(vn_reference_op_s, heap) *
975 create_reference_ops_from_call (gimple call)
977 VEC (vn_reference_op_s, heap) *result = NULL;
979 copy_reference_ops_from_call (call, &result);
983 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
984 *I_P to point to the last element of the replacement. */
986 vn_reference_fold_indirect (VEC (vn_reference_op_s, heap) **ops,
989 unsigned int i = *i_p;
990 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
991 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
993 HOST_WIDE_INT addr_offset;
995 /* The only thing we have to do is from &OBJ.foo.bar add the offset
996 from .foo.bar to the preceeding MEM_REF offset and replace the
997 address with &OBJ. */
998 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
1000 gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
1001 if (addr_base != op->op0)
1003 double_int off = tree_to_double_int (mem_op->op0);
1004 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
1005 off = double_int_add (off, shwi_to_double_int (addr_offset));
1006 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
1007 op->op0 = build_fold_addr_expr (addr_base);
1008 if (host_integerp (mem_op->op0, 0))
1009 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1015 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1016 *I_P to point to the last element of the replacement. */
1018 vn_reference_maybe_forwprop_address (VEC (vn_reference_op_s, heap) **ops,
1021 unsigned int i = *i_p;
1022 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
1023 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
1025 enum tree_code code;
1028 def_stmt = SSA_NAME_DEF_STMT (op->op0);
1029 if (!is_gimple_assign (def_stmt))
1032 code = gimple_assign_rhs_code (def_stmt);
1033 if (code != ADDR_EXPR
1034 && code != POINTER_PLUS_EXPR)
1037 off = tree_to_double_int (mem_op->op0);
1038 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
1040 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1041 from .foo.bar to the preceeding MEM_REF offset and replace the
1042 address with &OBJ. */
1043 if (code == ADDR_EXPR)
1045 tree addr, addr_base;
1046 HOST_WIDE_INT addr_offset;
1048 addr = gimple_assign_rhs1 (def_stmt);
1049 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1052 || TREE_CODE (addr_base) != MEM_REF)
1055 off = double_int_add (off, shwi_to_double_int (addr_offset));
1056 off = double_int_add (off, mem_ref_offset (addr_base));
1057 op->op0 = TREE_OPERAND (addr_base, 0);
1062 ptr = gimple_assign_rhs1 (def_stmt);
1063 ptroff = gimple_assign_rhs2 (def_stmt);
1064 if (TREE_CODE (ptr) != SSA_NAME
1065 || TREE_CODE (ptroff) != INTEGER_CST)
1068 off = double_int_add (off, tree_to_double_int (ptroff));
1072 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
1073 if (host_integerp (mem_op->op0, 0))
1074 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1077 if (TREE_CODE (op->op0) == SSA_NAME)
1078 op->op0 = SSA_VAL (op->op0);
1079 if (TREE_CODE (op->op0) != SSA_NAME)
1080 op->opcode = TREE_CODE (op->op0);
1083 if (TREE_CODE (op->op0) == SSA_NAME)
1084 vn_reference_maybe_forwprop_address (ops, i_p);
1085 else if (TREE_CODE (op->op0) == ADDR_EXPR)
1086 vn_reference_fold_indirect (ops, i_p);
1089 /* Optimize the reference REF to a constant if possible or return
1090 NULL_TREE if not. */
1093 fully_constant_vn_reference_p (vn_reference_t ref)
1095 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1096 vn_reference_op_t op;
1098 /* Try to simplify the translated expression if it is
1099 a call to a builtin function with at most two arguments. */
1100 op = VEC_index (vn_reference_op_s, operands, 0);
1101 if (op->opcode == CALL_EXPR
1102 && TREE_CODE (op->op0) == ADDR_EXPR
1103 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1104 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1105 && VEC_length (vn_reference_op_s, operands) >= 2
1106 && VEC_length (vn_reference_op_s, operands) <= 3)
1108 vn_reference_op_t arg0, arg1 = NULL;
1109 bool anyconst = false;
1110 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1111 if (VEC_length (vn_reference_op_s, operands) > 2)
1112 arg1 = VEC_index (vn_reference_op_s, operands, 2);
1113 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1114 || (arg0->opcode == ADDR_EXPR
1115 && is_gimple_min_invariant (arg0->op0)))
1118 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1119 || (arg1->opcode == ADDR_EXPR
1120 && is_gimple_min_invariant (arg1->op0))))
1124 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1127 arg1 ? arg1->op0 : NULL);
1129 && TREE_CODE (folded) == NOP_EXPR)
1130 folded = TREE_OPERAND (folded, 0);
1132 && is_gimple_min_invariant (folded))
1137 /* Simplify reads from constant strings. */
1138 else if (op->opcode == ARRAY_REF
1139 && TREE_CODE (op->op0) == INTEGER_CST
1140 && integer_zerop (op->op1)
1141 && VEC_length (vn_reference_op_s, operands) == 2)
1143 vn_reference_op_t arg0;
1144 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1145 if (arg0->opcode == STRING_CST
1146 && (TYPE_MODE (op->type)
1147 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0->op0))))
1148 && GET_MODE_CLASS (TYPE_MODE (op->type)) == MODE_INT
1149 && GET_MODE_SIZE (TYPE_MODE (op->type)) == 1
1150 && compare_tree_int (op->op0, TREE_STRING_LENGTH (arg0->op0)) < 0)
1151 return build_int_cst_type (op->type,
1152 (TREE_STRING_POINTER (arg0->op0)
1153 [TREE_INT_CST_LOW (op->op0)]));
1159 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1160 structures into their value numbers. This is done in-place, and
1161 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1162 whether any operands were valueized. */
1164 static VEC (vn_reference_op_s, heap) *
1165 valueize_refs_1 (VEC (vn_reference_op_s, heap) *orig, bool *valueized_anything)
1167 vn_reference_op_t vro;
1170 *valueized_anything = false;
1172 FOR_EACH_VEC_ELT (vn_reference_op_s, orig, i, vro)
1174 if (vro->opcode == SSA_NAME
1175 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1177 tree tem = SSA_VAL (vro->op0);
1178 if (tem != vro->op0)
1180 *valueized_anything = true;
1183 /* If it transforms from an SSA_NAME to a constant, update
1185 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1186 vro->opcode = TREE_CODE (vro->op0);
1188 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1190 tree tem = SSA_VAL (vro->op1);
1191 if (tem != vro->op1)
1193 *valueized_anything = true;
1197 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1199 tree tem = SSA_VAL (vro->op2);
1200 if (tem != vro->op2)
1202 *valueized_anything = true;
1206 /* If it transforms from an SSA_NAME to an address, fold with
1207 a preceding indirect reference. */
1210 && TREE_CODE (vro->op0) == ADDR_EXPR
1211 && VEC_index (vn_reference_op_s,
1212 orig, i - 1)->opcode == MEM_REF)
1213 vn_reference_fold_indirect (&orig, &i);
1215 && vro->opcode == SSA_NAME
1216 && VEC_index (vn_reference_op_s,
1217 orig, i - 1)->opcode == MEM_REF)
1218 vn_reference_maybe_forwprop_address (&orig, &i);
1219 /* If it transforms a non-constant ARRAY_REF into a constant
1220 one, adjust the constant offset. */
1221 else if (vro->opcode == ARRAY_REF
1223 && TREE_CODE (vro->op0) == INTEGER_CST
1224 && TREE_CODE (vro->op1) == INTEGER_CST
1225 && TREE_CODE (vro->op2) == INTEGER_CST)
1227 double_int off = tree_to_double_int (vro->op0);
1228 off = double_int_add (off,
1230 (tree_to_double_int (vro->op1)));
1231 off = double_int_mul (off, tree_to_double_int (vro->op2));
1232 if (double_int_fits_in_shwi_p (off))
1240 static VEC (vn_reference_op_s, heap) *
1241 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
1244 return valueize_refs_1 (orig, &tem);
1247 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
1249 /* Create a vector of vn_reference_op_s structures from REF, a
1250 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1251 this function. *VALUEIZED_ANYTHING will specify whether any
1252 operands were valueized. */
1254 static VEC(vn_reference_op_s, heap) *
1255 valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything)
1259 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1260 copy_reference_ops_from_ref (ref, &shared_lookup_references);
1261 shared_lookup_references = valueize_refs_1 (shared_lookup_references,
1262 valueized_anything);
1263 return shared_lookup_references;
1266 /* Create a vector of vn_reference_op_s structures from CALL, a
1267 call statement. The vector is shared among all callers of
1270 static VEC(vn_reference_op_s, heap) *
1271 valueize_shared_reference_ops_from_call (gimple call)
1275 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1276 copy_reference_ops_from_call (call, &shared_lookup_references);
1277 shared_lookup_references = valueize_refs (shared_lookup_references);
1278 return shared_lookup_references;
1281 /* Lookup a SCCVN reference operation VR in the current hash table.
1282 Returns the resulting value number if it exists in the hash table,
1283 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1284 vn_reference_t stored in the hashtable if something is found. */
1287 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1292 hash = vr->hashcode;
1293 slot = htab_find_slot_with_hash (current_info->references, vr,
1295 if (!slot && current_info == optimistic_info)
1296 slot = htab_find_slot_with_hash (valid_info->references, vr,
1301 *vnresult = (vn_reference_t)*slot;
1302 return ((vn_reference_t)*slot)->result;
1308 static tree *last_vuse_ptr;
1309 static vn_lookup_kind vn_walk_kind;
1310 static vn_lookup_kind default_vn_walk_kind;
1312 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1313 with the current VUSE and performs the expression lookup. */
1316 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
1318 vn_reference_t vr = (vn_reference_t)vr_;
1323 *last_vuse_ptr = vuse;
1325 /* Fixup vuse and hash. */
1327 vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1328 vr->vuse = SSA_VAL (vuse);
1330 vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1332 hash = vr->hashcode;
1333 slot = htab_find_slot_with_hash (current_info->references, vr,
1335 if (!slot && current_info == optimistic_info)
1336 slot = htab_find_slot_with_hash (valid_info->references, vr,
1344 /* Lookup an existing or insert a new vn_reference entry into the
1345 value table for the VUSE, SET, TYPE, OPERANDS reference which
1346 has the constant value CST. */
1348 static vn_reference_t
1349 vn_reference_lookup_or_insert_constant_for_pieces (tree vuse,
1352 VEC (vn_reference_op_s,
1356 struct vn_reference_s vr1;
1357 vn_reference_t result;
1359 vr1.operands = operands;
1362 vr1.hashcode = vn_reference_compute_hash (&vr1);
1363 if (vn_reference_lookup_1 (&vr1, &result))
1365 return vn_reference_insert_pieces (vuse, set, type,
1366 VEC_copy (vn_reference_op_s, heap,
1368 get_or_alloc_constant_value_id (cst));
1371 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1372 from the statement defining VUSE and if not successful tries to
1373 translate *REFP and VR_ through an aggregate copy at the defintion
1377 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_)
1379 vn_reference_t vr = (vn_reference_t)vr_;
1380 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1382 HOST_WIDE_INT offset, maxsize;
1383 static VEC (vn_reference_op_s, heap) *lhs_ops = NULL;
1385 bool lhs_ref_ok = false;
1387 /* First try to disambiguate after value-replacing in the definitions LHS. */
1388 if (is_gimple_assign (def_stmt))
1390 VEC (vn_reference_op_s, heap) *tem;
1391 tree lhs = gimple_assign_lhs (def_stmt);
1392 bool valueized_anything = false;
1393 /* Avoid re-allocation overhead. */
1394 VEC_truncate (vn_reference_op_s, lhs_ops, 0);
1395 copy_reference_ops_from_ref (lhs, &lhs_ops);
1397 lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything);
1398 gcc_assert (lhs_ops == tem);
1399 if (valueized_anything)
1401 lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
1402 get_alias_set (lhs),
1403 TREE_TYPE (lhs), lhs_ops);
1405 && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1410 ao_ref_init (&lhs_ref, lhs);
1415 base = ao_ref_base (ref);
1416 offset = ref->offset;
1417 maxsize = ref->max_size;
1419 /* If we cannot constrain the size of the reference we cannot
1420 test if anything kills it. */
1424 /* We can't deduce anything useful from clobbers. */
1425 if (gimple_clobber_p (def_stmt))
1428 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1429 from that definition.
1431 if (is_gimple_reg_type (vr->type)
1432 && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
1433 && integer_zerop (gimple_call_arg (def_stmt, 1))
1434 && host_integerp (gimple_call_arg (def_stmt, 2), 1)
1435 && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1437 tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1439 HOST_WIDE_INT offset2, size2, maxsize2;
1440 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1441 size2 = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2)) * 8;
1442 if ((unsigned HOST_WIDE_INT)size2 / 8
1443 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2))
1445 && operand_equal_p (base, base2, 0)
1446 && offset2 <= offset
1447 && offset2 + size2 >= offset + maxsize)
1449 tree val = build_zero_cst (vr->type);
1450 return vn_reference_lookup_or_insert_constant_for_pieces
1451 (vuse, vr->set, vr->type, vr->operands, val);
1455 /* 2) Assignment from an empty CONSTRUCTOR. */
1456 else if (is_gimple_reg_type (vr->type)
1457 && gimple_assign_single_p (def_stmt)
1458 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1459 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1462 HOST_WIDE_INT offset2, size2, maxsize2;
1463 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1464 &offset2, &size2, &maxsize2);
1466 && operand_equal_p (base, base2, 0)
1467 && offset2 <= offset
1468 && offset2 + size2 >= offset + maxsize)
1470 tree val = build_zero_cst (vr->type);
1471 return vn_reference_lookup_or_insert_constant_for_pieces
1472 (vuse, vr->set, vr->type, vr->operands, val);
1476 /* 3) Assignment from a constant. We can use folds native encode/interpret
1477 routines to extract the assigned bits. */
1478 else if (CHAR_BIT == 8 && BITS_PER_UNIT == 8
1479 && ref->size == maxsize
1480 && maxsize % BITS_PER_UNIT == 0
1481 && offset % BITS_PER_UNIT == 0
1482 && is_gimple_reg_type (vr->type)
1483 && gimple_assign_single_p (def_stmt)
1484 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
1487 HOST_WIDE_INT offset2, size2, maxsize2;
1488 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1489 &offset2, &size2, &maxsize2);
1491 && maxsize2 == size2
1492 && size2 % BITS_PER_UNIT == 0
1493 && offset2 % BITS_PER_UNIT == 0
1494 && operand_equal_p (base, base2, 0)
1495 && offset2 <= offset
1496 && offset2 + size2 >= offset + maxsize)
1498 /* We support up to 512-bit values (for V8DFmode). */
1499 unsigned char buffer[64];
1502 len = native_encode_expr (gimple_assign_rhs1 (def_stmt),
1503 buffer, sizeof (buffer));
1506 tree val = native_interpret_expr (vr->type,
1508 + ((offset - offset2)
1510 ref->size / BITS_PER_UNIT);
1512 return vn_reference_lookup_or_insert_constant_for_pieces
1513 (vuse, vr->set, vr->type, vr->operands, val);
1518 /* 4) Assignment from an SSA name which definition we may be able
1519 to access pieces from. */
1520 else if (ref->size == maxsize
1521 && is_gimple_reg_type (vr->type)
1522 && gimple_assign_single_p (def_stmt)
1523 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
1525 tree rhs1 = gimple_assign_rhs1 (def_stmt);
1526 gimple def_stmt2 = SSA_NAME_DEF_STMT (rhs1);
1527 if (is_gimple_assign (def_stmt2)
1528 && (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR
1529 || gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR)
1530 && types_compatible_p (vr->type, TREE_TYPE (TREE_TYPE (rhs1))))
1533 HOST_WIDE_INT offset2, size2, maxsize2, off;
1534 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1535 &offset2, &size2, &maxsize2);
1536 off = offset - offset2;
1538 && maxsize2 == size2
1539 && operand_equal_p (base, base2, 0)
1540 && offset2 <= offset
1541 && offset2 + size2 >= offset + maxsize)
1543 tree val = NULL_TREE;
1545 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1))));
1546 if (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR)
1549 val = gimple_assign_rhs1 (def_stmt2);
1550 else if (off == elsz)
1551 val = gimple_assign_rhs2 (def_stmt2);
1553 else if (gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR
1556 tree ctor = gimple_assign_rhs1 (def_stmt2);
1557 unsigned i = off / elsz;
1558 if (i < CONSTRUCTOR_NELTS (ctor))
1560 constructor_elt *elt = CONSTRUCTOR_ELT (ctor, i);
1561 if (compare_tree_int (elt->index, i) == 0)
1566 return vn_reference_lookup_or_insert_constant_for_pieces
1567 (vuse, vr->set, vr->type, vr->operands, val);
1572 /* 5) For aggregate copies translate the reference through them if
1573 the copy kills ref. */
1574 else if (vn_walk_kind == VN_WALKREWRITE
1575 && gimple_assign_single_p (def_stmt)
1576 && (DECL_P (gimple_assign_rhs1 (def_stmt))
1577 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
1578 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1581 HOST_WIDE_INT offset2, size2, maxsize2;
1583 VEC (vn_reference_op_s, heap) *rhs = NULL;
1584 vn_reference_op_t vro;
1590 /* See if the assignment kills REF. */
1591 base2 = ao_ref_base (&lhs_ref);
1592 offset2 = lhs_ref.offset;
1593 size2 = lhs_ref.size;
1594 maxsize2 = lhs_ref.max_size;
1596 || (base != base2 && !operand_equal_p (base, base2, 0))
1598 || offset2 + size2 < offset + maxsize)
1601 /* Find the common base of ref and the lhs. lhs_ops already
1602 contains valueized operands for the lhs. */
1603 i = VEC_length (vn_reference_op_s, vr->operands) - 1;
1604 j = VEC_length (vn_reference_op_s, lhs_ops) - 1;
1605 while (j >= 0 && i >= 0
1606 && vn_reference_op_eq (VEC_index (vn_reference_op_s,
1608 VEC_index (vn_reference_op_s, lhs_ops, j)))
1614 /* ??? The innermost op should always be a MEM_REF and we already
1615 checked that the assignment to the lhs kills vr. Thus for
1616 aggregate copies using char[] types the vn_reference_op_eq
1617 may fail when comparing types for compatibility. But we really
1618 don't care here - further lookups with the rewritten operands
1619 will simply fail if we messed up types too badly. */
1620 if (j == 0 && i >= 0
1621 && VEC_index (vn_reference_op_s, lhs_ops, 0)->opcode == MEM_REF
1622 && VEC_index (vn_reference_op_s, lhs_ops, 0)->off != -1
1623 && (VEC_index (vn_reference_op_s, lhs_ops, 0)->off
1624 == VEC_index (vn_reference_op_s, vr->operands, i)->off))
1627 /* i now points to the first additional op.
1628 ??? LHS may not be completely contained in VR, one or more
1629 VIEW_CONVERT_EXPRs could be in its way. We could at least
1630 try handling outermost VIEW_CONVERT_EXPRs. */
1634 /* Now re-write REF to be based on the rhs of the assignment. */
1635 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1636 /* We need to pre-pend vr->operands[0..i] to rhs. */
1637 if (i + 1 + VEC_length (vn_reference_op_s, rhs)
1638 > VEC_length (vn_reference_op_s, vr->operands))
1640 VEC (vn_reference_op_s, heap) *old = vr->operands;
1641 VEC_safe_grow (vn_reference_op_s, heap, vr->operands,
1642 i + 1 + VEC_length (vn_reference_op_s, rhs));
1643 if (old == shared_lookup_references
1644 && vr->operands != old)
1645 shared_lookup_references = NULL;
1648 VEC_truncate (vn_reference_op_s, vr->operands,
1649 i + 1 + VEC_length (vn_reference_op_s, rhs));
1650 FOR_EACH_VEC_ELT (vn_reference_op_s, rhs, j, vro)
1651 VEC_replace (vn_reference_op_s, vr->operands, i + 1 + j, vro);
1652 VEC_free (vn_reference_op_s, heap, rhs);
1653 vr->operands = valueize_refs (vr->operands);
1654 vr->hashcode = vn_reference_compute_hash (vr);
1656 /* Adjust *ref from the new operands. */
1657 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1659 /* This can happen with bitfields. */
1660 if (ref->size != r.size)
1664 /* Do not update last seen VUSE after translating. */
1665 last_vuse_ptr = NULL;
1667 /* Keep looking for the adjusted *REF / VR pair. */
1671 /* 6) For memcpy copies translate the reference through them if
1672 the copy kills ref. */
1673 else if (vn_walk_kind == VN_WALKREWRITE
1674 && is_gimple_reg_type (vr->type)
1675 /* ??? Handle BCOPY as well. */
1676 && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
1677 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
1678 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
1679 && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
1680 || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
1681 && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
1682 || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
1683 && host_integerp (gimple_call_arg (def_stmt, 2), 1))
1687 HOST_WIDE_INT rhs_offset, copy_size, lhs_offset;
1688 vn_reference_op_s op;
1692 /* Only handle non-variable, addressable refs. */
1693 if (ref->size != maxsize
1694 || offset % BITS_PER_UNIT != 0
1695 || ref->size % BITS_PER_UNIT != 0)
1698 /* Extract a pointer base and an offset for the destination. */
1699 lhs = gimple_call_arg (def_stmt, 0);
1701 if (TREE_CODE (lhs) == SSA_NAME)
1702 lhs = SSA_VAL (lhs);
1703 if (TREE_CODE (lhs) == ADDR_EXPR)
1705 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
1709 if (TREE_CODE (tem) == MEM_REF
1710 && host_integerp (TREE_OPERAND (tem, 1), 1))
1712 lhs = TREE_OPERAND (tem, 0);
1713 lhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1715 else if (DECL_P (tem))
1716 lhs = build_fold_addr_expr (tem);
1720 if (TREE_CODE (lhs) != SSA_NAME
1721 && TREE_CODE (lhs) != ADDR_EXPR)
1724 /* Extract a pointer base and an offset for the source. */
1725 rhs = gimple_call_arg (def_stmt, 1);
1727 if (TREE_CODE (rhs) == SSA_NAME)
1728 rhs = SSA_VAL (rhs);
1729 if (TREE_CODE (rhs) == ADDR_EXPR)
1731 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
1735 if (TREE_CODE (tem) == MEM_REF
1736 && host_integerp (TREE_OPERAND (tem, 1), 1))
1738 rhs = TREE_OPERAND (tem, 0);
1739 rhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1741 else if (DECL_P (tem))
1742 rhs = build_fold_addr_expr (tem);
1746 if (TREE_CODE (rhs) != SSA_NAME
1747 && TREE_CODE (rhs) != ADDR_EXPR)
1750 copy_size = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2));
1752 /* The bases of the destination and the references have to agree. */
1753 if ((TREE_CODE (base) != MEM_REF
1755 || (TREE_CODE (base) == MEM_REF
1756 && (TREE_OPERAND (base, 0) != lhs
1757 || !host_integerp (TREE_OPERAND (base, 1), 1)))
1759 && (TREE_CODE (lhs) != ADDR_EXPR
1760 || TREE_OPERAND (lhs, 0) != base)))
1763 /* And the access has to be contained within the memcpy destination. */
1764 at = offset / BITS_PER_UNIT;
1765 if (TREE_CODE (base) == MEM_REF)
1766 at += TREE_INT_CST_LOW (TREE_OPERAND (base, 1));
1768 || lhs_offset + copy_size < at + maxsize / BITS_PER_UNIT)
1771 /* Make room for 2 operands in the new reference. */
1772 if (VEC_length (vn_reference_op_s, vr->operands) < 2)
1774 VEC (vn_reference_op_s, heap) *old = vr->operands;
1775 VEC_safe_grow (vn_reference_op_s, heap, vr->operands, 2);
1776 if (old == shared_lookup_references
1777 && vr->operands != old)
1778 shared_lookup_references = NULL;
1781 VEC_truncate (vn_reference_op_s, vr->operands, 2);
1783 /* The looked-through reference is a simple MEM_REF. */
1784 memset (&op, 0, sizeof (op));
1786 op.opcode = MEM_REF;
1787 op.op0 = build_int_cst (ptr_type_node, at - rhs_offset);
1788 op.off = at - lhs_offset + rhs_offset;
1789 VEC_replace (vn_reference_op_s, vr->operands, 0, &op);
1790 op.type = TREE_TYPE (rhs);
1791 op.opcode = TREE_CODE (rhs);
1794 VEC_replace (vn_reference_op_s, vr->operands, 1, &op);
1795 vr->hashcode = vn_reference_compute_hash (vr);
1797 /* Adjust *ref from the new operands. */
1798 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1800 /* This can happen with bitfields. */
1801 if (ref->size != r.size)
1805 /* Do not update last seen VUSE after translating. */
1806 last_vuse_ptr = NULL;
1808 /* Keep looking for the adjusted *REF / VR pair. */
1812 /* Bail out and stop walking. */
1816 /* Lookup a reference operation by it's parts, in the current hash table.
1817 Returns the resulting value number if it exists in the hash table,
1818 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1819 vn_reference_t stored in the hashtable if something is found. */
1822 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
1823 VEC (vn_reference_op_s, heap) *operands,
1824 vn_reference_t *vnresult, vn_lookup_kind kind)
1826 struct vn_reference_s vr1;
1834 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1835 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1836 VEC_safe_grow (vn_reference_op_s, heap, shared_lookup_references,
1837 VEC_length (vn_reference_op_s, operands));
1838 memcpy (VEC_address (vn_reference_op_s, shared_lookup_references),
1839 VEC_address (vn_reference_op_s, operands),
1840 sizeof (vn_reference_op_s)
1841 * VEC_length (vn_reference_op_s, operands));
1842 vr1.operands = operands = shared_lookup_references
1843 = valueize_refs (shared_lookup_references);
1846 vr1.hashcode = vn_reference_compute_hash (&vr1);
1847 if ((cst = fully_constant_vn_reference_p (&vr1)))
1850 vn_reference_lookup_1 (&vr1, vnresult);
1852 && kind != VN_NOWALK
1856 vn_walk_kind = kind;
1857 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
1859 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1860 vn_reference_lookup_2,
1861 vn_reference_lookup_3, &vr1);
1862 if (vr1.operands != operands)
1863 VEC_free (vn_reference_op_s, heap, vr1.operands);
1867 return (*vnresult)->result;
1872 /* Lookup OP in the current hash table, and return the resulting value
1873 number if it exists in the hash table. Return NULL_TREE if it does
1874 not exist in the hash table or if the result field of the structure
1875 was NULL.. VNRESULT will be filled in with the vn_reference_t
1876 stored in the hashtable if one exists. */
1879 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
1880 vn_reference_t *vnresult)
1882 VEC (vn_reference_op_s, heap) *operands;
1883 struct vn_reference_s vr1;
1885 bool valuezied_anything;
1890 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1891 vr1.operands = operands
1892 = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
1893 vr1.type = TREE_TYPE (op);
1894 vr1.set = get_alias_set (op);
1895 vr1.hashcode = vn_reference_compute_hash (&vr1);
1896 if ((cst = fully_constant_vn_reference_p (&vr1)))
1899 if (kind != VN_NOWALK
1902 vn_reference_t wvnresult;
1904 /* Make sure to use a valueized reference if we valueized anything.
1905 Otherwise preserve the full reference for advanced TBAA. */
1906 if (!valuezied_anything
1907 || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
1909 ao_ref_init (&r, op);
1910 vn_walk_kind = kind;
1912 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1913 vn_reference_lookup_2,
1914 vn_reference_lookup_3, &vr1);
1915 if (vr1.operands != operands)
1916 VEC_free (vn_reference_op_s, heap, vr1.operands);
1920 *vnresult = wvnresult;
1921 return wvnresult->result;
1927 return vn_reference_lookup_1 (&vr1, vnresult);
1931 /* Insert OP into the current hash table with a value number of
1932 RESULT, and return the resulting reference structure we created. */
1935 vn_reference_insert (tree op, tree result, tree vuse)
1940 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1941 if (TREE_CODE (result) == SSA_NAME)
1942 vr1->value_id = VN_INFO (result)->value_id;
1944 vr1->value_id = get_or_alloc_constant_value_id (result);
1945 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1946 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1947 vr1->type = TREE_TYPE (op);
1948 vr1->set = get_alias_set (op);
1949 vr1->hashcode = vn_reference_compute_hash (vr1);
1950 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1952 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1955 /* Because we lookup stores using vuses, and value number failures
1956 using the vdefs (see visit_reference_op_store for how and why),
1957 it's possible that on failure we may try to insert an already
1958 inserted store. This is not wrong, there is no ssa name for a
1959 store that we could use as a differentiator anyway. Thus, unlike
1960 the other lookup functions, you cannot gcc_assert (!*slot)
1963 /* But free the old slot in case of a collision. */
1965 free_reference (*slot);
1971 /* Insert a reference by it's pieces into the current hash table with
1972 a value number of RESULT. Return the resulting reference
1973 structure we created. */
1976 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
1977 VEC (vn_reference_op_s, heap) *operands,
1978 tree result, unsigned int value_id)
1984 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1985 vr1->value_id = value_id;
1986 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1987 vr1->operands = valueize_refs (operands);
1990 vr1->hashcode = vn_reference_compute_hash (vr1);
1991 if (result && TREE_CODE (result) == SSA_NAME)
1992 result = SSA_VAL (result);
1993 vr1->result = result;
1995 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1998 /* At this point we should have all the things inserted that we have
1999 seen before, and we should never try inserting something that
2001 gcc_assert (!*slot);
2003 free_reference (*slot);
2009 /* Compute and return the hash value for nary operation VBO1. */
2012 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
2017 for (i = 0; i < vno1->length; ++i)
2018 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
2019 vno1->op[i] = SSA_VAL (vno1->op[i]);
2021 if (vno1->length == 2
2022 && commutative_tree_code (vno1->opcode)
2023 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
2025 tree temp = vno1->op[0];
2026 vno1->op[0] = vno1->op[1];
2030 hash = iterative_hash_hashval_t (vno1->opcode, 0);
2031 for (i = 0; i < vno1->length; ++i)
2032 hash = iterative_hash_expr (vno1->op[i], hash);
2037 /* Return the computed hashcode for nary operation P1. */
2040 vn_nary_op_hash (const void *p1)
2042 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
2043 return vno1->hashcode;
2046 /* Compare nary operations P1 and P2 and return true if they are
2050 vn_nary_op_eq (const void *p1, const void *p2)
2052 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
2053 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
2056 if (vno1->hashcode != vno2->hashcode)
2059 if (vno1->length != vno2->length)
2062 if (vno1->opcode != vno2->opcode
2063 || !types_compatible_p (vno1->type, vno2->type))
2066 for (i = 0; i < vno1->length; ++i)
2067 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
2073 /* Initialize VNO from the pieces provided. */
2076 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
2077 enum tree_code code, tree type, tree *ops)
2080 vno->length = length;
2082 memcpy (&vno->op[0], ops, sizeof (tree) * length);
2085 /* Initialize VNO from OP. */
2088 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
2092 vno->opcode = TREE_CODE (op);
2093 vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
2094 vno->type = TREE_TYPE (op);
2095 for (i = 0; i < vno->length; ++i)
2096 vno->op[i] = TREE_OPERAND (op, i);
2099 /* Return the number of operands for a vn_nary ops structure from STMT. */
2102 vn_nary_length_from_stmt (gimple stmt)
2104 switch (gimple_assign_rhs_code (stmt))
2108 case VIEW_CONVERT_EXPR:
2112 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2115 return gimple_num_ops (stmt) - 1;
2119 /* Initialize VNO from STMT. */
2122 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple stmt)
2126 vno->opcode = gimple_assign_rhs_code (stmt);
2127 vno->type = gimple_expr_type (stmt);
2128 switch (vno->opcode)
2132 case VIEW_CONVERT_EXPR:
2134 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2138 vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2139 for (i = 0; i < vno->length; ++i)
2140 vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value;
2144 vno->length = gimple_num_ops (stmt) - 1;
2145 for (i = 0; i < vno->length; ++i)
2146 vno->op[i] = gimple_op (stmt, i + 1);
2150 /* Compute the hashcode for VNO and look for it in the hash table;
2151 return the resulting value number if it exists in the hash table.
2152 Return NULL_TREE if it does not exist in the hash table or if the
2153 result field of the operation is NULL. VNRESULT will contain the
2154 vn_nary_op_t from the hashtable if it exists. */
2157 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
2164 vno->hashcode = vn_nary_op_compute_hash (vno);
2165 slot = htab_find_slot_with_hash (current_info->nary, vno, vno->hashcode,
2167 if (!slot && current_info == optimistic_info)
2168 slot = htab_find_slot_with_hash (valid_info->nary, vno, vno->hashcode,
2173 *vnresult = (vn_nary_op_t)*slot;
2174 return ((vn_nary_op_t)*slot)->result;
2177 /* Lookup a n-ary operation by its pieces and return the resulting value
2178 number if it exists in the hash table. Return NULL_TREE if it does
2179 not exist in the hash table or if the result field of the operation
2180 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2184 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2185 tree type, tree *ops, vn_nary_op_t *vnresult)
2187 vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s,
2188 sizeof_vn_nary_op (length));
2189 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2190 return vn_nary_op_lookup_1 (vno1, vnresult);
2193 /* Lookup OP in the current hash table, and return the resulting value
2194 number if it exists in the hash table. Return NULL_TREE if it does
2195 not exist in the hash table or if the result field of the operation
2196 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2200 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2203 = XALLOCAVAR (struct vn_nary_op_s,
2204 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op))));
2205 init_vn_nary_op_from_op (vno1, op);
2206 return vn_nary_op_lookup_1 (vno1, vnresult);
2209 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2210 value number if it exists in the hash table. Return NULL_TREE if
2211 it does not exist in the hash table. VNRESULT will contain the
2212 vn_nary_op_t from the hashtable if it exists. */
2215 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
2218 = XALLOCAVAR (struct vn_nary_op_s,
2219 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt)));
2220 init_vn_nary_op_from_stmt (vno1, stmt);
2221 return vn_nary_op_lookup_1 (vno1, vnresult);
2224 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2227 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2229 return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
2232 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2236 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
2238 vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
2239 ¤t_info->nary_obstack);
2241 vno1->value_id = value_id;
2242 vno1->length = length;
2243 vno1->result = result;
2248 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2249 VNO->HASHCODE first. */
2252 vn_nary_op_insert_into (vn_nary_op_t vno, htab_t table, bool compute_hash)
2257 vno->hashcode = vn_nary_op_compute_hash (vno);
2259 slot = htab_find_slot_with_hash (table, vno, vno->hashcode, INSERT);
2260 gcc_assert (!*slot);
2266 /* Insert a n-ary operation into the current hash table using it's
2267 pieces. Return the vn_nary_op_t structure we created and put in
2271 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
2272 tree type, tree *ops,
2273 tree result, unsigned int value_id)
2275 vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id);
2276 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2277 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2280 /* Insert OP into the current hash table with a value number of
2281 RESULT. Return the vn_nary_op_t structure we created and put in
2285 vn_nary_op_insert (tree op, tree result)
2287 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
2290 vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2291 init_vn_nary_op_from_op (vno1, op);
2292 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2295 /* Insert the rhs of STMT into the current hash table with a value number of
2299 vn_nary_op_insert_stmt (gimple stmt, tree result)
2302 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt),
2303 result, VN_INFO (result)->value_id);
2304 init_vn_nary_op_from_stmt (vno1, stmt);
2305 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2308 /* Compute a hashcode for PHI operation VP1 and return it. */
2310 static inline hashval_t
2311 vn_phi_compute_hash (vn_phi_t vp1)
2318 result = vp1->block->index;
2320 /* If all PHI arguments are constants we need to distinguish
2321 the PHI node via its type. */
2322 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
2323 result += (INTEGRAL_TYPE_P (type)
2324 + (INTEGRAL_TYPE_P (type)
2325 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
2327 FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2329 if (phi1op == VN_TOP)
2331 result = iterative_hash_expr (phi1op, result);
2337 /* Return the computed hashcode for phi operation P1. */
2340 vn_phi_hash (const void *p1)
2342 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2343 return vp1->hashcode;
2346 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2349 vn_phi_eq (const void *p1, const void *p2)
2351 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2352 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
2354 if (vp1->hashcode != vp2->hashcode)
2357 if (vp1->block == vp2->block)
2362 /* If the PHI nodes do not have compatible types
2363 they are not the same. */
2364 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
2365 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
2368 /* Any phi in the same block will have it's arguments in the
2369 same edge order, because of how we store phi nodes. */
2370 FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2372 tree phi2op = VEC_index (tree, vp2->phiargs, i);
2373 if (phi1op == VN_TOP || phi2op == VN_TOP)
2375 if (!expressions_equal_p (phi1op, phi2op))
2383 static VEC(tree, heap) *shared_lookup_phiargs;
2385 /* Lookup PHI in the current hash table, and return the resulting
2386 value number if it exists in the hash table. Return NULL_TREE if
2387 it does not exist in the hash table. */
2390 vn_phi_lookup (gimple phi)
2393 struct vn_phi_s vp1;
2396 VEC_truncate (tree, shared_lookup_phiargs, 0);
2398 /* Canonicalize the SSA_NAME's to their value number. */
2399 for (i = 0; i < gimple_phi_num_args (phi); i++)
2401 tree def = PHI_ARG_DEF (phi, i);
2402 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2403 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
2405 vp1.phiargs = shared_lookup_phiargs;
2406 vp1.block = gimple_bb (phi);
2407 vp1.hashcode = vn_phi_compute_hash (&vp1);
2408 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
2410 if (!slot && current_info == optimistic_info)
2411 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
2415 return ((vn_phi_t)*slot)->result;
2418 /* Insert PHI into the current hash table with a value number of
2422 vn_phi_insert (gimple phi, tree result)
2425 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
2427 VEC (tree, heap) *args = NULL;
2429 /* Canonicalize the SSA_NAME's to their value number. */
2430 for (i = 0; i < gimple_phi_num_args (phi); i++)
2432 tree def = PHI_ARG_DEF (phi, i);
2433 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2434 VEC_safe_push (tree, heap, args, def);
2436 vp1->value_id = VN_INFO (result)->value_id;
2437 vp1->phiargs = args;
2438 vp1->block = gimple_bb (phi);
2439 vp1->result = result;
2440 vp1->hashcode = vn_phi_compute_hash (vp1);
2442 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
2445 /* Because we iterate over phi operations more than once, it's
2446 possible the slot might already exist here, hence no assert.*/
2452 /* Print set of components in strongly connected component SCC to OUT. */
2455 print_scc (FILE *out, VEC (tree, heap) *scc)
2460 fprintf (out, "SCC consists of: ");
2461 FOR_EACH_VEC_ELT (tree, scc, i, var)
2463 print_generic_expr (out, var, 0);
2466 fprintf (out, "\n");
2469 /* Set the value number of FROM to TO, return true if it has changed
2473 set_ssa_val_to (tree from, tree to)
2475 tree currval = SSA_VAL (from);
2479 if (currval == from)
2481 if (dump_file && (dump_flags & TDF_DETAILS))
2483 fprintf (dump_file, "Not changing value number of ");
2484 print_generic_expr (dump_file, from, 0);
2485 fprintf (dump_file, " from VARYING to ");
2486 print_generic_expr (dump_file, to, 0);
2487 fprintf (dump_file, "\n");
2491 else if (TREE_CODE (to) == SSA_NAME
2492 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
2496 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2497 and invariants. So assert that here. */
2498 gcc_assert (to != NULL_TREE
2500 || TREE_CODE (to) == SSA_NAME
2501 || is_gimple_min_invariant (to)));
2503 if (dump_file && (dump_flags & TDF_DETAILS))
2505 fprintf (dump_file, "Setting value number of ");
2506 print_generic_expr (dump_file, from, 0);
2507 fprintf (dump_file, " to ");
2508 print_generic_expr (dump_file, to, 0);
2511 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
2513 VN_INFO (from)->valnum = to;
2514 if (dump_file && (dump_flags & TDF_DETAILS))
2515 fprintf (dump_file, " (changed)\n");
2518 if (dump_file && (dump_flags & TDF_DETAILS))
2519 fprintf (dump_file, "\n");
2523 /* Set all definitions in STMT to value number to themselves.
2524 Return true if a value number changed. */
2527 defs_to_varying (gimple stmt)
2529 bool changed = false;
2533 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2535 tree def = DEF_FROM_PTR (defp);
2537 VN_INFO (def)->use_processed = true;
2538 changed |= set_ssa_val_to (def, def);
2543 static bool expr_has_constants (tree expr);
2544 static tree valueize_expr (tree expr);
2546 /* Visit a copy between LHS and RHS, return true if the value number
2550 visit_copy (tree lhs, tree rhs)
2552 /* Follow chains of copies to their destination. */
2553 while (TREE_CODE (rhs) == SSA_NAME
2554 && SSA_VAL (rhs) != rhs)
2555 rhs = SSA_VAL (rhs);
2557 /* The copy may have a more interesting constant filled expression
2558 (we don't, since we know our RHS is just an SSA name). */
2559 if (TREE_CODE (rhs) == SSA_NAME)
2561 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
2562 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
2565 return set_ssa_val_to (lhs, rhs);
2568 /* Visit a nary operator RHS, value number it, and return true if the
2569 value number of LHS has changed as a result. */
2572 visit_nary_op (tree lhs, gimple stmt)
2574 bool changed = false;
2575 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2578 changed = set_ssa_val_to (lhs, result);
2581 changed = set_ssa_val_to (lhs, lhs);
2582 vn_nary_op_insert_stmt (stmt, lhs);
2588 /* Visit a call STMT storing into LHS. Return true if the value number
2589 of the LHS has changed as a result. */
2592 visit_reference_op_call (tree lhs, gimple stmt)
2594 bool changed = false;
2595 struct vn_reference_s vr1;
2597 tree vuse = gimple_vuse (stmt);
2599 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2600 vr1.operands = valueize_shared_reference_ops_from_call (stmt);
2601 vr1.type = gimple_expr_type (stmt);
2603 vr1.hashcode = vn_reference_compute_hash (&vr1);
2604 result = vn_reference_lookup_1 (&vr1, NULL);
2607 changed = set_ssa_val_to (lhs, result);
2608 if (TREE_CODE (result) == SSA_NAME
2609 && VN_INFO (result)->has_constants)
2610 VN_INFO (lhs)->has_constants = true;
2616 changed = set_ssa_val_to (lhs, lhs);
2617 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
2618 vr2->vuse = vr1.vuse;
2619 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
2620 vr2->type = vr1.type;
2622 vr2->hashcode = vr1.hashcode;
2624 slot = htab_find_slot_with_hash (current_info->references,
2625 vr2, vr2->hashcode, INSERT);
2627 free_reference (*slot);
2634 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2635 and return true if the value number of the LHS has changed as a result. */
2638 visit_reference_op_load (tree lhs, tree op, gimple stmt)
2640 bool changed = false;
2644 last_vuse = gimple_vuse (stmt);
2645 last_vuse_ptr = &last_vuse;
2646 result = vn_reference_lookup (op, gimple_vuse (stmt),
2647 default_vn_walk_kind, NULL);
2648 last_vuse_ptr = NULL;
2650 /* If we have a VCE, try looking up its operand as it might be stored in
2651 a different type. */
2652 if (!result && TREE_CODE (op) == VIEW_CONVERT_EXPR)
2653 result = vn_reference_lookup (TREE_OPERAND (op, 0), gimple_vuse (stmt),
2654 default_vn_walk_kind, NULL);
2656 /* We handle type-punning through unions by value-numbering based
2657 on offset and size of the access. Be prepared to handle a
2658 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2660 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
2662 /* We will be setting the value number of lhs to the value number
2663 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2664 So first simplify and lookup this expression to see if it
2665 is already available. */
2666 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
2667 if ((CONVERT_EXPR_P (val)
2668 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
2669 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
2671 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
2672 if ((CONVERT_EXPR_P (tem)
2673 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
2674 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
2675 TREE_TYPE (val), tem)))
2679 if (!is_gimple_min_invariant (val)
2680 && TREE_CODE (val) != SSA_NAME)
2681 result = vn_nary_op_lookup (val, NULL);
2682 /* If the expression is not yet available, value-number lhs to
2683 a new SSA_NAME we create. */
2686 result = make_ssa_name (SSA_NAME_VAR (lhs), gimple_build_nop ());
2687 /* Initialize value-number information properly. */
2688 VN_INFO_GET (result)->valnum = result;
2689 VN_INFO (result)->value_id = get_next_value_id ();
2690 VN_INFO (result)->expr = val;
2691 VN_INFO (result)->has_constants = expr_has_constants (val);
2692 VN_INFO (result)->needs_insertion = true;
2693 /* As all "inserted" statements are singleton SCCs, insert
2694 to the valid table. This is strictly needed to
2695 avoid re-generating new value SSA_NAMEs for the same
2696 expression during SCC iteration over and over (the
2697 optimistic table gets cleared after each iteration).
2698 We do not need to insert into the optimistic table, as
2699 lookups there will fall back to the valid table. */
2700 if (current_info == optimistic_info)
2702 current_info = valid_info;
2703 vn_nary_op_insert (val, result);
2704 current_info = optimistic_info;
2707 vn_nary_op_insert (val, result);
2708 if (dump_file && (dump_flags & TDF_DETAILS))
2710 fprintf (dump_file, "Inserting name ");
2711 print_generic_expr (dump_file, result, 0);
2712 fprintf (dump_file, " for expression ");
2713 print_generic_expr (dump_file, val, 0);
2714 fprintf (dump_file, "\n");
2721 changed = set_ssa_val_to (lhs, result);
2722 if (TREE_CODE (result) == SSA_NAME
2723 && VN_INFO (result)->has_constants)
2725 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
2726 VN_INFO (lhs)->has_constants = true;
2731 changed = set_ssa_val_to (lhs, lhs);
2732 vn_reference_insert (op, lhs, last_vuse);
2739 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2740 and return true if the value number of the LHS has changed as a result. */
2743 visit_reference_op_store (tree lhs, tree op, gimple stmt)
2745 bool changed = false;
2747 bool resultsame = false;
2749 /* First we want to lookup using the *vuses* from the store and see
2750 if there the last store to this location with the same address
2753 The vuses represent the memory state before the store. If the
2754 memory state, address, and value of the store is the same as the
2755 last store to this location, then this store will produce the
2756 same memory state as that store.
2758 In this case the vdef versions for this store are value numbered to those
2759 vuse versions, since they represent the same memory state after
2762 Otherwise, the vdefs for the store are used when inserting into
2763 the table, since the store generates a new memory state. */
2765 result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL);
2769 if (TREE_CODE (result) == SSA_NAME)
2770 result = SSA_VAL (result);
2771 if (TREE_CODE (op) == SSA_NAME)
2773 resultsame = expressions_equal_p (result, op);
2776 if (!result || !resultsame)
2780 if (dump_file && (dump_flags & TDF_DETAILS))
2782 fprintf (dump_file, "No store match\n");
2783 fprintf (dump_file, "Value numbering store ");
2784 print_generic_expr (dump_file, lhs, 0);
2785 fprintf (dump_file, " to ");
2786 print_generic_expr (dump_file, op, 0);
2787 fprintf (dump_file, "\n");
2789 /* Have to set value numbers before insert, since insert is
2790 going to valueize the references in-place. */
2791 if ((vdef = gimple_vdef (stmt)))
2793 VN_INFO (vdef)->use_processed = true;
2794 changed |= set_ssa_val_to (vdef, vdef);
2797 /* Do not insert structure copies into the tables. */
2798 if (is_gimple_min_invariant (op)
2799 || is_gimple_reg (op))
2800 vn_reference_insert (lhs, op, vdef);
2804 /* We had a match, so value number the vdef to have the value
2805 number of the vuse it came from. */
2808 if (dump_file && (dump_flags & TDF_DETAILS))
2809 fprintf (dump_file, "Store matched earlier value,"
2810 "value numbering store vdefs to matching vuses.\n");
2812 def = gimple_vdef (stmt);
2813 use = gimple_vuse (stmt);
2815 VN_INFO (def)->use_processed = true;
2816 changed |= set_ssa_val_to (def, SSA_VAL (use));
2822 /* Visit and value number PHI, return true if the value number
2826 visit_phi (gimple phi)
2828 bool changed = false;
2830 tree sameval = VN_TOP;
2831 bool allsame = true;
2834 /* TODO: We could check for this in init_sccvn, and replace this
2835 with a gcc_assert. */
2836 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
2837 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2839 /* See if all non-TOP arguments have the same value. TOP is
2840 equivalent to everything, so we can ignore it. */
2841 for (i = 0; i < gimple_phi_num_args (phi); i++)
2843 tree def = PHI_ARG_DEF (phi, i);
2845 if (TREE_CODE (def) == SSA_NAME)
2846 def = SSA_VAL (def);
2849 if (sameval == VN_TOP)
2855 if (!expressions_equal_p (def, sameval))
2863 /* If all value numbered to the same value, the phi node has that
2867 if (is_gimple_min_invariant (sameval))
2869 VN_INFO (PHI_RESULT (phi))->has_constants = true;
2870 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2874 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2875 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2878 if (TREE_CODE (sameval) == SSA_NAME)
2879 return visit_copy (PHI_RESULT (phi), sameval);
2881 return set_ssa_val_to (PHI_RESULT (phi), sameval);
2884 /* Otherwise, see if it is equivalent to a phi node in this block. */
2885 result = vn_phi_lookup (phi);
2888 if (TREE_CODE (result) == SSA_NAME)
2889 changed = visit_copy (PHI_RESULT (phi), result);
2891 changed = set_ssa_val_to (PHI_RESULT (phi), result);
2895 vn_phi_insert (phi, PHI_RESULT (phi));
2896 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2897 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
2898 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2904 /* Return true if EXPR contains constants. */
2907 expr_has_constants (tree expr)
2909 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2912 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
2915 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
2916 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
2917 /* Constants inside reference ops are rarely interesting, but
2918 it can take a lot of looking to find them. */
2920 case tcc_declaration:
2923 return is_gimple_min_invariant (expr);
2928 /* Return true if STMT contains constants. */
2931 stmt_has_constants (gimple stmt)
2933 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2936 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2938 case GIMPLE_UNARY_RHS:
2939 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2941 case GIMPLE_BINARY_RHS:
2942 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2943 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
2944 case GIMPLE_TERNARY_RHS:
2945 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2946 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt))
2947 || is_gimple_min_invariant (gimple_assign_rhs3 (stmt)));
2948 case GIMPLE_SINGLE_RHS:
2949 /* Constants inside reference ops are rarely interesting, but
2950 it can take a lot of looking to find them. */
2951 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2958 /* Replace SSA_NAMES in expr with their value numbers, and return the
2960 This is performed in place. */
2963 valueize_expr (tree expr)
2965 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2968 TREE_OPERAND (expr, 1) = vn_valueize (TREE_OPERAND (expr, 1));
2971 TREE_OPERAND (expr, 0) = vn_valueize (TREE_OPERAND (expr, 0));
2978 /* Simplify the binary expression RHS, and return the result if
2982 simplify_binary_expression (gimple stmt)
2984 tree result = NULL_TREE;
2985 tree op0 = gimple_assign_rhs1 (stmt);
2986 tree op1 = gimple_assign_rhs2 (stmt);
2987 enum tree_code code = gimple_assign_rhs_code (stmt);
2989 /* This will not catch every single case we could combine, but will
2990 catch those with constants. The goal here is to simultaneously
2991 combine constants between expressions, but avoid infinite
2992 expansion of expressions during simplification. */
2993 if (TREE_CODE (op0) == SSA_NAME)
2995 if (VN_INFO (op0)->has_constants
2996 || TREE_CODE_CLASS (code) == tcc_comparison
2997 || code == COMPLEX_EXPR)
2998 op0 = valueize_expr (vn_get_expr_for (op0));
3000 op0 = vn_valueize (op0);
3003 if (TREE_CODE (op1) == SSA_NAME)
3005 if (VN_INFO (op1)->has_constants
3006 || code == COMPLEX_EXPR)
3007 op1 = valueize_expr (vn_get_expr_for (op1));
3009 op1 = vn_valueize (op1);
3012 /* Pointer plus constant can be represented as invariant address.
3013 Do so to allow further propatation, see also tree forwprop. */
3014 if (code == POINTER_PLUS_EXPR
3015 && host_integerp (op1, 1)
3016 && TREE_CODE (op0) == ADDR_EXPR
3017 && is_gimple_min_invariant (op0))
3018 return build_invariant_address (TREE_TYPE (op0),
3019 TREE_OPERAND (op0, 0),
3020 TREE_INT_CST_LOW (op1));
3022 /* Avoid folding if nothing changed. */
3023 if (op0 == gimple_assign_rhs1 (stmt)
3024 && op1 == gimple_assign_rhs2 (stmt))
3027 fold_defer_overflow_warnings ();
3029 result = fold_binary (code, gimple_expr_type (stmt), op0, op1);
3031 STRIP_USELESS_TYPE_CONVERSION (result);
3033 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
3036 /* Make sure result is not a complex expression consisting
3037 of operators of operators (IE (a + b) + (a + c))
3038 Otherwise, we will end up with unbounded expressions if
3039 fold does anything at all. */
3040 if (result && valid_gimple_rhs_p (result))
3046 /* Simplify the unary expression RHS, and return the result if
3050 simplify_unary_expression (gimple stmt)
3052 tree result = NULL_TREE;
3053 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
3054 enum tree_code code = gimple_assign_rhs_code (stmt);
3056 /* We handle some tcc_reference codes here that are all
3057 GIMPLE_ASSIGN_SINGLE codes. */
3058 if (code == REALPART_EXPR
3059 || code == IMAGPART_EXPR
3060 || code == VIEW_CONVERT_EXPR
3061 || code == BIT_FIELD_REF)
3062 op0 = TREE_OPERAND (op0, 0);
3064 if (TREE_CODE (op0) != SSA_NAME)
3068 if (VN_INFO (op0)->has_constants)
3069 op0 = valueize_expr (vn_get_expr_for (op0));
3070 else if (CONVERT_EXPR_CODE_P (code)
3071 || code == REALPART_EXPR
3072 || code == IMAGPART_EXPR
3073 || code == VIEW_CONVERT_EXPR
3074 || code == BIT_FIELD_REF)
3076 /* We want to do tree-combining on conversion-like expressions.
3077 Make sure we feed only SSA_NAMEs or constants to fold though. */
3078 tree tem = valueize_expr (vn_get_expr_for (op0));
3079 if (UNARY_CLASS_P (tem)
3080 || BINARY_CLASS_P (tem)
3081 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
3082 || TREE_CODE (tem) == SSA_NAME
3083 || TREE_CODE (tem) == CONSTRUCTOR
3084 || is_gimple_min_invariant (tem))
3088 /* Avoid folding if nothing changed, but remember the expression. */
3089 if (op0 == orig_op0)
3092 if (code == BIT_FIELD_REF)
3094 tree rhs = gimple_assign_rhs1 (stmt);
3095 result = fold_ternary (BIT_FIELD_REF, TREE_TYPE (rhs),
3096 op0, TREE_OPERAND (rhs, 1), TREE_OPERAND (rhs, 2));
3099 result = fold_unary_ignore_overflow (code, gimple_expr_type (stmt), op0);
3102 STRIP_USELESS_TYPE_CONVERSION (result);
3103 if (valid_gimple_rhs_p (result))
3110 /* Try to simplify RHS using equivalences and constant folding. */
3113 try_to_simplify (gimple stmt)
3115 enum tree_code code = gimple_assign_rhs_code (stmt);
3118 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3119 in this case, there is no point in doing extra work. */
3120 if (code == SSA_NAME)
3123 /* First try constant folding based on our current lattice. */
3124 tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize);
3126 && (TREE_CODE (tem) == SSA_NAME
3127 || is_gimple_min_invariant (tem)))
3130 /* If that didn't work try combining multiple statements. */
3131 switch (TREE_CODE_CLASS (code))
3134 /* Fallthrough for some unary codes that can operate on registers. */
3135 if (!(code == REALPART_EXPR
3136 || code == IMAGPART_EXPR
3137 || code == VIEW_CONVERT_EXPR
3138 || code == BIT_FIELD_REF))
3140 /* We could do a little more with unary ops, if they expand
3141 into binary ops, but it's debatable whether it is worth it. */
3143 return simplify_unary_expression (stmt);
3145 case tcc_comparison:
3147 return simplify_binary_expression (stmt);
3156 /* Visit and value number USE, return true if the value number
3160 visit_use (tree use)
3162 bool changed = false;
3163 gimple stmt = SSA_NAME_DEF_STMT (use);
3165 VN_INFO (use)->use_processed = true;
3167 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
3168 if (dump_file && (dump_flags & TDF_DETAILS)
3169 && !SSA_NAME_IS_DEFAULT_DEF (use))
3171 fprintf (dump_file, "Value numbering ");
3172 print_generic_expr (dump_file, use, 0);
3173 fprintf (dump_file, " stmt = ");
3174 print_gimple_stmt (dump_file, stmt, 0, 0);
3177 /* Handle uninitialized uses. */
3178 if (SSA_NAME_IS_DEFAULT_DEF (use))
3179 changed = set_ssa_val_to (use, use);
3182 if (gimple_code (stmt) == GIMPLE_PHI)
3183 changed = visit_phi (stmt);
3184 else if (!gimple_has_lhs (stmt)
3185 || gimple_has_volatile_ops (stmt))
3186 changed = defs_to_varying (stmt);
3187 else if (is_gimple_assign (stmt))
3189 enum tree_code code = gimple_assign_rhs_code (stmt);
3190 tree lhs = gimple_assign_lhs (stmt);
3191 tree rhs1 = gimple_assign_rhs1 (stmt);
3194 /* Shortcut for copies. Simplifying copies is pointless,
3195 since we copy the expression and value they represent. */
3196 if (code == SSA_NAME
3197 && TREE_CODE (lhs) == SSA_NAME)
3199 changed = visit_copy (lhs, rhs1);
3202 simplified = try_to_simplify (stmt);
3205 if (dump_file && (dump_flags & TDF_DETAILS))
3207 fprintf (dump_file, "RHS ");
3208 print_gimple_expr (dump_file, stmt, 0, 0);
3209 fprintf (dump_file, " simplified to ");
3210 print_generic_expr (dump_file, simplified, 0);
3211 if (TREE_CODE (lhs) == SSA_NAME)
3212 fprintf (dump_file, " has constants %d\n",
3213 expr_has_constants (simplified));
3215 fprintf (dump_file, "\n");
3218 /* Setting value numbers to constants will occasionally
3219 screw up phi congruence because constants are not
3220 uniquely associated with a single ssa name that can be
3223 && is_gimple_min_invariant (simplified)
3224 && TREE_CODE (lhs) == SSA_NAME)
3226 VN_INFO (lhs)->expr = simplified;
3227 VN_INFO (lhs)->has_constants = true;
3228 changed = set_ssa_val_to (lhs, simplified);
3232 && TREE_CODE (simplified) == SSA_NAME
3233 && TREE_CODE (lhs) == SSA_NAME)
3235 changed = visit_copy (lhs, simplified);
3238 else if (simplified)
3240 if (TREE_CODE (lhs) == SSA_NAME)
3242 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
3243 /* We have to unshare the expression or else
3244 valuizing may change the IL stream. */
3245 VN_INFO (lhs)->expr = unshare_expr (simplified);
3248 else if (stmt_has_constants (stmt)
3249 && TREE_CODE (lhs) == SSA_NAME)
3250 VN_INFO (lhs)->has_constants = true;
3251 else if (TREE_CODE (lhs) == SSA_NAME)
3253 /* We reset expr and constantness here because we may
3254 have been value numbering optimistically, and
3255 iterating. They may become non-constant in this case,
3256 even if they were optimistically constant. */
3258 VN_INFO (lhs)->has_constants = false;
3259 VN_INFO (lhs)->expr = NULL_TREE;
3262 if ((TREE_CODE (lhs) == SSA_NAME
3263 /* We can substitute SSA_NAMEs that are live over
3264 abnormal edges with their constant value. */
3265 && !(gimple_assign_copy_p (stmt)
3266 && is_gimple_min_invariant (rhs1))
3268 && is_gimple_min_invariant (simplified))
3269 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3270 /* Stores or copies from SSA_NAMEs that are live over
3271 abnormal edges are a problem. */
3272 || (code == SSA_NAME
3273 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
3274 changed = defs_to_varying (stmt);
3275 else if (REFERENCE_CLASS_P (lhs)
3277 changed = visit_reference_op_store (lhs, rhs1, stmt);
3278 else if (TREE_CODE (lhs) == SSA_NAME)
3280 if ((gimple_assign_copy_p (stmt)
3281 && is_gimple_min_invariant (rhs1))
3283 && is_gimple_min_invariant (simplified)))
3285 VN_INFO (lhs)->has_constants = true;
3287 changed = set_ssa_val_to (lhs, simplified);
3289 changed = set_ssa_val_to (lhs, rhs1);
3293 switch (get_gimple_rhs_class (code))
3295 case GIMPLE_UNARY_RHS:
3296 case GIMPLE_BINARY_RHS:
3297 case GIMPLE_TERNARY_RHS:
3298 changed = visit_nary_op (lhs, stmt);
3300 case GIMPLE_SINGLE_RHS:
3301 switch (TREE_CODE_CLASS (code))
3304 /* VOP-less references can go through unary case. */
3305 if ((code == REALPART_EXPR
3306 || code == IMAGPART_EXPR
3307 || code == VIEW_CONVERT_EXPR
3308 || code == BIT_FIELD_REF)
3309 && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
3311 changed = visit_nary_op (lhs, stmt);
3315 case tcc_declaration:
3316 changed = visit_reference_op_load (lhs, rhs1, stmt);
3319 if (code == ADDR_EXPR)
3321 changed = visit_nary_op (lhs, stmt);
3324 else if (code == CONSTRUCTOR)
3326 changed = visit_nary_op (lhs, stmt);
3329 changed = defs_to_varying (stmt);
3333 changed = defs_to_varying (stmt);
3339 changed = defs_to_varying (stmt);
3341 else if (is_gimple_call (stmt))
3343 tree lhs = gimple_call_lhs (stmt);
3345 /* ??? We could try to simplify calls. */
3347 if (stmt_has_constants (stmt)
3348 && TREE_CODE (lhs) == SSA_NAME)
3349 VN_INFO (lhs)->has_constants = true;
3350 else if (TREE_CODE (lhs) == SSA_NAME)
3352 /* We reset expr and constantness here because we may
3353 have been value numbering optimistically, and
3354 iterating. They may become non-constant in this case,
3355 even if they were optimistically constant. */
3356 VN_INFO (lhs)->has_constants = false;
3357 VN_INFO (lhs)->expr = NULL_TREE;
3360 if (TREE_CODE (lhs) == SSA_NAME
3361 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3362 changed = defs_to_varying (stmt);
3363 /* ??? We should handle stores from calls. */
3364 else if (TREE_CODE (lhs) == SSA_NAME)
3366 if (!gimple_call_internal_p (stmt)
3367 && gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
3368 changed = visit_reference_op_call (lhs, stmt);
3370 changed = defs_to_varying (stmt);
3373 changed = defs_to_varying (stmt);
3380 /* Compare two operands by reverse postorder index */
3383 compare_ops (const void *pa, const void *pb)
3385 const tree opa = *((const tree *)pa);
3386 const tree opb = *((const tree *)pb);
3387 gimple opstmta = SSA_NAME_DEF_STMT (opa);
3388 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3392 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3393 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3394 else if (gimple_nop_p (opstmta))
3396 else if (gimple_nop_p (opstmtb))
3399 bba = gimple_bb (opstmta);
3400 bbb = gimple_bb (opstmtb);
3403 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3411 if (gimple_code (opstmta) == GIMPLE_PHI
3412 && gimple_code (opstmtb) == GIMPLE_PHI)
3413 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3414 else if (gimple_code (opstmta) == GIMPLE_PHI)
3416 else if (gimple_code (opstmtb) == GIMPLE_PHI)
3418 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3419 return gimple_uid (opstmta) - gimple_uid (opstmtb);
3421 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3423 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3426 /* Sort an array containing members of a strongly connected component
3427 SCC so that the members are ordered by RPO number.
3428 This means that when the sort is complete, iterating through the
3429 array will give you the members in RPO order. */
3432 sort_scc (VEC (tree, heap) *scc)
3434 VEC_qsort (tree, scc, compare_ops);
3437 /* Insert the no longer used nary ONARY to the hash INFO. */
3440 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3442 size_t size = sizeof_vn_nary_op (onary->length);
3443 vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
3444 &info->nary_obstack);
3445 memcpy (nary, onary, size);
3446 vn_nary_op_insert_into (nary, info->nary, false);
3449 /* Insert the no longer used phi OPHI to the hash INFO. */
3452 copy_phi (vn_phi_t ophi, vn_tables_t info)
3454 vn_phi_t phi = (vn_phi_t) pool_alloc (info->phis_pool);
3456 memcpy (phi, ophi, sizeof (*phi));
3457 ophi->phiargs = NULL;
3458 slot = htab_find_slot_with_hash (info->phis, phi, phi->hashcode, INSERT);
3459 gcc_assert (!*slot);
3463 /* Insert the no longer used reference OREF to the hash INFO. */
3466 copy_reference (vn_reference_t oref, vn_tables_t info)
3470 ref = (vn_reference_t) pool_alloc (info->references_pool);
3471 memcpy (ref, oref, sizeof (*ref));
3472 oref->operands = NULL;
3473 slot = htab_find_slot_with_hash (info->references, ref, ref->hashcode,
3476 free_reference (*slot);
3480 /* Process a strongly connected component in the SSA graph. */
3483 process_scc (VEC (tree, heap) *scc)
3487 unsigned int iterations = 0;
3488 bool changed = true;
3494 /* If the SCC has a single member, just visit it. */
3495 if (VEC_length (tree, scc) == 1)
3497 tree use = VEC_index (tree, scc, 0);
3498 if (VN_INFO (use)->use_processed)
3500 /* We need to make sure it doesn't form a cycle itself, which can
3501 happen for self-referential PHI nodes. In that case we would
3502 end up inserting an expression with VN_TOP operands into the
3503 valid table which makes us derive bogus equivalences later.
3504 The cheapest way to check this is to assume it for all PHI nodes. */
3505 if (gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_PHI)
3506 /* Fallthru to iteration. */ ;
3514 /* Iterate over the SCC with the optimistic table until it stops
3516 current_info = optimistic_info;
3521 if (dump_file && (dump_flags & TDF_DETAILS))
3522 fprintf (dump_file, "Starting iteration %d\n", iterations);
3523 /* As we are value-numbering optimistically we have to
3524 clear the expression tables and the simplified expressions
3525 in each iteration until we converge. */
3526 htab_empty (optimistic_info->nary);
3527 htab_empty (optimistic_info->phis);
3528 htab_empty (optimistic_info->references);
3529 obstack_free (&optimistic_info->nary_obstack, NULL);
3530 gcc_obstack_init (&optimistic_info->nary_obstack);
3531 empty_alloc_pool (optimistic_info->phis_pool);
3532 empty_alloc_pool (optimistic_info->references_pool);
3533 FOR_EACH_VEC_ELT (tree, scc, i, var)
3534 VN_INFO (var)->expr = NULL_TREE;
3535 FOR_EACH_VEC_ELT (tree, scc, i, var)
3536 changed |= visit_use (var);
3539 statistics_histogram_event (cfun, "SCC iterations", iterations);
3541 /* Finally, copy the contents of the no longer used optimistic
3542 table to the valid table. */
3543 FOR_EACH_HTAB_ELEMENT (optimistic_info->nary, nary, vn_nary_op_t, hi)
3544 copy_nary (nary, valid_info);
3545 FOR_EACH_HTAB_ELEMENT (optimistic_info->phis, phi, vn_phi_t, hi)
3546 copy_phi (phi, valid_info);
3547 FOR_EACH_HTAB_ELEMENT (optimistic_info->references, ref, vn_reference_t, hi)
3548 copy_reference (ref, valid_info);
3550 current_info = valid_info;
3553 DEF_VEC_O(ssa_op_iter);
3554 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
3556 /* Pop the components of the found SCC for NAME off the SCC stack
3557 and process them. Returns true if all went well, false if
3558 we run into resource limits. */
3561 extract_and_process_scc_for_name (tree name)
3563 VEC (tree, heap) *scc = NULL;
3566 /* Found an SCC, pop the components off the SCC stack and
3570 x = VEC_pop (tree, sccstack);
3572 VN_INFO (x)->on_sccstack = false;
3573 VEC_safe_push (tree, heap, scc, x);
3574 } while (x != name);
3576 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3577 if (VEC_length (tree, scc)
3578 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
3581 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
3582 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
3583 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
3587 if (VEC_length (tree, scc) > 1)
3590 if (dump_file && (dump_flags & TDF_DETAILS))
3591 print_scc (dump_file, scc);
3595 VEC_free (tree, heap, scc);
3600 /* Depth first search on NAME to discover and process SCC's in the SSA
3602 Execution of this algorithm relies on the fact that the SCC's are
3603 popped off the stack in topological order.
3604 Returns true if successful, false if we stopped processing SCC's due
3605 to resource constraints. */
3610 VEC(ssa_op_iter, heap) *itervec = NULL;
3611 VEC(tree, heap) *namevec = NULL;
3612 use_operand_p usep = NULL;
3619 VN_INFO (name)->dfsnum = next_dfs_num++;
3620 VN_INFO (name)->visited = true;
3621 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
3623 VEC_safe_push (tree, heap, sccstack, name);
3624 VN_INFO (name)->on_sccstack = true;
3625 defstmt = SSA_NAME_DEF_STMT (name);
3627 /* Recursively DFS on our operands, looking for SCC's. */
3628 if (!gimple_nop_p (defstmt))
3630 /* Push a new iterator. */
3631 if (gimple_code (defstmt) == GIMPLE_PHI)
3632 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
3634 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
3637 clear_and_done_ssa_iter (&iter);
3641 /* If we are done processing uses of a name, go up the stack
3642 of iterators and process SCCs as we found them. */
3643 if (op_iter_done (&iter))
3645 /* See if we found an SCC. */
3646 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
3647 if (!extract_and_process_scc_for_name (name))
3649 VEC_free (tree, heap, namevec);
3650 VEC_free (ssa_op_iter, heap, itervec);
3654 /* Check if we are done. */
3655 if (VEC_empty (tree, namevec))
3657 VEC_free (tree, heap, namevec);
3658 VEC_free (ssa_op_iter, heap, itervec);
3662 /* Restore the last use walker and continue walking there. */
3664 name = VEC_pop (tree, namevec);
3665 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
3666 sizeof (ssa_op_iter));
3667 VEC_pop (ssa_op_iter, itervec);
3668 goto continue_walking;
3671 use = USE_FROM_PTR (usep);
3673 /* Since we handle phi nodes, we will sometimes get
3674 invariants in the use expression. */
3675 if (TREE_CODE (use) == SSA_NAME)
3677 if (! (VN_INFO (use)->visited))
3679 /* Recurse by pushing the current use walking state on
3680 the stack and starting over. */
3681 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
3682 VEC_safe_push(tree, heap, namevec, name);
3687 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
3688 VN_INFO (use)->low);
3690 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
3691 && VN_INFO (use)->on_sccstack)
3693 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
3694 VN_INFO (name)->low);
3698 usep = op_iter_next_use (&iter);
3702 /* Allocate a value number table. */
3705 allocate_vn_table (vn_tables_t table)
3707 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
3708 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
3709 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
3712 gcc_obstack_init (&table->nary_obstack);
3713 table->phis_pool = create_alloc_pool ("VN phis",
3714 sizeof (struct vn_phi_s),
3716 table->references_pool = create_alloc_pool ("VN references",
3717 sizeof (struct vn_reference_s),
3721 /* Free a value number table. */
3724 free_vn_table (vn_tables_t table)
3726 htab_delete (table->phis);
3727 htab_delete (table->nary);
3728 htab_delete (table->references);
3729 obstack_free (&table->nary_obstack, NULL);
3730 free_alloc_pool (table->phis_pool);
3731 free_alloc_pool (table->references_pool);
3739 int *rpo_numbers_temp;
3741 calculate_dominance_info (CDI_DOMINATORS);
3743 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
3746 constant_value_ids = BITMAP_ALLOC (NULL);
3751 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
3752 /* VEC_alloc doesn't actually grow it to the right size, it just
3753 preallocates the space to do so. */
3754 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
3755 gcc_obstack_init (&vn_ssa_aux_obstack);
3757 shared_lookup_phiargs = NULL;
3758 shared_lookup_references = NULL;
3759 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3760 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3761 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
3763 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3764 the i'th block in RPO order is bb. We want to map bb's to RPO
3765 numbers, so we need to rearrange this array. */
3766 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
3767 rpo_numbers[rpo_numbers_temp[j]] = j;
3769 XDELETE (rpo_numbers_temp);
3771 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
3773 /* Create the VN_INFO structures, and initialize value numbers to
3775 for (i = 0; i < num_ssa_names; i++)
3777 tree name = ssa_name (i);
3780 VN_INFO_GET (name)->valnum = VN_TOP;
3781 VN_INFO (name)->expr = NULL_TREE;
3782 VN_INFO (name)->value_id = 0;
3786 renumber_gimple_stmt_uids ();
3788 /* Create the valid and optimistic value numbering tables. */
3789 valid_info = XCNEW (struct vn_tables_s);
3790 allocate_vn_table (valid_info);
3791 optimistic_info = XCNEW (struct vn_tables_s);
3792 allocate_vn_table (optimistic_info);
3800 htab_delete (constant_to_value_id);
3801 BITMAP_FREE (constant_value_ids);
3802 VEC_free (tree, heap, shared_lookup_phiargs);
3803 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
3804 XDELETEVEC (rpo_numbers);
3806 for (i = 0; i < num_ssa_names; i++)
3808 tree name = ssa_name (i);
3810 && VN_INFO (name)->needs_insertion)
3811 release_ssa_name (name);
3813 obstack_free (&vn_ssa_aux_obstack, NULL);
3814 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
3816 VEC_free (tree, heap, sccstack);
3817 free_vn_table (valid_info);
3818 XDELETE (valid_info);
3819 free_vn_table (optimistic_info);
3820 XDELETE (optimistic_info);
3823 /* Set *ID if we computed something useful in RESULT. */
3826 set_value_id_for_result (tree result, unsigned int *id)
3830 if (TREE_CODE (result) == SSA_NAME)
3831 *id = VN_INFO (result)->value_id;
3832 else if (is_gimple_min_invariant (result))
3833 *id = get_or_alloc_constant_value_id (result);
3837 /* Set the value ids in the valid hash tables. */
3840 set_hashtable_value_ids (void)
3847 /* Now set the value ids of the things we had put in the hash
3850 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
3851 vno, vn_nary_op_t, hi)
3852 set_value_id_for_result (vno->result, &vno->value_id);
3854 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
3856 set_value_id_for_result (vp->result, &vp->value_id);
3858 FOR_EACH_HTAB_ELEMENT (valid_info->references,
3859 vr, vn_reference_t, hi)
3860 set_value_id_for_result (vr->result, &vr->value_id);
3863 /* Do SCCVN. Returns true if it finished, false if we bailed out
3864 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
3865 how we use the alias oracle walking during the VN process. */
3868 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
3872 bool changed = true;
3874 default_vn_walk_kind = default_vn_walk_kind_;
3877 current_info = valid_info;
3879 for (param = DECL_ARGUMENTS (current_function_decl);
3881 param = DECL_CHAIN (param))
3883 if (gimple_default_def (cfun, param) != NULL)
3885 tree def = gimple_default_def (cfun, param);
3886 VN_INFO (def)->valnum = def;
3890 for (i = 1; i < num_ssa_names; ++i)
3892 tree name = ssa_name (i);
3894 && VN_INFO (name)->visited == false
3895 && !has_zero_uses (name))
3903 /* Initialize the value ids. */
3905 for (i = 1; i < num_ssa_names; ++i)
3907 tree name = ssa_name (i);
3911 info = VN_INFO (name);
3912 if (info->valnum == name
3913 || info->valnum == VN_TOP)
3914 info->value_id = get_next_value_id ();
3915 else if (is_gimple_min_invariant (info->valnum))
3916 info->value_id = get_or_alloc_constant_value_id (info->valnum);
3919 /* Propagate until they stop changing. */
3923 for (i = 1; i < num_ssa_names; ++i)
3925 tree name = ssa_name (i);
3929 info = VN_INFO (name);
3930 if (TREE_CODE (info->valnum) == SSA_NAME
3931 && info->valnum != name
3932 && info->value_id != VN_INFO (info->valnum)->value_id)
3935 info->value_id = VN_INFO (info->valnum)->value_id;
3940 set_hashtable_value_ids ();
3942 if (dump_file && (dump_flags & TDF_DETAILS))
3944 fprintf (dump_file, "Value numbers:\n");
3945 for (i = 0; i < num_ssa_names; i++)
3947 tree name = ssa_name (i);
3949 && VN_INFO (name)->visited
3950 && SSA_VAL (name) != name)
3952 print_generic_expr (dump_file, name, 0);
3953 fprintf (dump_file, " = ");
3954 print_generic_expr (dump_file, SSA_VAL (name), 0);
3955 fprintf (dump_file, "\n");
3963 /* Return the maximum value id we have ever seen. */
3966 get_max_value_id (void)
3968 return next_value_id;
3971 /* Return the next unique value id. */
3974 get_next_value_id (void)
3976 return next_value_id++;
3980 /* Compare two expressions E1 and E2 and return true if they are equal. */
3983 expressions_equal_p (tree e1, tree e2)
3985 /* The obvious case. */
3989 /* If only one of them is null, they cannot be equal. */
3993 /* Now perform the actual comparison. */
3994 if (TREE_CODE (e1) == TREE_CODE (e2)
3995 && operand_equal_p (e1, e2, OEP_PURE_SAME))
4002 /* Return true if the nary operation NARY may trap. This is a copy
4003 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4006 vn_nary_may_trap (vn_nary_op_t nary)
4009 tree rhs2 = NULL_TREE;
4010 bool honor_nans = false;
4011 bool honor_snans = false;
4012 bool fp_operation = false;
4013 bool honor_trapv = false;
4017 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
4018 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
4019 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
4022 fp_operation = FLOAT_TYPE_P (type);
4025 honor_nans = flag_trapping_math && !flag_finite_math_only;
4026 honor_snans = flag_signaling_nans != 0;
4028 else if (INTEGRAL_TYPE_P (type)
4029 && TYPE_OVERFLOW_TRAPS (type))
4032 if (nary->length >= 2)
4034 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
4036 honor_nans, honor_snans, rhs2,
4042 for (i = 0; i < nary->length; ++i)
4043 if (tree_could_trap_p (nary->op[i]))