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;
221 if (vn->valnum == VN_TOP)
224 /* If the value-number is a constant it is the representative
226 if (TREE_CODE (vn->valnum) != SSA_NAME)
229 /* Get to the information of the value of this SSA_NAME. */
230 vn = VN_INFO (vn->valnum);
232 /* If the value-number is a constant it is the representative
234 if (TREE_CODE (vn->valnum) != SSA_NAME)
237 /* Else if we have an expression, return it. */
238 if (vn->expr != NULL_TREE)
241 /* Otherwise use the defining statement to build the expression. */
242 def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
244 /* If the value number is a default-definition or a PHI result
246 if (gimple_nop_p (def_stmt)
247 || gimple_code (def_stmt) == GIMPLE_PHI)
250 if (!is_gimple_assign (def_stmt))
253 /* FIXME tuples. This is incomplete and likely will miss some
255 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)))
258 if ((gimple_assign_rhs_code (def_stmt) == VIEW_CONVERT_EXPR
259 || gimple_assign_rhs_code (def_stmt) == REALPART_EXPR
260 || gimple_assign_rhs_code (def_stmt) == IMAGPART_EXPR)
261 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
262 expr = fold_build1 (gimple_assign_rhs_code (def_stmt),
263 gimple_expr_type (def_stmt),
264 TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0));
268 expr = fold_build1 (gimple_assign_rhs_code (def_stmt),
269 gimple_expr_type (def_stmt),
270 gimple_assign_rhs1 (def_stmt));
274 expr = fold_build2 (gimple_assign_rhs_code (def_stmt),
275 gimple_expr_type (def_stmt),
276 gimple_assign_rhs1 (def_stmt),
277 gimple_assign_rhs2 (def_stmt));
282 if (expr == NULL_TREE)
285 /* Cache the expression. */
292 /* Free a phi operation structure VP. */
297 vn_phi_t phi = (vn_phi_t) vp;
298 VEC_free (tree, heap, phi->phiargs);
301 /* Free a reference operation structure VP. */
304 free_reference (void *vp)
306 vn_reference_t vr = (vn_reference_t) vp;
307 VEC_free (vn_reference_op_s, heap, vr->operands);
310 /* Hash table equality function for vn_constant_t. */
313 vn_constant_eq (const void *p1, const void *p2)
315 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
316 const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
318 if (vc1->hashcode != vc2->hashcode)
321 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
324 /* Hash table hash function for vn_constant_t. */
327 vn_constant_hash (const void *p1)
329 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
330 return vc1->hashcode;
333 /* Lookup a value id for CONSTANT and return it. If it does not
337 get_constant_value_id (tree constant)
340 struct vn_constant_s vc;
342 vc.hashcode = vn_hash_constant_with_type (constant);
343 vc.constant = constant;
344 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
345 vc.hashcode, NO_INSERT);
347 return ((vn_constant_t)*slot)->value_id;
351 /* Lookup a value id for CONSTANT, and if it does not exist, create a
352 new one and return it. If it does exist, return it. */
355 get_or_alloc_constant_value_id (tree constant)
358 struct vn_constant_s vc;
361 vc.hashcode = vn_hash_constant_with_type (constant);
362 vc.constant = constant;
363 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
364 vc.hashcode, INSERT);
366 return ((vn_constant_t)*slot)->value_id;
368 vcp = XNEW (struct vn_constant_s);
369 vcp->hashcode = vc.hashcode;
370 vcp->constant = constant;
371 vcp->value_id = get_next_value_id ();
372 *slot = (void *) vcp;
373 bitmap_set_bit (constant_value_ids, vcp->value_id);
374 return vcp->value_id;
377 /* Return true if V is a value id for a constant. */
380 value_id_constant_p (unsigned int v)
382 return bitmap_bit_p (constant_value_ids, v);
385 /* Compare two reference operands P1 and P2 for equality. Return true if
386 they are equal, and false otherwise. */
389 vn_reference_op_eq (const void *p1, const void *p2)
391 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
392 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
394 return (vro1->opcode == vro2->opcode
395 /* We do not care for differences in type qualification. */
396 && (vro1->type == vro2->type
397 || (vro1->type && vro2->type
398 && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type),
399 TYPE_MAIN_VARIANT (vro2->type))))
400 && expressions_equal_p (vro1->op0, vro2->op0)
401 && expressions_equal_p (vro1->op1, vro2->op1)
402 && expressions_equal_p (vro1->op2, vro2->op2));
405 /* Compute the hash for a reference operand VRO1. */
408 vn_reference_op_compute_hash (const vn_reference_op_t vro1, hashval_t result)
410 result = iterative_hash_hashval_t (vro1->opcode, result);
412 result = iterative_hash_expr (vro1->op0, result);
414 result = iterative_hash_expr (vro1->op1, result);
416 result = iterative_hash_expr (vro1->op2, result);
420 /* Return the hashcode for a given reference operation P1. */
423 vn_reference_hash (const void *p1)
425 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
426 return vr1->hashcode;
429 /* Compute a hash for the reference operation VR1 and return it. */
432 vn_reference_compute_hash (const vn_reference_t vr1)
434 hashval_t result = 0;
436 vn_reference_op_t vro;
437 HOST_WIDE_INT off = -1;
440 FOR_EACH_VEC_ELT (vn_reference_op_s, vr1->operands, i, vro)
442 if (vro->opcode == MEM_REF)
444 else if (vro->opcode != ADDR_EXPR)
456 result = iterative_hash_hashval_t (off, result);
459 && vro->opcode == ADDR_EXPR)
463 tree op = TREE_OPERAND (vro->op0, 0);
464 result = iterative_hash_hashval_t (TREE_CODE (op), result);
465 result = iterative_hash_expr (op, result);
469 result = vn_reference_op_compute_hash (vro, result);
473 result += SSA_NAME_VERSION (vr1->vuse);
478 /* Return true if reference operations P1 and P2 are equivalent. This
479 means they have the same set of operands and vuses. */
482 vn_reference_eq (const void *p1, const void *p2)
486 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
487 const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
488 if (vr1->hashcode != vr2->hashcode)
491 /* Early out if this is not a hash collision. */
492 if (vr1->hashcode != vr2->hashcode)
495 /* The VOP needs to be the same. */
496 if (vr1->vuse != vr2->vuse)
499 /* If the operands are the same we are done. */
500 if (vr1->operands == vr2->operands)
503 if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
506 if (INTEGRAL_TYPE_P (vr1->type)
507 && INTEGRAL_TYPE_P (vr2->type))
509 if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
512 else if (INTEGRAL_TYPE_P (vr1->type)
513 && (TYPE_PRECISION (vr1->type)
514 != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
516 else if (INTEGRAL_TYPE_P (vr2->type)
517 && (TYPE_PRECISION (vr2->type)
518 != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
525 HOST_WIDE_INT off1 = 0, off2 = 0;
526 vn_reference_op_t vro1, vro2;
527 vn_reference_op_s tem1, tem2;
528 bool deref1 = false, deref2 = false;
529 for (; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro1); i++)
531 if (vro1->opcode == MEM_REF)
537 for (; VEC_iterate (vn_reference_op_s, vr2->operands, j, vro2); j++)
539 if (vro2->opcode == MEM_REF)
547 if (deref1 && vro1->opcode == ADDR_EXPR)
549 memset (&tem1, 0, sizeof (tem1));
550 tem1.op0 = TREE_OPERAND (vro1->op0, 0);
551 tem1.type = TREE_TYPE (tem1.op0);
552 tem1.opcode = TREE_CODE (tem1.op0);
555 if (deref2 && vro2->opcode == ADDR_EXPR)
557 memset (&tem2, 0, sizeof (tem2));
558 tem2.op0 = TREE_OPERAND (vro2->op0, 0);
559 tem2.type = TREE_TYPE (tem2.op0);
560 tem2.opcode = TREE_CODE (tem2.op0);
563 if (!vn_reference_op_eq (vro1, vro2))
568 while (VEC_length (vn_reference_op_s, vr1->operands) != i
569 || VEC_length (vn_reference_op_s, vr2->operands) != j);
574 /* Copy the operations present in load/store REF into RESULT, a vector of
575 vn_reference_op_s's. */
578 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
580 if (TREE_CODE (ref) == TARGET_MEM_REF)
582 vn_reference_op_s temp;
584 memset (&temp, 0, sizeof (temp));
585 temp.type = TREE_TYPE (ref);
586 temp.opcode = TREE_CODE (ref);
587 temp.op0 = TMR_INDEX (ref);
588 temp.op1 = TMR_STEP (ref);
589 temp.op2 = TMR_OFFSET (ref);
591 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
593 memset (&temp, 0, sizeof (temp));
594 temp.type = NULL_TREE;
595 temp.opcode = ERROR_MARK;
596 temp.op0 = TMR_INDEX2 (ref);
598 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
600 memset (&temp, 0, sizeof (temp));
601 temp.type = NULL_TREE;
602 temp.opcode = TREE_CODE (TMR_BASE (ref));
603 temp.op0 = TMR_BASE (ref);
605 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
609 /* For non-calls, store the information that makes up the address. */
613 vn_reference_op_s temp;
615 memset (&temp, 0, sizeof (temp));
616 temp.type = TREE_TYPE (ref);
617 temp.opcode = TREE_CODE (ref);
623 /* The base address gets its own vn_reference_op_s structure. */
624 temp.op0 = TREE_OPERAND (ref, 1);
625 if (host_integerp (TREE_OPERAND (ref, 1), 0))
626 temp.off = TREE_INT_CST_LOW (TREE_OPERAND (ref, 1));
629 /* Record bits and position. */
630 temp.op0 = TREE_OPERAND (ref, 1);
631 temp.op1 = TREE_OPERAND (ref, 2);
634 /* The field decl is enough to unambiguously specify the field,
635 a matching type is not necessary and a mismatching type
636 is always a spurious difference. */
637 temp.type = NULL_TREE;
638 temp.op0 = TREE_OPERAND (ref, 1);
639 temp.op1 = TREE_OPERAND (ref, 2);
641 tree this_offset = component_ref_field_offset (ref);
643 && TREE_CODE (this_offset) == INTEGER_CST)
645 tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
646 if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0)
649 = double_int_add (tree_to_double_int (this_offset),
651 (tree_to_double_int (bit_offset),
653 ? 3 : exact_log2 (BITS_PER_UNIT),
654 HOST_BITS_PER_DOUBLE_INT, true));
655 if (double_int_fits_in_shwi_p (off))
661 case ARRAY_RANGE_REF:
663 /* Record index as operand. */
664 temp.op0 = TREE_OPERAND (ref, 1);
665 /* Always record lower bounds and element size. */
666 temp.op1 = array_ref_low_bound (ref);
667 temp.op2 = array_ref_element_size (ref);
668 if (TREE_CODE (temp.op0) == INTEGER_CST
669 && TREE_CODE (temp.op1) == INTEGER_CST
670 && TREE_CODE (temp.op2) == INTEGER_CST)
672 double_int off = tree_to_double_int (temp.op0);
673 off = double_int_add (off,
675 (tree_to_double_int (temp.op1)));
676 off = double_int_mul (off, tree_to_double_int (temp.op2));
677 if (double_int_fits_in_shwi_p (off))
682 if (DECL_HARD_REGISTER (ref))
691 /* Canonicalize decls to MEM[&decl] which is what we end up with
692 when valueizing MEM[ptr] with ptr = &decl. */
693 temp.opcode = MEM_REF;
694 temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0);
696 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
697 temp.opcode = ADDR_EXPR;
698 temp.op0 = build_fold_addr_expr (ref);
699 temp.type = TREE_TYPE (temp.op0);
712 if (is_gimple_min_invariant (ref))
718 /* These are only interesting for their operands, their
719 existence, and their type. They will never be the last
720 ref in the chain of references (IE they require an
721 operand), so we don't have to put anything
722 for op* as it will be handled by the iteration */
724 case VIEW_CONVERT_EXPR:
728 /* This is only interesting for its constant offset. */
729 temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
734 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
736 if (REFERENCE_CLASS_P (ref)
737 || (TREE_CODE (ref) == ADDR_EXPR
738 && !is_gimple_min_invariant (ref)))
739 ref = TREE_OPERAND (ref, 0);
745 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
746 operands in *OPS, the reference alias set SET and the reference type TYPE.
747 Return true if something useful was produced. */
750 ao_ref_init_from_vn_reference (ao_ref *ref,
751 alias_set_type set, tree type,
752 VEC (vn_reference_op_s, heap) *ops)
754 vn_reference_op_t op;
756 tree base = NULL_TREE;
758 HOST_WIDE_INT offset = 0;
759 HOST_WIDE_INT max_size;
760 HOST_WIDE_INT size = -1;
761 tree size_tree = NULL_TREE;
762 alias_set_type base_alias_set = -1;
764 /* First get the final access size from just the outermost expression. */
765 op = VEC_index (vn_reference_op_s, ops, 0);
766 if (op->opcode == COMPONENT_REF)
767 size_tree = DECL_SIZE (op->op0);
768 else if (op->opcode == BIT_FIELD_REF)
772 enum machine_mode mode = TYPE_MODE (type);
774 size_tree = TYPE_SIZE (type);
776 size = GET_MODE_BITSIZE (mode);
778 if (size_tree != NULL_TREE)
780 if (!host_integerp (size_tree, 1))
783 size = TREE_INT_CST_LOW (size_tree);
786 /* Initially, maxsize is the same as the accessed element size.
787 In the following it will only grow (or become -1). */
790 /* Compute cumulative bit-offset for nested component-refs and array-refs,
791 and find the ultimate containing object. */
792 FOR_EACH_VEC_ELT (vn_reference_op_s, ops, i, op)
796 /* These may be in the reference ops, but we cannot do anything
797 sensible with them here. */
799 /* Apart from ADDR_EXPR arguments to MEM_REF. */
800 if (base != NULL_TREE
801 && TREE_CODE (base) == MEM_REF
803 && DECL_P (TREE_OPERAND (op->op0, 0)))
805 vn_reference_op_t pop = VEC_index (vn_reference_op_s, ops, i-1);
806 base = TREE_OPERAND (op->op0, 0);
813 offset += pop->off * BITS_PER_UNIT;
821 /* Record the base objects. */
823 base_alias_set = get_deref_alias_set (op->op0);
824 *op0_p = build2 (MEM_REF, op->type,
826 op0_p = &TREE_OPERAND (*op0_p, 0);
837 /* And now the usual component-reference style ops. */
839 offset += tree_low_cst (op->op1, 0);
844 tree field = op->op0;
845 /* We do not have a complete COMPONENT_REF tree here so we
846 cannot use component_ref_field_offset. Do the interesting
850 || !host_integerp (DECL_FIELD_OFFSET (field), 1))
854 offset += (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field))
856 offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
861 case ARRAY_RANGE_REF:
863 /* We recorded the lower bound and the element size. */
864 if (!host_integerp (op->op0, 0)
865 || !host_integerp (op->op1, 0)
866 || !host_integerp (op->op2, 0))
870 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (op->op0);
871 hindex -= TREE_INT_CST_LOW (op->op1);
872 hindex *= TREE_INT_CST_LOW (op->op2);
873 hindex *= BITS_PER_UNIT;
885 case VIEW_CONVERT_EXPR:
902 if (base == NULL_TREE)
905 ref->ref = NULL_TREE;
907 ref->offset = offset;
909 ref->max_size = max_size;
910 ref->ref_alias_set = set;
911 if (base_alias_set != -1)
912 ref->base_alias_set = base_alias_set;
914 ref->base_alias_set = get_alias_set (base);
919 /* Copy the operations present in load/store/call REF into RESULT, a vector of
920 vn_reference_op_s's. */
923 copy_reference_ops_from_call (gimple call,
924 VEC(vn_reference_op_s, heap) **result)
926 vn_reference_op_s temp;
929 /* Copy the type, opcode, function being called and static chain. */
930 memset (&temp, 0, sizeof (temp));
931 temp.type = gimple_call_return_type (call);
932 temp.opcode = CALL_EXPR;
933 temp.op0 = gimple_call_fn (call);
934 temp.op1 = gimple_call_chain (call);
936 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
938 /* Copy the call arguments. As they can be references as well,
939 just chain them together. */
940 for (i = 0; i < gimple_call_num_args (call); ++i)
942 tree callarg = gimple_call_arg (call, i);
943 copy_reference_ops_from_ref (callarg, result);
947 /* Create a vector of vn_reference_op_s structures from REF, a
948 REFERENCE_CLASS_P tree. The vector is not shared. */
950 static VEC(vn_reference_op_s, heap) *
951 create_reference_ops_from_ref (tree ref)
953 VEC (vn_reference_op_s, heap) *result = NULL;
955 copy_reference_ops_from_ref (ref, &result);
959 /* Create a vector of vn_reference_op_s structures from CALL, a
960 call statement. The vector is not shared. */
962 static VEC(vn_reference_op_s, heap) *
963 create_reference_ops_from_call (gimple call)
965 VEC (vn_reference_op_s, heap) *result = NULL;
967 copy_reference_ops_from_call (call, &result);
971 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
972 *I_P to point to the last element of the replacement. */
974 vn_reference_fold_indirect (VEC (vn_reference_op_s, heap) **ops,
977 unsigned int i = *i_p;
978 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
979 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
981 HOST_WIDE_INT addr_offset;
983 /* The only thing we have to do is from &OBJ.foo.bar add the offset
984 from .foo.bar to the preceeding MEM_REF offset and replace the
985 address with &OBJ. */
986 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
988 gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
989 if (addr_base != op->op0)
991 double_int off = tree_to_double_int (mem_op->op0);
992 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
993 off = double_int_add (off, shwi_to_double_int (addr_offset));
994 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
995 op->op0 = build_fold_addr_expr (addr_base);
996 if (host_integerp (mem_op->op0, 0))
997 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1003 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1004 *I_P to point to the last element of the replacement. */
1006 vn_reference_maybe_forwprop_address (VEC (vn_reference_op_s, heap) **ops,
1009 unsigned int i = *i_p;
1010 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
1011 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
1013 enum tree_code code;
1016 def_stmt = SSA_NAME_DEF_STMT (op->op0);
1017 if (!is_gimple_assign (def_stmt))
1020 code = gimple_assign_rhs_code (def_stmt);
1021 if (code != ADDR_EXPR
1022 && code != POINTER_PLUS_EXPR)
1025 off = tree_to_double_int (mem_op->op0);
1026 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
1028 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1029 from .foo.bar to the preceeding MEM_REF offset and replace the
1030 address with &OBJ. */
1031 if (code == ADDR_EXPR)
1033 tree addr, addr_base;
1034 HOST_WIDE_INT addr_offset;
1036 addr = gimple_assign_rhs1 (def_stmt);
1037 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1040 || TREE_CODE (addr_base) != MEM_REF)
1043 off = double_int_add (off, shwi_to_double_int (addr_offset));
1044 off = double_int_add (off, mem_ref_offset (addr_base));
1045 op->op0 = TREE_OPERAND (addr_base, 0);
1050 ptr = gimple_assign_rhs1 (def_stmt);
1051 ptroff = gimple_assign_rhs2 (def_stmt);
1052 if (TREE_CODE (ptr) != SSA_NAME
1053 || TREE_CODE (ptroff) != INTEGER_CST)
1056 off = double_int_add (off, tree_to_double_int (ptroff));
1060 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
1061 if (host_integerp (mem_op->op0, 0))
1062 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1065 if (TREE_CODE (op->op0) == SSA_NAME)
1066 op->op0 = SSA_VAL (op->op0);
1067 if (TREE_CODE (op->op0) != SSA_NAME)
1068 op->opcode = TREE_CODE (op->op0);
1071 if (TREE_CODE (op->op0) == SSA_NAME)
1072 vn_reference_maybe_forwprop_address (ops, i_p);
1073 else if (TREE_CODE (op->op0) == ADDR_EXPR)
1074 vn_reference_fold_indirect (ops, i_p);
1077 /* Optimize the reference REF to a constant if possible or return
1078 NULL_TREE if not. */
1081 fully_constant_vn_reference_p (vn_reference_t ref)
1083 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1084 vn_reference_op_t op;
1086 /* Try to simplify the translated expression if it is
1087 a call to a builtin function with at most two arguments. */
1088 op = VEC_index (vn_reference_op_s, operands, 0);
1089 if (op->opcode == CALL_EXPR
1090 && TREE_CODE (op->op0) == ADDR_EXPR
1091 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1092 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1093 && VEC_length (vn_reference_op_s, operands) >= 2
1094 && VEC_length (vn_reference_op_s, operands) <= 3)
1096 vn_reference_op_t arg0, arg1 = NULL;
1097 bool anyconst = false;
1098 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1099 if (VEC_length (vn_reference_op_s, operands) > 2)
1100 arg1 = VEC_index (vn_reference_op_s, operands, 2);
1101 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1102 || (arg0->opcode == ADDR_EXPR
1103 && is_gimple_min_invariant (arg0->op0)))
1106 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1107 || (arg1->opcode == ADDR_EXPR
1108 && is_gimple_min_invariant (arg1->op0))))
1112 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1115 arg1 ? arg1->op0 : NULL);
1117 && TREE_CODE (folded) == NOP_EXPR)
1118 folded = TREE_OPERAND (folded, 0);
1120 && is_gimple_min_invariant (folded))
1125 /* Simplify reads from constant strings. */
1126 else if (op->opcode == ARRAY_REF
1127 && TREE_CODE (op->op0) == INTEGER_CST
1128 && integer_zerop (op->op1)
1129 && VEC_length (vn_reference_op_s, operands) == 2)
1131 vn_reference_op_t arg0;
1132 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1133 if (arg0->opcode == STRING_CST
1134 && (TYPE_MODE (op->type)
1135 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0->op0))))
1136 && GET_MODE_CLASS (TYPE_MODE (op->type)) == MODE_INT
1137 && GET_MODE_SIZE (TYPE_MODE (op->type)) == 1
1138 && compare_tree_int (op->op0, TREE_STRING_LENGTH (arg0->op0)) < 0)
1139 return build_int_cst_type (op->type,
1140 (TREE_STRING_POINTER (arg0->op0)
1141 [TREE_INT_CST_LOW (op->op0)]));
1147 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1148 structures into their value numbers. This is done in-place, and
1149 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1150 whether any operands were valueized. */
1152 static VEC (vn_reference_op_s, heap) *
1153 valueize_refs_1 (VEC (vn_reference_op_s, heap) *orig, bool *valueized_anything)
1155 vn_reference_op_t vro;
1158 *valueized_anything = false;
1160 FOR_EACH_VEC_ELT (vn_reference_op_s, orig, i, vro)
1162 if (vro->opcode == SSA_NAME
1163 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1165 tree tem = SSA_VAL (vro->op0);
1166 if (tem != vro->op0)
1168 *valueized_anything = true;
1171 /* If it transforms from an SSA_NAME to a constant, update
1173 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1174 vro->opcode = TREE_CODE (vro->op0);
1176 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1178 tree tem = SSA_VAL (vro->op1);
1179 if (tem != vro->op1)
1181 *valueized_anything = true;
1185 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1187 tree tem = SSA_VAL (vro->op2);
1188 if (tem != vro->op2)
1190 *valueized_anything = true;
1194 /* If it transforms from an SSA_NAME to an address, fold with
1195 a preceding indirect reference. */
1198 && TREE_CODE (vro->op0) == ADDR_EXPR
1199 && VEC_index (vn_reference_op_s,
1200 orig, i - 1)->opcode == MEM_REF)
1201 vn_reference_fold_indirect (&orig, &i);
1203 && vro->opcode == SSA_NAME
1204 && VEC_index (vn_reference_op_s,
1205 orig, i - 1)->opcode == MEM_REF)
1206 vn_reference_maybe_forwprop_address (&orig, &i);
1207 /* If it transforms a non-constant ARRAY_REF into a constant
1208 one, adjust the constant offset. */
1209 else if (vro->opcode == ARRAY_REF
1211 && TREE_CODE (vro->op0) == INTEGER_CST
1212 && TREE_CODE (vro->op1) == INTEGER_CST
1213 && TREE_CODE (vro->op2) == INTEGER_CST)
1215 double_int off = tree_to_double_int (vro->op0);
1216 off = double_int_add (off,
1218 (tree_to_double_int (vro->op1)));
1219 off = double_int_mul (off, tree_to_double_int (vro->op2));
1220 if (double_int_fits_in_shwi_p (off))
1228 static VEC (vn_reference_op_s, heap) *
1229 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
1232 return valueize_refs_1 (orig, &tem);
1235 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
1237 /* Create a vector of vn_reference_op_s structures from REF, a
1238 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1239 this function. *VALUEIZED_ANYTHING will specify whether any
1240 operands were valueized. */
1242 static VEC(vn_reference_op_s, heap) *
1243 valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything)
1247 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1248 copy_reference_ops_from_ref (ref, &shared_lookup_references);
1249 shared_lookup_references = valueize_refs_1 (shared_lookup_references,
1250 valueized_anything);
1251 return shared_lookup_references;
1254 /* Create a vector of vn_reference_op_s structures from CALL, a
1255 call statement. The vector is shared among all callers of
1258 static VEC(vn_reference_op_s, heap) *
1259 valueize_shared_reference_ops_from_call (gimple call)
1263 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1264 copy_reference_ops_from_call (call, &shared_lookup_references);
1265 shared_lookup_references = valueize_refs (shared_lookup_references);
1266 return shared_lookup_references;
1269 /* Lookup a SCCVN reference operation VR in the current hash table.
1270 Returns the resulting value number if it exists in the hash table,
1271 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1272 vn_reference_t stored in the hashtable if something is found. */
1275 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1280 hash = vr->hashcode;
1281 slot = htab_find_slot_with_hash (current_info->references, vr,
1283 if (!slot && current_info == optimistic_info)
1284 slot = htab_find_slot_with_hash (valid_info->references, vr,
1289 *vnresult = (vn_reference_t)*slot;
1290 return ((vn_reference_t)*slot)->result;
1296 static tree *last_vuse_ptr;
1297 static vn_lookup_kind vn_walk_kind;
1298 static vn_lookup_kind default_vn_walk_kind;
1300 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1301 with the current VUSE and performs the expression lookup. */
1304 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
1306 vn_reference_t vr = (vn_reference_t)vr_;
1311 *last_vuse_ptr = vuse;
1313 /* Fixup vuse and hash. */
1315 vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1316 vr->vuse = SSA_VAL (vuse);
1318 vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1320 hash = vr->hashcode;
1321 slot = htab_find_slot_with_hash (current_info->references, vr,
1323 if (!slot && current_info == optimistic_info)
1324 slot = htab_find_slot_with_hash (valid_info->references, vr,
1332 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1333 from the statement defining VUSE and if not successful tries to
1334 translate *REFP and VR_ through an aggregate copy at the defintion
1338 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_)
1340 vn_reference_t vr = (vn_reference_t)vr_;
1341 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1343 HOST_WIDE_INT offset, maxsize;
1344 static VEC (vn_reference_op_s, heap) *lhs_ops = NULL;
1346 bool lhs_ref_ok = false;
1348 /* First try to disambiguate after value-replacing in the definitions LHS. */
1349 if (is_gimple_assign (def_stmt))
1351 VEC (vn_reference_op_s, heap) *tem;
1352 tree lhs = gimple_assign_lhs (def_stmt);
1353 /* Avoid re-allocation overhead. */
1354 VEC_truncate (vn_reference_op_s, lhs_ops, 0);
1355 copy_reference_ops_from_ref (lhs, &lhs_ops);
1357 lhs_ops = valueize_refs (lhs_ops);
1358 gcc_assert (lhs_ops == tem);
1359 lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref, get_alias_set (lhs),
1360 TREE_TYPE (lhs), lhs_ops);
1362 && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1366 base = ao_ref_base (ref);
1367 offset = ref->offset;
1368 maxsize = ref->max_size;
1370 /* If we cannot constrain the size of the reference we cannot
1371 test if anything kills it. */
1375 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1376 from that defintion.
1378 if (is_gimple_reg_type (vr->type)
1379 && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
1380 && integer_zerop (gimple_call_arg (def_stmt, 1))
1381 && host_integerp (gimple_call_arg (def_stmt, 2), 1)
1382 && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1384 tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1386 HOST_WIDE_INT offset2, size2, maxsize2;
1387 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1388 size2 = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2)) * 8;
1389 if ((unsigned HOST_WIDE_INT)size2 / 8
1390 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2))
1392 && operand_equal_p (base, base2, 0)
1393 && offset2 <= offset
1394 && offset2 + size2 >= offset + maxsize)
1396 tree val = build_zero_cst (vr->type);
1397 unsigned int value_id = get_or_alloc_constant_value_id (val);
1398 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1399 VEC_copy (vn_reference_op_s,
1400 heap, vr->operands),
1405 /* 2) Assignment from an empty CONSTRUCTOR. */
1406 else if (is_gimple_reg_type (vr->type)
1407 && gimple_assign_single_p (def_stmt)
1408 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1409 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1412 HOST_WIDE_INT offset2, size2, maxsize2;
1413 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1414 &offset2, &size2, &maxsize2);
1416 && operand_equal_p (base, base2, 0)
1417 && offset2 <= offset
1418 && offset2 + size2 >= offset + maxsize)
1420 tree val = build_zero_cst (vr->type);
1421 unsigned int value_id = get_or_alloc_constant_value_id (val);
1422 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1423 VEC_copy (vn_reference_op_s,
1424 heap, vr->operands),
1429 /* 3) For aggregate copies translate the reference through them if
1430 the copy kills ref. */
1431 else if (vn_walk_kind == VN_WALKREWRITE
1432 && gimple_assign_single_p (def_stmt)
1433 && (DECL_P (gimple_assign_rhs1 (def_stmt))
1434 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
1435 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1438 HOST_WIDE_INT offset2, size2, maxsize2;
1440 VEC (vn_reference_op_s, heap) *rhs = NULL;
1441 vn_reference_op_t vro;
1447 /* See if the assignment kills REF. */
1448 base2 = ao_ref_base (&lhs_ref);
1449 offset2 = lhs_ref.offset;
1450 size2 = lhs_ref.size;
1451 maxsize2 = lhs_ref.max_size;
1453 || (base != base2 && !operand_equal_p (base, base2, 0))
1455 || offset2 + size2 < offset + maxsize)
1458 /* Find the common base of ref and the lhs. lhs_ops already
1459 contains valueized operands for the lhs. */
1460 i = VEC_length (vn_reference_op_s, vr->operands) - 1;
1461 j = VEC_length (vn_reference_op_s, lhs_ops) - 1;
1462 while (j >= 0 && i >= 0
1463 && vn_reference_op_eq (VEC_index (vn_reference_op_s,
1465 VEC_index (vn_reference_op_s, lhs_ops, j)))
1471 /* i now points to the first additional op.
1472 ??? LHS may not be completely contained in VR, one or more
1473 VIEW_CONVERT_EXPRs could be in its way. We could at least
1474 try handling outermost VIEW_CONVERT_EXPRs. */
1478 /* Now re-write REF to be based on the rhs of the assignment. */
1479 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1480 /* We need to pre-pend vr->operands[0..i] to rhs. */
1481 if (i + 1 + VEC_length (vn_reference_op_s, rhs)
1482 > VEC_length (vn_reference_op_s, vr->operands))
1484 VEC (vn_reference_op_s, heap) *old = vr->operands;
1485 VEC_safe_grow (vn_reference_op_s, heap, vr->operands,
1486 i + 1 + VEC_length (vn_reference_op_s, rhs));
1487 if (old == shared_lookup_references
1488 && vr->operands != old)
1489 shared_lookup_references = NULL;
1492 VEC_truncate (vn_reference_op_s, vr->operands,
1493 i + 1 + VEC_length (vn_reference_op_s, rhs));
1494 FOR_EACH_VEC_ELT (vn_reference_op_s, rhs, j, vro)
1495 VEC_replace (vn_reference_op_s, vr->operands, i + 1 + j, vro);
1496 VEC_free (vn_reference_op_s, heap, rhs);
1497 vr->hashcode = vn_reference_compute_hash (vr);
1499 /* Adjust *ref from the new operands. */
1500 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1502 /* This can happen with bitfields. */
1503 if (ref->size != r.size)
1507 /* Do not update last seen VUSE after translating. */
1508 last_vuse_ptr = NULL;
1510 /* Keep looking for the adjusted *REF / VR pair. */
1514 /* 4) For memcpy copies translate the reference through them if
1515 the copy kills ref. */
1516 else if (vn_walk_kind == VN_WALKREWRITE
1517 && is_gimple_reg_type (vr->type)
1518 /* ??? Handle BCOPY as well. */
1519 && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
1520 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
1521 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
1522 && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
1523 || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
1524 && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
1525 || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
1526 && host_integerp (gimple_call_arg (def_stmt, 2), 1))
1530 HOST_WIDE_INT rhs_offset, copy_size, lhs_offset;
1531 vn_reference_op_s op;
1535 /* Only handle non-variable, addressable refs. */
1536 if (ref->size != maxsize
1537 || offset % BITS_PER_UNIT != 0
1538 || ref->size % BITS_PER_UNIT != 0)
1541 /* Extract a pointer base and an offset for the destination. */
1542 lhs = gimple_call_arg (def_stmt, 0);
1544 if (TREE_CODE (lhs) == SSA_NAME)
1545 lhs = SSA_VAL (lhs);
1546 if (TREE_CODE (lhs) == ADDR_EXPR)
1548 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
1552 if (TREE_CODE (tem) == MEM_REF
1553 && host_integerp (TREE_OPERAND (tem, 1), 1))
1555 lhs = TREE_OPERAND (tem, 0);
1556 lhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1558 else if (DECL_P (tem))
1559 lhs = build_fold_addr_expr (tem);
1563 if (TREE_CODE (lhs) != SSA_NAME
1564 && TREE_CODE (lhs) != ADDR_EXPR)
1567 /* Extract a pointer base and an offset for the source. */
1568 rhs = gimple_call_arg (def_stmt, 1);
1570 if (TREE_CODE (rhs) == SSA_NAME)
1571 rhs = SSA_VAL (rhs);
1572 if (TREE_CODE (rhs) == ADDR_EXPR)
1574 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
1578 if (TREE_CODE (tem) == MEM_REF
1579 && host_integerp (TREE_OPERAND (tem, 1), 1))
1581 rhs = TREE_OPERAND (tem, 0);
1582 rhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1584 else if (DECL_P (tem))
1585 rhs = build_fold_addr_expr (tem);
1589 if (TREE_CODE (rhs) != SSA_NAME
1590 && TREE_CODE (rhs) != ADDR_EXPR)
1593 copy_size = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2));
1595 /* The bases of the destination and the references have to agree. */
1596 if ((TREE_CODE (base) != MEM_REF
1598 || (TREE_CODE (base) == MEM_REF
1599 && (TREE_OPERAND (base, 0) != lhs
1600 || !host_integerp (TREE_OPERAND (base, 1), 1)))
1602 && (TREE_CODE (lhs) != ADDR_EXPR
1603 || TREE_OPERAND (lhs, 0) != base)))
1606 /* And the access has to be contained within the memcpy destination. */
1607 at = offset / BITS_PER_UNIT;
1608 if (TREE_CODE (base) == MEM_REF)
1609 at += TREE_INT_CST_LOW (TREE_OPERAND (base, 1));
1611 || lhs_offset + copy_size < at + maxsize / BITS_PER_UNIT)
1614 /* Make room for 2 operands in the new reference. */
1615 if (VEC_length (vn_reference_op_s, vr->operands) < 2)
1617 VEC (vn_reference_op_s, heap) *old = vr->operands;
1618 VEC_safe_grow (vn_reference_op_s, heap, vr->operands, 2);
1619 if (old == shared_lookup_references
1620 && vr->operands != old)
1621 shared_lookup_references = NULL;
1624 VEC_truncate (vn_reference_op_s, vr->operands, 2);
1626 /* The looked-through reference is a simple MEM_REF. */
1627 memset (&op, 0, sizeof (op));
1629 op.opcode = MEM_REF;
1630 op.op0 = build_int_cst (ptr_type_node, at - rhs_offset);
1631 op.off = at - lhs_offset + rhs_offset;
1632 VEC_replace (vn_reference_op_s, vr->operands, 0, &op);
1633 op.type = TREE_TYPE (rhs);
1634 op.opcode = TREE_CODE (rhs);
1637 VEC_replace (vn_reference_op_s, vr->operands, 1, &op);
1638 vr->hashcode = vn_reference_compute_hash (vr);
1640 /* Adjust *ref from the new operands. */
1641 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1643 /* This can happen with bitfields. */
1644 if (ref->size != r.size)
1648 /* Do not update last seen VUSE after translating. */
1649 last_vuse_ptr = NULL;
1651 /* Keep looking for the adjusted *REF / VR pair. */
1655 /* Bail out and stop walking. */
1659 /* Lookup a reference operation by it's parts, in the current hash table.
1660 Returns the resulting value number if it exists in the hash table,
1661 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1662 vn_reference_t stored in the hashtable if something is found. */
1665 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
1666 VEC (vn_reference_op_s, heap) *operands,
1667 vn_reference_t *vnresult, vn_lookup_kind kind)
1669 struct vn_reference_s vr1;
1677 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1678 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1679 VEC_safe_grow (vn_reference_op_s, heap, shared_lookup_references,
1680 VEC_length (vn_reference_op_s, operands));
1681 memcpy (VEC_address (vn_reference_op_s, shared_lookup_references),
1682 VEC_address (vn_reference_op_s, operands),
1683 sizeof (vn_reference_op_s)
1684 * VEC_length (vn_reference_op_s, operands));
1685 vr1.operands = operands = shared_lookup_references
1686 = valueize_refs (shared_lookup_references);
1689 vr1.hashcode = vn_reference_compute_hash (&vr1);
1690 if ((cst = fully_constant_vn_reference_p (&vr1)))
1693 vn_reference_lookup_1 (&vr1, vnresult);
1695 && kind != VN_NOWALK
1699 vn_walk_kind = kind;
1700 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
1702 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1703 vn_reference_lookup_2,
1704 vn_reference_lookup_3, &vr1);
1705 if (vr1.operands != operands)
1706 VEC_free (vn_reference_op_s, heap, vr1.operands);
1710 return (*vnresult)->result;
1715 /* Lookup OP in the current hash table, and return the resulting value
1716 number if it exists in the hash table. Return NULL_TREE if it does
1717 not exist in the hash table or if the result field of the structure
1718 was NULL.. VNRESULT will be filled in with the vn_reference_t
1719 stored in the hashtable if one exists. */
1722 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
1723 vn_reference_t *vnresult)
1725 VEC (vn_reference_op_s, heap) *operands;
1726 struct vn_reference_s vr1;
1728 bool valuezied_anything;
1733 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1734 vr1.operands = operands
1735 = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
1736 vr1.type = TREE_TYPE (op);
1737 vr1.set = get_alias_set (op);
1738 vr1.hashcode = vn_reference_compute_hash (&vr1);
1739 if ((cst = fully_constant_vn_reference_p (&vr1)))
1742 if (kind != VN_NOWALK
1745 vn_reference_t wvnresult;
1747 /* Make sure to use a valueized reference if we valueized anything.
1748 Otherwise preserve the full reference for advanced TBAA. */
1749 if (!valuezied_anything
1750 || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
1752 ao_ref_init (&r, op);
1753 vn_walk_kind = kind;
1755 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1756 vn_reference_lookup_2,
1757 vn_reference_lookup_3, &vr1);
1758 if (vr1.operands != operands)
1759 VEC_free (vn_reference_op_s, heap, vr1.operands);
1763 *vnresult = wvnresult;
1764 return wvnresult->result;
1770 return vn_reference_lookup_1 (&vr1, vnresult);
1774 /* Insert OP into the current hash table with a value number of
1775 RESULT, and return the resulting reference structure we created. */
1778 vn_reference_insert (tree op, tree result, tree vuse)
1783 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1784 if (TREE_CODE (result) == SSA_NAME)
1785 vr1->value_id = VN_INFO (result)->value_id;
1787 vr1->value_id = get_or_alloc_constant_value_id (result);
1788 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1789 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1790 vr1->type = TREE_TYPE (op);
1791 vr1->set = get_alias_set (op);
1792 vr1->hashcode = vn_reference_compute_hash (vr1);
1793 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1795 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1798 /* Because we lookup stores using vuses, and value number failures
1799 using the vdefs (see visit_reference_op_store for how and why),
1800 it's possible that on failure we may try to insert an already
1801 inserted store. This is not wrong, there is no ssa name for a
1802 store that we could use as a differentiator anyway. Thus, unlike
1803 the other lookup functions, you cannot gcc_assert (!*slot)
1806 /* But free the old slot in case of a collision. */
1808 free_reference (*slot);
1814 /* Insert a reference by it's pieces into the current hash table with
1815 a value number of RESULT. Return the resulting reference
1816 structure we created. */
1819 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
1820 VEC (vn_reference_op_s, heap) *operands,
1821 tree result, unsigned int value_id)
1827 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1828 vr1->value_id = value_id;
1829 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1830 vr1->operands = valueize_refs (operands);
1833 vr1->hashcode = vn_reference_compute_hash (vr1);
1834 if (result && TREE_CODE (result) == SSA_NAME)
1835 result = SSA_VAL (result);
1836 vr1->result = result;
1838 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1841 /* At this point we should have all the things inserted that we have
1842 seen before, and we should never try inserting something that
1844 gcc_assert (!*slot);
1846 free_reference (*slot);
1852 /* Compute and return the hash value for nary operation VBO1. */
1855 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1860 for (i = 0; i < vno1->length; ++i)
1861 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1862 vno1->op[i] = SSA_VAL (vno1->op[i]);
1864 if (vno1->length == 2
1865 && commutative_tree_code (vno1->opcode)
1866 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1868 tree temp = vno1->op[0];
1869 vno1->op[0] = vno1->op[1];
1873 hash = iterative_hash_hashval_t (vno1->opcode, 0);
1874 for (i = 0; i < vno1->length; ++i)
1875 hash = iterative_hash_expr (vno1->op[i], hash);
1880 /* Return the computed hashcode for nary operation P1. */
1883 vn_nary_op_hash (const void *p1)
1885 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1886 return vno1->hashcode;
1889 /* Compare nary operations P1 and P2 and return true if they are
1893 vn_nary_op_eq (const void *p1, const void *p2)
1895 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1896 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1899 if (vno1->hashcode != vno2->hashcode)
1902 if (vno1->opcode != vno2->opcode
1903 || !types_compatible_p (vno1->type, vno2->type))
1906 for (i = 0; i < vno1->length; ++i)
1907 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1913 /* Initialize VNO from the pieces provided. */
1916 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
1917 enum tree_code code, tree type, tree op0,
1918 tree op1, tree op2, tree op3)
1921 vno->length = length;
1925 /* The fallthrus here are deliberate. */
1926 case 4: vno->op[3] = op3;
1927 case 3: vno->op[2] = op2;
1928 case 2: vno->op[1] = op1;
1929 case 1: vno->op[0] = op0;
1935 /* Initialize VNO from OP. */
1938 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
1942 vno->opcode = TREE_CODE (op);
1943 vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
1944 vno->type = TREE_TYPE (op);
1945 for (i = 0; i < vno->length; ++i)
1946 vno->op[i] = TREE_OPERAND (op, i);
1949 /* Initialize VNO from STMT. */
1952 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple stmt)
1956 vno->opcode = gimple_assign_rhs_code (stmt);
1957 vno->length = gimple_num_ops (stmt) - 1;
1958 vno->type = gimple_expr_type (stmt);
1959 for (i = 0; i < vno->length; ++i)
1960 vno->op[i] = gimple_op (stmt, i + 1);
1961 if (vno->opcode == REALPART_EXPR
1962 || vno->opcode == IMAGPART_EXPR
1963 || vno->opcode == VIEW_CONVERT_EXPR)
1964 vno->op[0] = TREE_OPERAND (vno->op[0], 0);
1967 /* Compute the hashcode for VNO and look for it in the hash table;
1968 return the resulting value number if it exists in the hash table.
1969 Return NULL_TREE if it does not exist in the hash table or if the
1970 result field of the operation is NULL. VNRESULT will contain the
1971 vn_nary_op_t from the hashtable if it exists. */
1974 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
1981 vno->hashcode = vn_nary_op_compute_hash (vno);
1982 slot = htab_find_slot_with_hash (current_info->nary, vno, vno->hashcode,
1984 if (!slot && current_info == optimistic_info)
1985 slot = htab_find_slot_with_hash (valid_info->nary, vno, vno->hashcode,
1990 *vnresult = (vn_nary_op_t)*slot;
1991 return ((vn_nary_op_t)*slot)->result;
1994 /* Lookup a n-ary operation by its pieces and return the resulting value
1995 number if it exists in the hash table. Return NULL_TREE if it does
1996 not exist in the hash table or if the result field of the operation
1997 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2001 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2002 tree type, tree op0, tree op1, tree op2,
2003 tree op3, vn_nary_op_t *vnresult)
2005 struct vn_nary_op_s vno1;
2006 init_vn_nary_op_from_pieces (&vno1, length, code, type, op0, op1, op2, op3);
2007 return vn_nary_op_lookup_1 (&vno1, vnresult);
2010 /* Lookup OP in the current hash table, and return the resulting value
2011 number if it exists in the hash table. Return NULL_TREE if it does
2012 not exist in the hash table or if the result field of the operation
2013 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2017 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2019 struct vn_nary_op_s vno1;
2020 init_vn_nary_op_from_op (&vno1, op);
2021 return vn_nary_op_lookup_1 (&vno1, vnresult);
2024 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2025 value number if it exists in the hash table. Return NULL_TREE if
2026 it does not exist in the hash table. VNRESULT will contain the
2027 vn_nary_op_t from the hashtable if it exists. */
2030 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
2032 struct vn_nary_op_s vno1;
2033 init_vn_nary_op_from_stmt (&vno1, stmt);
2034 return vn_nary_op_lookup_1 (&vno1, vnresult);
2037 /* Return the size of a vn_nary_op_t with LENGTH operands. */
2040 sizeof_vn_nary_op (unsigned int length)
2042 return sizeof (struct vn_nary_op_s) - sizeof (tree) * (4 - length);
2045 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2048 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2050 return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
2053 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2057 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
2059 vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
2060 ¤t_info->nary_obstack);
2062 vno1->value_id = value_id;
2063 vno1->length = length;
2064 vno1->result = result;
2069 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2070 VNO->HASHCODE first. */
2073 vn_nary_op_insert_into (vn_nary_op_t vno, htab_t table, bool compute_hash)
2078 vno->hashcode = vn_nary_op_compute_hash (vno);
2080 slot = htab_find_slot_with_hash (table, vno, vno->hashcode, INSERT);
2081 gcc_assert (!*slot);
2087 /* Insert a n-ary operation into the current hash table using it's
2088 pieces. Return the vn_nary_op_t structure we created and put in
2092 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
2093 tree type, tree op0,
2094 tree op1, tree op2, tree op3,
2096 unsigned int value_id)
2100 vno1 = alloc_vn_nary_op (length, result, value_id);
2101 init_vn_nary_op_from_pieces (vno1, length, code, type, op0, op1, op2, op3);
2102 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2105 /* Insert OP into the current hash table with a value number of
2106 RESULT. Return the vn_nary_op_t structure we created and put in
2110 vn_nary_op_insert (tree op, tree result)
2112 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
2115 vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2116 init_vn_nary_op_from_op (vno1, op);
2117 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2120 /* Insert the rhs of STMT into the current hash table with a value number of
2124 vn_nary_op_insert_stmt (gimple stmt, tree result)
2126 unsigned length = gimple_num_ops (stmt) - 1;
2129 vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2130 init_vn_nary_op_from_stmt (vno1, stmt);
2131 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2134 /* Compute a hashcode for PHI operation VP1 and return it. */
2136 static inline hashval_t
2137 vn_phi_compute_hash (vn_phi_t vp1)
2144 result = vp1->block->index;
2146 /* If all PHI arguments are constants we need to distinguish
2147 the PHI node via its type. */
2148 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
2149 result += (INTEGRAL_TYPE_P (type)
2150 + (INTEGRAL_TYPE_P (type)
2151 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
2153 FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2155 if (phi1op == VN_TOP)
2157 result = iterative_hash_expr (phi1op, result);
2163 /* Return the computed hashcode for phi operation P1. */
2166 vn_phi_hash (const void *p1)
2168 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2169 return vp1->hashcode;
2172 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2175 vn_phi_eq (const void *p1, const void *p2)
2177 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2178 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
2180 if (vp1->hashcode != vp2->hashcode)
2183 if (vp1->block == vp2->block)
2188 /* If the PHI nodes do not have compatible types
2189 they are not the same. */
2190 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
2191 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
2194 /* Any phi in the same block will have it's arguments in the
2195 same edge order, because of how we store phi nodes. */
2196 FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2198 tree phi2op = VEC_index (tree, vp2->phiargs, i);
2199 if (phi1op == VN_TOP || phi2op == VN_TOP)
2201 if (!expressions_equal_p (phi1op, phi2op))
2209 static VEC(tree, heap) *shared_lookup_phiargs;
2211 /* Lookup PHI in the current hash table, and return the resulting
2212 value number if it exists in the hash table. Return NULL_TREE if
2213 it does not exist in the hash table. */
2216 vn_phi_lookup (gimple phi)
2219 struct vn_phi_s vp1;
2222 VEC_truncate (tree, shared_lookup_phiargs, 0);
2224 /* Canonicalize the SSA_NAME's to their value number. */
2225 for (i = 0; i < gimple_phi_num_args (phi); i++)
2227 tree def = PHI_ARG_DEF (phi, i);
2228 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2229 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
2231 vp1.phiargs = shared_lookup_phiargs;
2232 vp1.block = gimple_bb (phi);
2233 vp1.hashcode = vn_phi_compute_hash (&vp1);
2234 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
2236 if (!slot && current_info == optimistic_info)
2237 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
2241 return ((vn_phi_t)*slot)->result;
2244 /* Insert PHI into the current hash table with a value number of
2248 vn_phi_insert (gimple phi, tree result)
2251 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
2253 VEC (tree, heap) *args = NULL;
2255 /* Canonicalize the SSA_NAME's to their value number. */
2256 for (i = 0; i < gimple_phi_num_args (phi); i++)
2258 tree def = PHI_ARG_DEF (phi, i);
2259 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2260 VEC_safe_push (tree, heap, args, def);
2262 vp1->value_id = VN_INFO (result)->value_id;
2263 vp1->phiargs = args;
2264 vp1->block = gimple_bb (phi);
2265 vp1->result = result;
2266 vp1->hashcode = vn_phi_compute_hash (vp1);
2268 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
2271 /* Because we iterate over phi operations more than once, it's
2272 possible the slot might already exist here, hence no assert.*/
2278 /* Print set of components in strongly connected component SCC to OUT. */
2281 print_scc (FILE *out, VEC (tree, heap) *scc)
2286 fprintf (out, "SCC consists of: ");
2287 FOR_EACH_VEC_ELT (tree, scc, i, var)
2289 print_generic_expr (out, var, 0);
2292 fprintf (out, "\n");
2295 /* Set the value number of FROM to TO, return true if it has changed
2299 set_ssa_val_to (tree from, tree to)
2301 tree currval = SSA_VAL (from);
2305 if (currval == from)
2307 if (dump_file && (dump_flags & TDF_DETAILS))
2309 fprintf (dump_file, "Not changing value number of ");
2310 print_generic_expr (dump_file, from, 0);
2311 fprintf (dump_file, " from VARYING to ");
2312 print_generic_expr (dump_file, to, 0);
2313 fprintf (dump_file, "\n");
2317 else if (TREE_CODE (to) == SSA_NAME
2318 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
2322 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2323 and invariants. So assert that here. */
2324 gcc_assert (to != NULL_TREE
2326 || TREE_CODE (to) == SSA_NAME
2327 || is_gimple_min_invariant (to)));
2329 if (dump_file && (dump_flags & TDF_DETAILS))
2331 fprintf (dump_file, "Setting value number of ");
2332 print_generic_expr (dump_file, from, 0);
2333 fprintf (dump_file, " to ");
2334 print_generic_expr (dump_file, to, 0);
2337 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
2339 VN_INFO (from)->valnum = to;
2340 if (dump_file && (dump_flags & TDF_DETAILS))
2341 fprintf (dump_file, " (changed)\n");
2344 if (dump_file && (dump_flags & TDF_DETAILS))
2345 fprintf (dump_file, "\n");
2349 /* Set all definitions in STMT to value number to themselves.
2350 Return true if a value number changed. */
2353 defs_to_varying (gimple stmt)
2355 bool changed = false;
2359 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2361 tree def = DEF_FROM_PTR (defp);
2363 VN_INFO (def)->use_processed = true;
2364 changed |= set_ssa_val_to (def, def);
2369 static bool expr_has_constants (tree expr);
2370 static tree valueize_expr (tree expr);
2372 /* Visit a copy between LHS and RHS, return true if the value number
2376 visit_copy (tree lhs, tree rhs)
2378 /* Follow chains of copies to their destination. */
2379 while (TREE_CODE (rhs) == SSA_NAME
2380 && SSA_VAL (rhs) != rhs)
2381 rhs = SSA_VAL (rhs);
2383 /* The copy may have a more interesting constant filled expression
2384 (we don't, since we know our RHS is just an SSA name). */
2385 if (TREE_CODE (rhs) == SSA_NAME)
2387 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
2388 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
2391 return set_ssa_val_to (lhs, rhs);
2394 /* Visit a nary operator RHS, value number it, and return true if the
2395 value number of LHS has changed as a result. */
2398 visit_nary_op (tree lhs, gimple stmt)
2400 bool changed = false;
2401 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2404 changed = set_ssa_val_to (lhs, result);
2407 changed = set_ssa_val_to (lhs, lhs);
2408 vn_nary_op_insert_stmt (stmt, lhs);
2414 /* Visit a call STMT storing into LHS. Return true if the value number
2415 of the LHS has changed as a result. */
2418 visit_reference_op_call (tree lhs, gimple stmt)
2420 bool changed = false;
2421 struct vn_reference_s vr1;
2423 tree vuse = gimple_vuse (stmt);
2425 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2426 vr1.operands = valueize_shared_reference_ops_from_call (stmt);
2427 vr1.type = gimple_expr_type (stmt);
2429 vr1.hashcode = vn_reference_compute_hash (&vr1);
2430 result = vn_reference_lookup_1 (&vr1, NULL);
2433 changed = set_ssa_val_to (lhs, result);
2434 if (TREE_CODE (result) == SSA_NAME
2435 && VN_INFO (result)->has_constants)
2436 VN_INFO (lhs)->has_constants = true;
2442 changed = set_ssa_val_to (lhs, lhs);
2443 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
2444 vr2->vuse = vr1.vuse;
2445 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
2446 vr2->type = vr1.type;
2448 vr2->hashcode = vr1.hashcode;
2450 slot = htab_find_slot_with_hash (current_info->references,
2451 vr2, vr2->hashcode, INSERT);
2453 free_reference (*slot);
2460 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2461 and return true if the value number of the LHS has changed as a result. */
2464 visit_reference_op_load (tree lhs, tree op, gimple stmt)
2466 bool changed = false;
2470 last_vuse = gimple_vuse (stmt);
2471 last_vuse_ptr = &last_vuse;
2472 result = vn_reference_lookup (op, gimple_vuse (stmt),
2473 default_vn_walk_kind, NULL);
2474 last_vuse_ptr = NULL;
2476 /* If we have a VCE, try looking up its operand as it might be stored in
2477 a different type. */
2478 if (!result && TREE_CODE (op) == VIEW_CONVERT_EXPR)
2479 result = vn_reference_lookup (TREE_OPERAND (op, 0), gimple_vuse (stmt),
2480 default_vn_walk_kind, NULL);
2482 /* We handle type-punning through unions by value-numbering based
2483 on offset and size of the access. Be prepared to handle a
2484 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2486 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
2488 /* We will be setting the value number of lhs to the value number
2489 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2490 So first simplify and lookup this expression to see if it
2491 is already available. */
2492 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
2493 if ((CONVERT_EXPR_P (val)
2494 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
2495 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
2497 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
2498 if ((CONVERT_EXPR_P (tem)
2499 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
2500 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
2501 TREE_TYPE (val), tem)))
2505 if (!is_gimple_min_invariant (val)
2506 && TREE_CODE (val) != SSA_NAME)
2507 result = vn_nary_op_lookup (val, NULL);
2508 /* If the expression is not yet available, value-number lhs to
2509 a new SSA_NAME we create. */
2512 result = make_ssa_name (SSA_NAME_VAR (lhs), gimple_build_nop ());
2513 /* Initialize value-number information properly. */
2514 VN_INFO_GET (result)->valnum = result;
2515 VN_INFO (result)->value_id = get_next_value_id ();
2516 VN_INFO (result)->expr = val;
2517 VN_INFO (result)->has_constants = expr_has_constants (val);
2518 VN_INFO (result)->needs_insertion = true;
2519 /* As all "inserted" statements are singleton SCCs, insert
2520 to the valid table. This is strictly needed to
2521 avoid re-generating new value SSA_NAMEs for the same
2522 expression during SCC iteration over and over (the
2523 optimistic table gets cleared after each iteration).
2524 We do not need to insert into the optimistic table, as
2525 lookups there will fall back to the valid table. */
2526 if (current_info == optimistic_info)
2528 current_info = valid_info;
2529 vn_nary_op_insert (val, result);
2530 current_info = optimistic_info;
2533 vn_nary_op_insert (val, result);
2534 if (dump_file && (dump_flags & TDF_DETAILS))
2536 fprintf (dump_file, "Inserting name ");
2537 print_generic_expr (dump_file, result, 0);
2538 fprintf (dump_file, " for expression ");
2539 print_generic_expr (dump_file, val, 0);
2540 fprintf (dump_file, "\n");
2547 changed = set_ssa_val_to (lhs, result);
2548 if (TREE_CODE (result) == SSA_NAME
2549 && VN_INFO (result)->has_constants)
2551 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
2552 VN_INFO (lhs)->has_constants = true;
2557 changed = set_ssa_val_to (lhs, lhs);
2558 vn_reference_insert (op, lhs, last_vuse);
2565 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2566 and return true if the value number of the LHS has changed as a result. */
2569 visit_reference_op_store (tree lhs, tree op, gimple stmt)
2571 bool changed = false;
2573 bool resultsame = false;
2575 /* First we want to lookup using the *vuses* from the store and see
2576 if there the last store to this location with the same address
2579 The vuses represent the memory state before the store. If the
2580 memory state, address, and value of the store is the same as the
2581 last store to this location, then this store will produce the
2582 same memory state as that store.
2584 In this case the vdef versions for this store are value numbered to those
2585 vuse versions, since they represent the same memory state after
2588 Otherwise, the vdefs for the store are used when inserting into
2589 the table, since the store generates a new memory state. */
2591 result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL);
2595 if (TREE_CODE (result) == SSA_NAME)
2596 result = SSA_VAL (result);
2597 if (TREE_CODE (op) == SSA_NAME)
2599 resultsame = expressions_equal_p (result, op);
2602 if (!result || !resultsame)
2606 if (dump_file && (dump_flags & TDF_DETAILS))
2608 fprintf (dump_file, "No store match\n");
2609 fprintf (dump_file, "Value numbering store ");
2610 print_generic_expr (dump_file, lhs, 0);
2611 fprintf (dump_file, " to ");
2612 print_generic_expr (dump_file, op, 0);
2613 fprintf (dump_file, "\n");
2615 /* Have to set value numbers before insert, since insert is
2616 going to valueize the references in-place. */
2617 if ((vdef = gimple_vdef (stmt)))
2619 VN_INFO (vdef)->use_processed = true;
2620 changed |= set_ssa_val_to (vdef, vdef);
2623 /* Do not insert structure copies into the tables. */
2624 if (is_gimple_min_invariant (op)
2625 || is_gimple_reg (op))
2626 vn_reference_insert (lhs, op, vdef);
2630 /* We had a match, so value number the vdef to have the value
2631 number of the vuse it came from. */
2634 if (dump_file && (dump_flags & TDF_DETAILS))
2635 fprintf (dump_file, "Store matched earlier value,"
2636 "value numbering store vdefs to matching vuses.\n");
2638 def = gimple_vdef (stmt);
2639 use = gimple_vuse (stmt);
2641 VN_INFO (def)->use_processed = true;
2642 changed |= set_ssa_val_to (def, SSA_VAL (use));
2648 /* Visit and value number PHI, return true if the value number
2652 visit_phi (gimple phi)
2654 bool changed = false;
2656 tree sameval = VN_TOP;
2657 bool allsame = true;
2660 /* TODO: We could check for this in init_sccvn, and replace this
2661 with a gcc_assert. */
2662 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
2663 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2665 /* See if all non-TOP arguments have the same value. TOP is
2666 equivalent to everything, so we can ignore it. */
2667 for (i = 0; i < gimple_phi_num_args (phi); i++)
2669 tree def = PHI_ARG_DEF (phi, i);
2671 if (TREE_CODE (def) == SSA_NAME)
2672 def = SSA_VAL (def);
2675 if (sameval == VN_TOP)
2681 if (!expressions_equal_p (def, sameval))
2689 /* If all value numbered to the same value, the phi node has that
2693 if (is_gimple_min_invariant (sameval))
2695 VN_INFO (PHI_RESULT (phi))->has_constants = true;
2696 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2700 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2701 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2704 if (TREE_CODE (sameval) == SSA_NAME)
2705 return visit_copy (PHI_RESULT (phi), sameval);
2707 return set_ssa_val_to (PHI_RESULT (phi), sameval);
2710 /* Otherwise, see if it is equivalent to a phi node in this block. */
2711 result = vn_phi_lookup (phi);
2714 if (TREE_CODE (result) == SSA_NAME)
2715 changed = visit_copy (PHI_RESULT (phi), result);
2717 changed = set_ssa_val_to (PHI_RESULT (phi), result);
2721 vn_phi_insert (phi, PHI_RESULT (phi));
2722 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2723 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
2724 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2730 /* Return true if EXPR contains constants. */
2733 expr_has_constants (tree expr)
2735 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2738 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
2741 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
2742 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
2743 /* Constants inside reference ops are rarely interesting, but
2744 it can take a lot of looking to find them. */
2746 case tcc_declaration:
2749 return is_gimple_min_invariant (expr);
2754 /* Return true if STMT contains constants. */
2757 stmt_has_constants (gimple stmt)
2759 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2762 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2764 case GIMPLE_UNARY_RHS:
2765 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2767 case GIMPLE_BINARY_RHS:
2768 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2769 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
2770 case GIMPLE_TERNARY_RHS:
2771 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2772 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt))
2773 || is_gimple_min_invariant (gimple_assign_rhs3 (stmt)));
2774 case GIMPLE_SINGLE_RHS:
2775 /* Constants inside reference ops are rarely interesting, but
2776 it can take a lot of looking to find them. */
2777 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2784 /* Replace SSA_NAMES in expr with their value numbers, and return the
2786 This is performed in place. */
2789 valueize_expr (tree expr)
2791 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2794 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2795 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2796 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2799 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2800 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2801 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2802 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
2803 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
2804 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
2812 /* Simplify the binary expression RHS, and return the result if
2816 simplify_binary_expression (gimple stmt)
2818 tree result = NULL_TREE;
2819 tree op0 = gimple_assign_rhs1 (stmt);
2820 tree op1 = gimple_assign_rhs2 (stmt);
2822 /* This will not catch every single case we could combine, but will
2823 catch those with constants. The goal here is to simultaneously
2824 combine constants between expressions, but avoid infinite
2825 expansion of expressions during simplification. */
2826 if (TREE_CODE (op0) == SSA_NAME)
2828 if (VN_INFO (op0)->has_constants
2829 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
2830 op0 = valueize_expr (vn_get_expr_for (op0));
2831 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
2832 op0 = SSA_VAL (op0);
2835 if (TREE_CODE (op1) == SSA_NAME)
2837 if (VN_INFO (op1)->has_constants)
2838 op1 = valueize_expr (vn_get_expr_for (op1));
2839 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
2840 op1 = SSA_VAL (op1);
2843 /* Pointer plus constant can be represented as invariant address.
2844 Do so to allow further propatation, see also tree forwprop. */
2845 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
2846 && host_integerp (op1, 1)
2847 && TREE_CODE (op0) == ADDR_EXPR
2848 && is_gimple_min_invariant (op0))
2849 return build_invariant_address (TREE_TYPE (op0),
2850 TREE_OPERAND (op0, 0),
2851 TREE_INT_CST_LOW (op1));
2853 /* Avoid folding if nothing changed. */
2854 if (op0 == gimple_assign_rhs1 (stmt)
2855 && op1 == gimple_assign_rhs2 (stmt))
2858 fold_defer_overflow_warnings ();
2860 result = fold_binary (gimple_assign_rhs_code (stmt),
2861 gimple_expr_type (stmt), op0, op1);
2863 STRIP_USELESS_TYPE_CONVERSION (result);
2865 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2868 /* Make sure result is not a complex expression consisting
2869 of operators of operators (IE (a + b) + (a + c))
2870 Otherwise, we will end up with unbounded expressions if
2871 fold does anything at all. */
2872 if (result && valid_gimple_rhs_p (result))
2878 /* Simplify the unary expression RHS, and return the result if
2882 simplify_unary_expression (gimple stmt)
2884 tree result = NULL_TREE;
2885 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2887 /* We handle some tcc_reference codes here that are all
2888 GIMPLE_ASSIGN_SINGLE codes. */
2889 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2890 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2891 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2892 op0 = TREE_OPERAND (op0, 0);
2894 if (TREE_CODE (op0) != SSA_NAME)
2898 if (VN_INFO (op0)->has_constants)
2899 op0 = valueize_expr (vn_get_expr_for (op0));
2900 else if (gimple_assign_cast_p (stmt)
2901 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2902 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2903 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2905 /* We want to do tree-combining on conversion-like expressions.
2906 Make sure we feed only SSA_NAMEs or constants to fold though. */
2907 tree tem = valueize_expr (vn_get_expr_for (op0));
2908 if (UNARY_CLASS_P (tem)
2909 || BINARY_CLASS_P (tem)
2910 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2911 || TREE_CODE (tem) == SSA_NAME
2912 || is_gimple_min_invariant (tem))
2916 /* Avoid folding if nothing changed, but remember the expression. */
2917 if (op0 == orig_op0)
2920 result = fold_unary_ignore_overflow (gimple_assign_rhs_code (stmt),
2921 gimple_expr_type (stmt), op0);
2924 STRIP_USELESS_TYPE_CONVERSION (result);
2925 if (valid_gimple_rhs_p (result))
2932 /* Valueize NAME if it is an SSA name, otherwise just return it. */
2935 vn_valueize (tree name)
2937 if (TREE_CODE (name) == SSA_NAME)
2939 tree tem = SSA_VAL (name);
2940 return tem == VN_TOP ? name : tem;
2945 /* Try to simplify RHS using equivalences and constant folding. */
2948 try_to_simplify (gimple stmt)
2952 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2953 in this case, there is no point in doing extra work. */
2954 if (gimple_assign_copy_p (stmt)
2955 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2958 /* First try constant folding based on our current lattice. */
2959 tem = gimple_fold_stmt_to_constant (stmt, vn_valueize);
2963 /* If that didn't work try combining multiple statements. */
2964 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2967 /* Fallthrough for some codes that can operate on registers. */
2968 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2969 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2970 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2972 /* We could do a little more with unary ops, if they expand
2973 into binary ops, but it's debatable whether it is worth it. */
2975 return simplify_unary_expression (stmt);
2977 case tcc_comparison:
2979 return simplify_binary_expression (stmt);
2988 /* Visit and value number USE, return true if the value number
2992 visit_use (tree use)
2994 bool changed = false;
2995 gimple stmt = SSA_NAME_DEF_STMT (use);
2997 VN_INFO (use)->use_processed = true;
2999 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
3000 if (dump_file && (dump_flags & TDF_DETAILS)
3001 && !SSA_NAME_IS_DEFAULT_DEF (use))
3003 fprintf (dump_file, "Value numbering ");
3004 print_generic_expr (dump_file, use, 0);
3005 fprintf (dump_file, " stmt = ");
3006 print_gimple_stmt (dump_file, stmt, 0, 0);
3009 /* Handle uninitialized uses. */
3010 if (SSA_NAME_IS_DEFAULT_DEF (use))
3011 changed = set_ssa_val_to (use, use);
3014 if (gimple_code (stmt) == GIMPLE_PHI)
3015 changed = visit_phi (stmt);
3016 else if (!gimple_has_lhs (stmt)
3017 || gimple_has_volatile_ops (stmt)
3018 || stmt_could_throw_p (stmt))
3019 changed = defs_to_varying (stmt);
3020 else if (is_gimple_assign (stmt))
3022 tree lhs = gimple_assign_lhs (stmt);
3025 /* Shortcut for copies. Simplifying copies is pointless,
3026 since we copy the expression and value they represent. */
3027 if (gimple_assign_copy_p (stmt)
3028 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
3029 && TREE_CODE (lhs) == SSA_NAME)
3031 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
3034 simplified = try_to_simplify (stmt);
3037 if (dump_file && (dump_flags & TDF_DETAILS))
3039 fprintf (dump_file, "RHS ");
3040 print_gimple_expr (dump_file, stmt, 0, 0);
3041 fprintf (dump_file, " simplified to ");
3042 print_generic_expr (dump_file, simplified, 0);
3043 if (TREE_CODE (lhs) == SSA_NAME)
3044 fprintf (dump_file, " has constants %d\n",
3045 expr_has_constants (simplified));
3047 fprintf (dump_file, "\n");
3050 /* Setting value numbers to constants will occasionally
3051 screw up phi congruence because constants are not
3052 uniquely associated with a single ssa name that can be
3055 && is_gimple_min_invariant (simplified)
3056 && TREE_CODE (lhs) == SSA_NAME)
3058 VN_INFO (lhs)->expr = simplified;
3059 VN_INFO (lhs)->has_constants = true;
3060 changed = set_ssa_val_to (lhs, simplified);
3064 && TREE_CODE (simplified) == SSA_NAME
3065 && TREE_CODE (lhs) == SSA_NAME)
3067 changed = visit_copy (lhs, simplified);
3070 else if (simplified)
3072 if (TREE_CODE (lhs) == SSA_NAME)
3074 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
3075 /* We have to unshare the expression or else
3076 valuizing may change the IL stream. */
3077 VN_INFO (lhs)->expr = unshare_expr (simplified);
3080 else if (stmt_has_constants (stmt)
3081 && TREE_CODE (lhs) == SSA_NAME)
3082 VN_INFO (lhs)->has_constants = true;
3083 else if (TREE_CODE (lhs) == SSA_NAME)
3085 /* We reset expr and constantness here because we may
3086 have been value numbering optimistically, and
3087 iterating. They may become non-constant in this case,
3088 even if they were optimistically constant. */
3090 VN_INFO (lhs)->has_constants = false;
3091 VN_INFO (lhs)->expr = NULL_TREE;
3094 if ((TREE_CODE (lhs) == SSA_NAME
3095 /* We can substitute SSA_NAMEs that are live over
3096 abnormal edges with their constant value. */
3097 && !(gimple_assign_copy_p (stmt)
3098 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
3100 && is_gimple_min_invariant (simplified))
3101 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3102 /* Stores or copies from SSA_NAMEs that are live over
3103 abnormal edges are a problem. */
3104 || (gimple_assign_single_p (stmt)
3105 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
3106 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))))
3107 changed = defs_to_varying (stmt);
3108 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
3110 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
3112 else if (TREE_CODE (lhs) == SSA_NAME)
3114 if ((gimple_assign_copy_p (stmt)
3115 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
3117 && is_gimple_min_invariant (simplified)))
3119 VN_INFO (lhs)->has_constants = true;
3121 changed = set_ssa_val_to (lhs, simplified);
3123 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
3127 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3129 case GIMPLE_UNARY_RHS:
3130 case GIMPLE_BINARY_RHS:
3131 case GIMPLE_TERNARY_RHS:
3132 changed = visit_nary_op (lhs, stmt);
3134 case GIMPLE_SINGLE_RHS:
3135 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
3138 /* VOP-less references can go through unary case. */
3139 if ((gimple_assign_rhs_code (stmt) == REALPART_EXPR
3140 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
3141 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
3142 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (stmt), 0)) == SSA_NAME)
3144 changed = visit_nary_op (lhs, stmt);
3148 case tcc_declaration:
3149 changed = visit_reference_op_load
3150 (lhs, gimple_assign_rhs1 (stmt), stmt);
3152 case tcc_expression:
3153 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
3155 changed = visit_nary_op (lhs, stmt);
3160 changed = defs_to_varying (stmt);
3164 changed = defs_to_varying (stmt);
3170 changed = defs_to_varying (stmt);
3172 else if (is_gimple_call (stmt))
3174 tree lhs = gimple_call_lhs (stmt);
3176 /* ??? We could try to simplify calls. */
3178 if (stmt_has_constants (stmt)
3179 && TREE_CODE (lhs) == SSA_NAME)
3180 VN_INFO (lhs)->has_constants = true;
3181 else if (TREE_CODE (lhs) == SSA_NAME)
3183 /* We reset expr and constantness here because we may
3184 have been value numbering optimistically, and
3185 iterating. They may become non-constant in this case,
3186 even if they were optimistically constant. */
3187 VN_INFO (lhs)->has_constants = false;
3188 VN_INFO (lhs)->expr = NULL_TREE;
3191 if (TREE_CODE (lhs) == SSA_NAME
3192 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3193 changed = defs_to_varying (stmt);
3194 /* ??? We should handle stores from calls. */
3195 else if (TREE_CODE (lhs) == SSA_NAME)
3197 if (!gimple_call_internal_p (stmt)
3198 && gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
3199 changed = visit_reference_op_call (lhs, stmt);
3201 changed = defs_to_varying (stmt);
3204 changed = defs_to_varying (stmt);
3211 /* Compare two operands by reverse postorder index */
3214 compare_ops (const void *pa, const void *pb)
3216 const tree opa = *((const tree *)pa);
3217 const tree opb = *((const tree *)pb);
3218 gimple opstmta = SSA_NAME_DEF_STMT (opa);
3219 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3223 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3224 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3225 else if (gimple_nop_p (opstmta))
3227 else if (gimple_nop_p (opstmtb))
3230 bba = gimple_bb (opstmta);
3231 bbb = gimple_bb (opstmtb);
3234 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3242 if (gimple_code (opstmta) == GIMPLE_PHI
3243 && gimple_code (opstmtb) == GIMPLE_PHI)
3244 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3245 else if (gimple_code (opstmta) == GIMPLE_PHI)
3247 else if (gimple_code (opstmtb) == GIMPLE_PHI)
3249 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3250 return gimple_uid (opstmta) - gimple_uid (opstmtb);
3252 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3254 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3257 /* Sort an array containing members of a strongly connected component
3258 SCC so that the members are ordered by RPO number.
3259 This means that when the sort is complete, iterating through the
3260 array will give you the members in RPO order. */
3263 sort_scc (VEC (tree, heap) *scc)
3265 VEC_qsort (tree, scc, compare_ops);
3268 /* Insert the no longer used nary ONARY to the hash INFO. */
3271 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3273 size_t size = sizeof_vn_nary_op (onary->length);
3274 vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
3275 &info->nary_obstack);
3276 memcpy (nary, onary, size);
3277 vn_nary_op_insert_into (nary, info->nary, false);
3280 /* Insert the no longer used phi OPHI to the hash INFO. */
3283 copy_phi (vn_phi_t ophi, vn_tables_t info)
3285 vn_phi_t phi = (vn_phi_t) pool_alloc (info->phis_pool);
3287 memcpy (phi, ophi, sizeof (*phi));
3288 ophi->phiargs = NULL;
3289 slot = htab_find_slot_with_hash (info->phis, phi, phi->hashcode, INSERT);
3290 gcc_assert (!*slot);
3294 /* Insert the no longer used reference OREF to the hash INFO. */
3297 copy_reference (vn_reference_t oref, vn_tables_t info)
3301 ref = (vn_reference_t) pool_alloc (info->references_pool);
3302 memcpy (ref, oref, sizeof (*ref));
3303 oref->operands = NULL;
3304 slot = htab_find_slot_with_hash (info->references, ref, ref->hashcode,
3307 free_reference (*slot);
3311 /* Process a strongly connected component in the SSA graph. */
3314 process_scc (VEC (tree, heap) *scc)
3318 unsigned int iterations = 0;
3319 bool changed = true;
3325 /* If the SCC has a single member, just visit it. */
3326 if (VEC_length (tree, scc) == 1)
3328 tree use = VEC_index (tree, scc, 0);
3329 if (VN_INFO (use)->use_processed)
3331 /* We need to make sure it doesn't form a cycle itself, which can
3332 happen for self-referential PHI nodes. In that case we would
3333 end up inserting an expression with VN_TOP operands into the
3334 valid table which makes us derive bogus equivalences later.
3335 The cheapest way to check this is to assume it for all PHI nodes. */
3336 if (gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_PHI)
3337 /* Fallthru to iteration. */ ;
3345 /* Iterate over the SCC with the optimistic table until it stops
3347 current_info = optimistic_info;
3352 if (dump_file && (dump_flags & TDF_DETAILS))
3353 fprintf (dump_file, "Starting iteration %d\n", iterations);
3354 /* As we are value-numbering optimistically we have to
3355 clear the expression tables and the simplified expressions
3356 in each iteration until we converge. */
3357 htab_empty (optimistic_info->nary);
3358 htab_empty (optimistic_info->phis);
3359 htab_empty (optimistic_info->references);
3360 obstack_free (&optimistic_info->nary_obstack, NULL);
3361 gcc_obstack_init (&optimistic_info->nary_obstack);
3362 empty_alloc_pool (optimistic_info->phis_pool);
3363 empty_alloc_pool (optimistic_info->references_pool);
3364 FOR_EACH_VEC_ELT (tree, scc, i, var)
3365 VN_INFO (var)->expr = NULL_TREE;
3366 FOR_EACH_VEC_ELT (tree, scc, i, var)
3367 changed |= visit_use (var);
3370 statistics_histogram_event (cfun, "SCC iterations", iterations);
3372 /* Finally, copy the contents of the no longer used optimistic
3373 table to the valid table. */
3374 FOR_EACH_HTAB_ELEMENT (optimistic_info->nary, nary, vn_nary_op_t, hi)
3375 copy_nary (nary, valid_info);
3376 FOR_EACH_HTAB_ELEMENT (optimistic_info->phis, phi, vn_phi_t, hi)
3377 copy_phi (phi, valid_info);
3378 FOR_EACH_HTAB_ELEMENT (optimistic_info->references, ref, vn_reference_t, hi)
3379 copy_reference (ref, valid_info);
3381 current_info = valid_info;
3384 DEF_VEC_O(ssa_op_iter);
3385 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
3387 /* Pop the components of the found SCC for NAME off the SCC stack
3388 and process them. Returns true if all went well, false if
3389 we run into resource limits. */
3392 extract_and_process_scc_for_name (tree name)
3394 VEC (tree, heap) *scc = NULL;
3397 /* Found an SCC, pop the components off the SCC stack and
3401 x = VEC_pop (tree, sccstack);
3403 VN_INFO (x)->on_sccstack = false;
3404 VEC_safe_push (tree, heap, scc, x);
3405 } while (x != name);
3407 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3408 if (VEC_length (tree, scc)
3409 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
3412 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
3413 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
3414 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
3418 if (VEC_length (tree, scc) > 1)
3421 if (dump_file && (dump_flags & TDF_DETAILS))
3422 print_scc (dump_file, scc);
3426 VEC_free (tree, heap, scc);
3431 /* Depth first search on NAME to discover and process SCC's in the SSA
3433 Execution of this algorithm relies on the fact that the SCC's are
3434 popped off the stack in topological order.
3435 Returns true if successful, false if we stopped processing SCC's due
3436 to resource constraints. */
3441 VEC(ssa_op_iter, heap) *itervec = NULL;
3442 VEC(tree, heap) *namevec = NULL;
3443 use_operand_p usep = NULL;
3450 VN_INFO (name)->dfsnum = next_dfs_num++;
3451 VN_INFO (name)->visited = true;
3452 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
3454 VEC_safe_push (tree, heap, sccstack, name);
3455 VN_INFO (name)->on_sccstack = true;
3456 defstmt = SSA_NAME_DEF_STMT (name);
3458 /* Recursively DFS on our operands, looking for SCC's. */
3459 if (!gimple_nop_p (defstmt))
3461 /* Push a new iterator. */
3462 if (gimple_code (defstmt) == GIMPLE_PHI)
3463 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
3465 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
3468 clear_and_done_ssa_iter (&iter);
3472 /* If we are done processing uses of a name, go up the stack
3473 of iterators and process SCCs as we found them. */
3474 if (op_iter_done (&iter))
3476 /* See if we found an SCC. */
3477 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
3478 if (!extract_and_process_scc_for_name (name))
3480 VEC_free (tree, heap, namevec);
3481 VEC_free (ssa_op_iter, heap, itervec);
3485 /* Check if we are done. */
3486 if (VEC_empty (tree, namevec))
3488 VEC_free (tree, heap, namevec);
3489 VEC_free (ssa_op_iter, heap, itervec);
3493 /* Restore the last use walker and continue walking there. */
3495 name = VEC_pop (tree, namevec);
3496 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
3497 sizeof (ssa_op_iter));
3498 VEC_pop (ssa_op_iter, itervec);
3499 goto continue_walking;
3502 use = USE_FROM_PTR (usep);
3504 /* Since we handle phi nodes, we will sometimes get
3505 invariants in the use expression. */
3506 if (TREE_CODE (use) == SSA_NAME)
3508 if (! (VN_INFO (use)->visited))
3510 /* Recurse by pushing the current use walking state on
3511 the stack and starting over. */
3512 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
3513 VEC_safe_push(tree, heap, namevec, name);
3518 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
3519 VN_INFO (use)->low);
3521 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
3522 && VN_INFO (use)->on_sccstack)
3524 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
3525 VN_INFO (name)->low);
3529 usep = op_iter_next_use (&iter);
3533 /* Allocate a value number table. */
3536 allocate_vn_table (vn_tables_t table)
3538 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
3539 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
3540 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
3543 gcc_obstack_init (&table->nary_obstack);
3544 table->phis_pool = create_alloc_pool ("VN phis",
3545 sizeof (struct vn_phi_s),
3547 table->references_pool = create_alloc_pool ("VN references",
3548 sizeof (struct vn_reference_s),
3552 /* Free a value number table. */
3555 free_vn_table (vn_tables_t table)
3557 htab_delete (table->phis);
3558 htab_delete (table->nary);
3559 htab_delete (table->references);
3560 obstack_free (&table->nary_obstack, NULL);
3561 free_alloc_pool (table->phis_pool);
3562 free_alloc_pool (table->references_pool);
3570 int *rpo_numbers_temp;
3572 calculate_dominance_info (CDI_DOMINATORS);
3574 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
3577 constant_value_ids = BITMAP_ALLOC (NULL);
3582 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
3583 /* VEC_alloc doesn't actually grow it to the right size, it just
3584 preallocates the space to do so. */
3585 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
3586 gcc_obstack_init (&vn_ssa_aux_obstack);
3588 shared_lookup_phiargs = NULL;
3589 shared_lookup_references = NULL;
3590 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3591 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3592 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
3594 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3595 the i'th block in RPO order is bb. We want to map bb's to RPO
3596 numbers, so we need to rearrange this array. */
3597 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
3598 rpo_numbers[rpo_numbers_temp[j]] = j;
3600 XDELETE (rpo_numbers_temp);
3602 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
3604 /* Create the VN_INFO structures, and initialize value numbers to
3606 for (i = 0; i < num_ssa_names; i++)
3608 tree name = ssa_name (i);
3611 VN_INFO_GET (name)->valnum = VN_TOP;
3612 VN_INFO (name)->expr = NULL_TREE;
3613 VN_INFO (name)->value_id = 0;
3617 renumber_gimple_stmt_uids ();
3619 /* Create the valid and optimistic value numbering tables. */
3620 valid_info = XCNEW (struct vn_tables_s);
3621 allocate_vn_table (valid_info);
3622 optimistic_info = XCNEW (struct vn_tables_s);
3623 allocate_vn_table (optimistic_info);
3631 htab_delete (constant_to_value_id);
3632 BITMAP_FREE (constant_value_ids);
3633 VEC_free (tree, heap, shared_lookup_phiargs);
3634 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
3635 XDELETEVEC (rpo_numbers);
3637 for (i = 0; i < num_ssa_names; i++)
3639 tree name = ssa_name (i);
3641 && VN_INFO (name)->needs_insertion)
3642 release_ssa_name (name);
3644 obstack_free (&vn_ssa_aux_obstack, NULL);
3645 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
3647 VEC_free (tree, heap, sccstack);
3648 free_vn_table (valid_info);
3649 XDELETE (valid_info);
3650 free_vn_table (optimistic_info);
3651 XDELETE (optimistic_info);
3654 /* Set *ID if we computed something useful in RESULT. */
3657 set_value_id_for_result (tree result, unsigned int *id)
3661 if (TREE_CODE (result) == SSA_NAME)
3662 *id = VN_INFO (result)->value_id;
3663 else if (is_gimple_min_invariant (result))
3664 *id = get_or_alloc_constant_value_id (result);
3668 /* Set the value ids in the valid hash tables. */
3671 set_hashtable_value_ids (void)
3678 /* Now set the value ids of the things we had put in the hash
3681 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
3682 vno, vn_nary_op_t, hi)
3683 set_value_id_for_result (vno->result, &vno->value_id);
3685 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
3687 set_value_id_for_result (vp->result, &vp->value_id);
3689 FOR_EACH_HTAB_ELEMENT (valid_info->references,
3690 vr, vn_reference_t, hi)
3691 set_value_id_for_result (vr->result, &vr->value_id);
3694 /* Do SCCVN. Returns true if it finished, false if we bailed out
3695 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
3696 how we use the alias oracle walking during the VN process. */
3699 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
3703 bool changed = true;
3705 default_vn_walk_kind = default_vn_walk_kind_;
3708 current_info = valid_info;
3710 for (param = DECL_ARGUMENTS (current_function_decl);
3712 param = DECL_CHAIN (param))
3714 if (gimple_default_def (cfun, param) != NULL)
3716 tree def = gimple_default_def (cfun, param);
3717 VN_INFO (def)->valnum = def;
3721 for (i = 1; i < num_ssa_names; ++i)
3723 tree name = ssa_name (i);
3725 && VN_INFO (name)->visited == false
3726 && !has_zero_uses (name))
3734 /* Initialize the value ids. */
3736 for (i = 1; i < num_ssa_names; ++i)
3738 tree name = ssa_name (i);
3742 info = VN_INFO (name);
3743 if (info->valnum == name
3744 || info->valnum == VN_TOP)
3745 info->value_id = get_next_value_id ();
3746 else if (is_gimple_min_invariant (info->valnum))
3747 info->value_id = get_or_alloc_constant_value_id (info->valnum);
3750 /* Propagate until they stop changing. */
3754 for (i = 1; i < num_ssa_names; ++i)
3756 tree name = ssa_name (i);
3760 info = VN_INFO (name);
3761 if (TREE_CODE (info->valnum) == SSA_NAME
3762 && info->valnum != name
3763 && info->value_id != VN_INFO (info->valnum)->value_id)
3766 info->value_id = VN_INFO (info->valnum)->value_id;
3771 set_hashtable_value_ids ();
3773 if (dump_file && (dump_flags & TDF_DETAILS))
3775 fprintf (dump_file, "Value numbers:\n");
3776 for (i = 0; i < num_ssa_names; i++)
3778 tree name = ssa_name (i);
3780 && VN_INFO (name)->visited
3781 && SSA_VAL (name) != name)
3783 print_generic_expr (dump_file, name, 0);
3784 fprintf (dump_file, " = ");
3785 print_generic_expr (dump_file, SSA_VAL (name), 0);
3786 fprintf (dump_file, "\n");
3794 /* Return the maximum value id we have ever seen. */
3797 get_max_value_id (void)
3799 return next_value_id;
3802 /* Return the next unique value id. */
3805 get_next_value_id (void)
3807 return next_value_id++;
3811 /* Compare two expressions E1 and E2 and return true if they are equal. */
3814 expressions_equal_p (tree e1, tree e2)
3816 /* The obvious case. */
3820 /* If only one of them is null, they cannot be equal. */
3824 /* Now perform the actual comparison. */
3825 if (TREE_CODE (e1) == TREE_CODE (e2)
3826 && operand_equal_p (e1, e2, OEP_PURE_SAME))
3833 /* Return true if the nary operation NARY may trap. This is a copy
3834 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
3837 vn_nary_may_trap (vn_nary_op_t nary)
3840 tree rhs2 = NULL_TREE;
3841 bool honor_nans = false;
3842 bool honor_snans = false;
3843 bool fp_operation = false;
3844 bool honor_trapv = false;
3848 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
3849 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
3850 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
3853 fp_operation = FLOAT_TYPE_P (type);
3856 honor_nans = flag_trapping_math && !flag_finite_math_only;
3857 honor_snans = flag_signaling_nans != 0;
3859 else if (INTEGRAL_TYPE_P (type)
3860 && TYPE_OVERFLOW_TRAPS (type))
3863 if (nary->length >= 2)
3865 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
3867 honor_nans, honor_snans, rhs2,
3873 for (i = 0; i < nary->length; ++i)
3874 if (tree_could_trap_p (nary->op[i]))