1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
37 #include "tree-iterator.h"
38 #include "alloc-pool.h"
39 #include "tree-pass.h"
42 #include "langhooks.h"
45 #include "tree-ssa-propagate.h"
46 #include "tree-ssa-sccvn.h"
47 #include "gimple-fold.h"
49 /* This algorithm is based on the SCC algorithm presented by Keith
50 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
51 (http://citeseer.ist.psu.edu/41805.html). In
52 straight line code, it is equivalent to a regular hash based value
53 numbering that is performed in reverse postorder.
55 For code with cycles, there are two alternatives, both of which
56 require keeping the hashtables separate from the actual list of
57 value numbers for SSA names.
59 1. Iterate value numbering in an RPO walk of the blocks, removing
60 all the entries from the hashtable after each iteration (but
61 keeping the SSA name->value number mapping between iterations).
62 Iterate until it does not change.
64 2. Perform value numbering as part of an SCC walk on the SSA graph,
65 iterating only the cycles in the SSA graph until they do not change
66 (using a separate, optimistic hashtable for value numbering the SCC
69 The second is not just faster in practice (because most SSA graph
70 cycles do not involve all the variables in the graph), it also has
73 One of these nice properties is that when we pop an SCC off the
74 stack, we are guaranteed to have processed all the operands coming from
75 *outside of that SCC*, so we do not need to do anything special to
76 ensure they have value numbers.
78 Another nice property is that the SCC walk is done as part of a DFS
79 of the SSA graph, which makes it easy to perform combining and
80 simplifying operations at the same time.
82 The code below is deliberately written in a way that makes it easy
83 to separate the SCC walk from the other work it does.
85 In order to propagate constants through the code, we track which
86 expressions contain constants, and use those while folding. In
87 theory, we could also track expressions whose value numbers are
88 replaced, in case we end up folding based on expression
91 In order to value number memory, we assign value numbers to vuses.
92 This enables us to note that, for example, stores to the same
93 address of the same value from the same starting memory states are
97 1. We can iterate only the changing portions of the SCC's, but
98 I have not seen an SCC big enough for this to be a win.
99 2. If you differentiate between phi nodes for loops and phi nodes
100 for if-then-else, you can properly consider phi nodes in different
101 blocks for equivalence.
102 3. We could value number vuses in more cases, particularly, whole
106 /* The set of hashtables and alloc_pool's for their items. */
108 typedef struct vn_tables_s
113 struct obstack nary_obstack;
114 alloc_pool phis_pool;
115 alloc_pool references_pool;
118 static htab_t constant_to_value_id;
119 static bitmap constant_value_ids;
122 /* Valid hashtables storing information we have proven to be
125 static vn_tables_t valid_info;
127 /* Optimistic hashtables storing information we are making assumptions about
128 during iterations. */
130 static vn_tables_t optimistic_info;
132 /* Pointer to the set of hashtables that is currently being used.
133 Should always point to either the optimistic_info, or the
136 static vn_tables_t current_info;
139 /* Reverse post order index for each basic block. */
141 static int *rpo_numbers;
143 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
145 /* This represents the top of the VN lattice, which is the universal
150 /* Unique counter for our value ids. */
152 static unsigned int next_value_id;
154 /* Next DFS number and the stack for strongly connected component
157 static unsigned int next_dfs_num;
158 static VEC (tree, heap) *sccstack;
161 DEF_VEC_P(vn_ssa_aux_t);
162 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
164 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
165 are allocated on an obstack for locality reasons, and to free them
166 without looping over the VEC. */
168 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
169 static struct obstack vn_ssa_aux_obstack;
171 /* Return the value numbering information for a given SSA name. */
176 vn_ssa_aux_t res = VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
177 SSA_NAME_VERSION (name));
178 gcc_checking_assert (res);
182 /* Set the value numbering info for a given SSA name to a given
186 VN_INFO_SET (tree name, vn_ssa_aux_t value)
188 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
189 SSA_NAME_VERSION (name), value);
192 /* Initialize the value numbering info for a given SSA name.
193 This should be called just once for every SSA name. */
196 VN_INFO_GET (tree name)
198 vn_ssa_aux_t newinfo;
200 newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
201 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
202 if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
203 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
204 SSA_NAME_VERSION (name) + 1);
205 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
206 SSA_NAME_VERSION (name), newinfo);
211 /* Get the representative expression for the SSA_NAME NAME. Returns
212 the representative SSA_NAME if there is no expression associated with it. */
215 vn_get_expr_for (tree name)
217 vn_ssa_aux_t vn = VN_INFO (name);
219 tree expr = NULL_TREE;
222 if (vn->valnum == VN_TOP)
225 /* If the value-number is a constant it is the representative
227 if (TREE_CODE (vn->valnum) != SSA_NAME)
230 /* Get to the information of the value of this SSA_NAME. */
231 vn = VN_INFO (vn->valnum);
233 /* If the value-number is a constant it is the representative
235 if (TREE_CODE (vn->valnum) != SSA_NAME)
238 /* Else if we have an expression, return it. */
239 if (vn->expr != NULL_TREE)
242 /* Otherwise use the defining statement to build the expression. */
243 def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
245 /* If the value number is not an assignment use it directly. */
246 if (!is_gimple_assign (def_stmt))
249 /* FIXME tuples. This is incomplete and likely will miss some
251 code = gimple_assign_rhs_code (def_stmt);
252 switch (TREE_CODE_CLASS (code))
255 if ((code == REALPART_EXPR
256 || code == IMAGPART_EXPR
257 || code == VIEW_CONVERT_EXPR)
258 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt),
260 expr = fold_build1 (code,
261 gimple_expr_type (def_stmt),
262 TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0));
266 expr = fold_build1 (code,
267 gimple_expr_type (def_stmt),
268 gimple_assign_rhs1 (def_stmt));
272 expr = fold_build2 (code,
273 gimple_expr_type (def_stmt),
274 gimple_assign_rhs1 (def_stmt),
275 gimple_assign_rhs2 (def_stmt));
280 if (expr == NULL_TREE)
283 /* Cache the expression. */
290 /* Free a phi operation structure VP. */
295 vn_phi_t phi = (vn_phi_t) vp;
296 VEC_free (tree, heap, phi->phiargs);
299 /* Free a reference operation structure VP. */
302 free_reference (void *vp)
304 vn_reference_t vr = (vn_reference_t) vp;
305 VEC_free (vn_reference_op_s, heap, vr->operands);
308 /* Hash table equality function for vn_constant_t. */
311 vn_constant_eq (const void *p1, const void *p2)
313 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
314 const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
316 if (vc1->hashcode != vc2->hashcode)
319 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
322 /* Hash table hash function for vn_constant_t. */
325 vn_constant_hash (const void *p1)
327 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
328 return vc1->hashcode;
331 /* Lookup a value id for CONSTANT and return it. If it does not
335 get_constant_value_id (tree constant)
338 struct vn_constant_s vc;
340 vc.hashcode = vn_hash_constant_with_type (constant);
341 vc.constant = constant;
342 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
343 vc.hashcode, NO_INSERT);
345 return ((vn_constant_t)*slot)->value_id;
349 /* Lookup a value id for CONSTANT, and if it does not exist, create a
350 new one and return it. If it does exist, return it. */
353 get_or_alloc_constant_value_id (tree constant)
356 struct vn_constant_s vc;
359 vc.hashcode = vn_hash_constant_with_type (constant);
360 vc.constant = constant;
361 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
362 vc.hashcode, INSERT);
364 return ((vn_constant_t)*slot)->value_id;
366 vcp = XNEW (struct vn_constant_s);
367 vcp->hashcode = vc.hashcode;
368 vcp->constant = constant;
369 vcp->value_id = get_next_value_id ();
370 *slot = (void *) vcp;
371 bitmap_set_bit (constant_value_ids, vcp->value_id);
372 return vcp->value_id;
375 /* Return true if V is a value id for a constant. */
378 value_id_constant_p (unsigned int v)
380 return bitmap_bit_p (constant_value_ids, v);
383 /* Compare two reference operands P1 and P2 for equality. Return true if
384 they are equal, and false otherwise. */
387 vn_reference_op_eq (const void *p1, const void *p2)
389 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
390 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
392 return (vro1->opcode == vro2->opcode
393 /* We do not care for differences in type qualification. */
394 && (vro1->type == vro2->type
395 || (vro1->type && vro2->type
396 && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type),
397 TYPE_MAIN_VARIANT (vro2->type))))
398 && expressions_equal_p (vro1->op0, vro2->op0)
399 && expressions_equal_p (vro1->op1, vro2->op1)
400 && expressions_equal_p (vro1->op2, vro2->op2));
403 /* Compute the hash for a reference operand VRO1. */
406 vn_reference_op_compute_hash (const vn_reference_op_t vro1, hashval_t result)
408 result = iterative_hash_hashval_t (vro1->opcode, result);
410 result = iterative_hash_expr (vro1->op0, result);
412 result = iterative_hash_expr (vro1->op1, result);
414 result = iterative_hash_expr (vro1->op2, result);
418 /* Return the hashcode for a given reference operation P1. */
421 vn_reference_hash (const void *p1)
423 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
424 return vr1->hashcode;
427 /* Compute a hash for the reference operation VR1 and return it. */
430 vn_reference_compute_hash (const vn_reference_t vr1)
432 hashval_t result = 0;
434 vn_reference_op_t vro;
435 HOST_WIDE_INT off = -1;
438 FOR_EACH_VEC_ELT (vn_reference_op_s, vr1->operands, i, vro)
440 if (vro->opcode == MEM_REF)
442 else if (vro->opcode != ADDR_EXPR)
454 result = iterative_hash_hashval_t (off, result);
457 && vro->opcode == ADDR_EXPR)
461 tree op = TREE_OPERAND (vro->op0, 0);
462 result = iterative_hash_hashval_t (TREE_CODE (op), result);
463 result = iterative_hash_expr (op, result);
467 result = vn_reference_op_compute_hash (vro, result);
471 result += SSA_NAME_VERSION (vr1->vuse);
476 /* Return true if reference operations P1 and P2 are equivalent. This
477 means they have the same set of operands and vuses. */
480 vn_reference_eq (const void *p1, const void *p2)
484 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
485 const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
486 if (vr1->hashcode != vr2->hashcode)
489 /* Early out if this is not a hash collision. */
490 if (vr1->hashcode != vr2->hashcode)
493 /* The VOP needs to be the same. */
494 if (vr1->vuse != vr2->vuse)
497 /* If the operands are the same we are done. */
498 if (vr1->operands == vr2->operands)
501 if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
504 if (INTEGRAL_TYPE_P (vr1->type)
505 && INTEGRAL_TYPE_P (vr2->type))
507 if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
510 else if (INTEGRAL_TYPE_P (vr1->type)
511 && (TYPE_PRECISION (vr1->type)
512 != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
514 else if (INTEGRAL_TYPE_P (vr2->type)
515 && (TYPE_PRECISION (vr2->type)
516 != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
523 HOST_WIDE_INT off1 = 0, off2 = 0;
524 vn_reference_op_t vro1, vro2;
525 vn_reference_op_s tem1, tem2;
526 bool deref1 = false, deref2 = false;
527 for (; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro1); i++)
529 if (vro1->opcode == MEM_REF)
535 for (; VEC_iterate (vn_reference_op_s, vr2->operands, j, vro2); j++)
537 if (vro2->opcode == MEM_REF)
545 if (deref1 && vro1->opcode == ADDR_EXPR)
547 memset (&tem1, 0, sizeof (tem1));
548 tem1.op0 = TREE_OPERAND (vro1->op0, 0);
549 tem1.type = TREE_TYPE (tem1.op0);
550 tem1.opcode = TREE_CODE (tem1.op0);
553 if (deref2 && vro2->opcode == ADDR_EXPR)
555 memset (&tem2, 0, sizeof (tem2));
556 tem2.op0 = TREE_OPERAND (vro2->op0, 0);
557 tem2.type = TREE_TYPE (tem2.op0);
558 tem2.opcode = TREE_CODE (tem2.op0);
561 if (!vn_reference_op_eq (vro1, vro2))
566 while (VEC_length (vn_reference_op_s, vr1->operands) != i
567 || VEC_length (vn_reference_op_s, vr2->operands) != j);
572 /* Copy the operations present in load/store REF into RESULT, a vector of
573 vn_reference_op_s's. */
576 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
578 if (TREE_CODE (ref) == TARGET_MEM_REF)
580 vn_reference_op_s temp;
582 memset (&temp, 0, sizeof (temp));
583 temp.type = TREE_TYPE (ref);
584 temp.opcode = TREE_CODE (ref);
585 temp.op0 = TMR_INDEX (ref);
586 temp.op1 = TMR_STEP (ref);
587 temp.op2 = TMR_OFFSET (ref);
589 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
591 memset (&temp, 0, sizeof (temp));
592 temp.type = NULL_TREE;
593 temp.opcode = ERROR_MARK;
594 temp.op0 = TMR_INDEX2 (ref);
596 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
598 memset (&temp, 0, sizeof (temp));
599 temp.type = NULL_TREE;
600 temp.opcode = TREE_CODE (TMR_BASE (ref));
601 temp.op0 = TMR_BASE (ref);
603 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
607 /* For non-calls, store the information that makes up the address. */
611 vn_reference_op_s temp;
613 memset (&temp, 0, sizeof (temp));
614 temp.type = TREE_TYPE (ref);
615 temp.opcode = TREE_CODE (ref);
621 /* The base address gets its own vn_reference_op_s structure. */
622 temp.op0 = TREE_OPERAND (ref, 1);
623 if (host_integerp (TREE_OPERAND (ref, 1), 0))
624 temp.off = TREE_INT_CST_LOW (TREE_OPERAND (ref, 1));
627 /* Record bits and position. */
628 temp.op0 = TREE_OPERAND (ref, 1);
629 temp.op1 = TREE_OPERAND (ref, 2);
632 /* The field decl is enough to unambiguously specify the field,
633 a matching type is not necessary and a mismatching type
634 is always a spurious difference. */
635 temp.type = NULL_TREE;
636 temp.op0 = TREE_OPERAND (ref, 1);
637 temp.op1 = TREE_OPERAND (ref, 2);
639 tree this_offset = component_ref_field_offset (ref);
641 && TREE_CODE (this_offset) == INTEGER_CST)
643 tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
644 if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0)
647 = double_int_add (tree_to_double_int (this_offset),
649 (tree_to_double_int (bit_offset),
651 ? 3 : exact_log2 (BITS_PER_UNIT),
652 HOST_BITS_PER_DOUBLE_INT, true));
653 if (double_int_fits_in_shwi_p (off))
659 case ARRAY_RANGE_REF:
661 /* Record index as operand. */
662 temp.op0 = TREE_OPERAND (ref, 1);
663 /* Always record lower bounds and element size. */
664 temp.op1 = array_ref_low_bound (ref);
665 temp.op2 = array_ref_element_size (ref);
666 if (TREE_CODE (temp.op0) == INTEGER_CST
667 && TREE_CODE (temp.op1) == INTEGER_CST
668 && TREE_CODE (temp.op2) == INTEGER_CST)
670 double_int off = tree_to_double_int (temp.op0);
671 off = double_int_add (off,
673 (tree_to_double_int (temp.op1)));
674 off = double_int_mul (off, tree_to_double_int (temp.op2));
675 if (double_int_fits_in_shwi_p (off))
680 if (DECL_HARD_REGISTER (ref))
689 /* Canonicalize decls to MEM[&decl] which is what we end up with
690 when valueizing MEM[ptr] with ptr = &decl. */
691 temp.opcode = MEM_REF;
692 temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0);
694 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
695 temp.opcode = ADDR_EXPR;
696 temp.op0 = build_fold_addr_expr (ref);
697 temp.type = TREE_TYPE (temp.op0);
711 if (is_gimple_min_invariant (ref))
717 /* These are only interesting for their operands, their
718 existence, and their type. They will never be the last
719 ref in the chain of references (IE they require an
720 operand), so we don't have to put anything
721 for op* as it will be handled by the iteration */
723 case VIEW_CONVERT_EXPR:
727 /* This is only interesting for its constant offset. */
728 temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
733 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
735 if (REFERENCE_CLASS_P (ref)
736 || (TREE_CODE (ref) == ADDR_EXPR
737 && !is_gimple_min_invariant (ref)))
738 ref = TREE_OPERAND (ref, 0);
744 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
745 operands in *OPS, the reference alias set SET and the reference type TYPE.
746 Return true if something useful was produced. */
749 ao_ref_init_from_vn_reference (ao_ref *ref,
750 alias_set_type set, tree type,
751 VEC (vn_reference_op_s, heap) *ops)
753 vn_reference_op_t op;
755 tree base = NULL_TREE;
757 HOST_WIDE_INT offset = 0;
758 HOST_WIDE_INT max_size;
759 HOST_WIDE_INT size = -1;
760 tree size_tree = NULL_TREE;
761 alias_set_type base_alias_set = -1;
763 /* First get the final access size from just the outermost expression. */
764 op = VEC_index (vn_reference_op_s, ops, 0);
765 if (op->opcode == COMPONENT_REF)
766 size_tree = DECL_SIZE (op->op0);
767 else if (op->opcode == BIT_FIELD_REF)
771 enum machine_mode mode = TYPE_MODE (type);
773 size_tree = TYPE_SIZE (type);
775 size = GET_MODE_BITSIZE (mode);
777 if (size_tree != NULL_TREE)
779 if (!host_integerp (size_tree, 1))
782 size = TREE_INT_CST_LOW (size_tree);
785 /* Initially, maxsize is the same as the accessed element size.
786 In the following it will only grow (or become -1). */
789 /* Compute cumulative bit-offset for nested component-refs and array-refs,
790 and find the ultimate containing object. */
791 FOR_EACH_VEC_ELT (vn_reference_op_s, ops, i, op)
795 /* These may be in the reference ops, but we cannot do anything
796 sensible with them here. */
798 /* Apart from ADDR_EXPR arguments to MEM_REF. */
799 if (base != NULL_TREE
800 && TREE_CODE (base) == MEM_REF
802 && DECL_P (TREE_OPERAND (op->op0, 0)))
804 vn_reference_op_t pop = VEC_index (vn_reference_op_s, ops, i-1);
805 base = TREE_OPERAND (op->op0, 0);
812 offset += pop->off * BITS_PER_UNIT;
820 /* Record the base objects. */
822 base_alias_set = get_deref_alias_set (op->op0);
823 *op0_p = build2 (MEM_REF, op->type,
825 op0_p = &TREE_OPERAND (*op0_p, 0);
836 /* And now the usual component-reference style ops. */
838 offset += tree_low_cst (op->op1, 0);
843 tree field = op->op0;
844 /* We do not have a complete COMPONENT_REF tree here so we
845 cannot use component_ref_field_offset. Do the interesting
849 || !host_integerp (DECL_FIELD_OFFSET (field), 1))
853 offset += (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field))
855 offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
860 case ARRAY_RANGE_REF:
862 /* We recorded the lower bound and the element size. */
863 if (!host_integerp (op->op0, 0)
864 || !host_integerp (op->op1, 0)
865 || !host_integerp (op->op2, 0))
869 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (op->op0);
870 hindex -= TREE_INT_CST_LOW (op->op1);
871 hindex *= TREE_INT_CST_LOW (op->op2);
872 hindex *= BITS_PER_UNIT;
884 case VIEW_CONVERT_EXPR:
901 if (base == NULL_TREE)
904 ref->ref = NULL_TREE;
906 ref->offset = offset;
908 ref->max_size = max_size;
909 ref->ref_alias_set = set;
910 if (base_alias_set != -1)
911 ref->base_alias_set = base_alias_set;
913 ref->base_alias_set = get_alias_set (base);
918 /* Copy the operations present in load/store/call REF into RESULT, a vector of
919 vn_reference_op_s's. */
922 copy_reference_ops_from_call (gimple call,
923 VEC(vn_reference_op_s, heap) **result)
925 vn_reference_op_s temp;
928 /* Copy the type, opcode, function being called and static chain. */
929 memset (&temp, 0, sizeof (temp));
930 temp.type = gimple_call_return_type (call);
931 temp.opcode = CALL_EXPR;
932 temp.op0 = gimple_call_fn (call);
933 temp.op1 = gimple_call_chain (call);
935 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
937 /* Copy the call arguments. As they can be references as well,
938 just chain them together. */
939 for (i = 0; i < gimple_call_num_args (call); ++i)
941 tree callarg = gimple_call_arg (call, i);
942 copy_reference_ops_from_ref (callarg, result);
946 /* Create a vector of vn_reference_op_s structures from REF, a
947 REFERENCE_CLASS_P tree. The vector is not shared. */
949 static VEC(vn_reference_op_s, heap) *
950 create_reference_ops_from_ref (tree ref)
952 VEC (vn_reference_op_s, heap) *result = NULL;
954 copy_reference_ops_from_ref (ref, &result);
958 /* Create a vector of vn_reference_op_s structures from CALL, a
959 call statement. The vector is not shared. */
961 static VEC(vn_reference_op_s, heap) *
962 create_reference_ops_from_call (gimple call)
964 VEC (vn_reference_op_s, heap) *result = NULL;
966 copy_reference_ops_from_call (call, &result);
970 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
971 *I_P to point to the last element of the replacement. */
973 vn_reference_fold_indirect (VEC (vn_reference_op_s, heap) **ops,
976 unsigned int i = *i_p;
977 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
978 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
980 HOST_WIDE_INT addr_offset;
982 /* The only thing we have to do is from &OBJ.foo.bar add the offset
983 from .foo.bar to the preceeding MEM_REF offset and replace the
984 address with &OBJ. */
985 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
987 gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
988 if (addr_base != op->op0)
990 double_int off = tree_to_double_int (mem_op->op0);
991 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
992 off = double_int_add (off, shwi_to_double_int (addr_offset));
993 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
994 op->op0 = build_fold_addr_expr (addr_base);
995 if (host_integerp (mem_op->op0, 0))
996 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1002 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1003 *I_P to point to the last element of the replacement. */
1005 vn_reference_maybe_forwprop_address (VEC (vn_reference_op_s, heap) **ops,
1008 unsigned int i = *i_p;
1009 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
1010 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
1012 enum tree_code code;
1015 def_stmt = SSA_NAME_DEF_STMT (op->op0);
1016 if (!is_gimple_assign (def_stmt))
1019 code = gimple_assign_rhs_code (def_stmt);
1020 if (code != ADDR_EXPR
1021 && code != POINTER_PLUS_EXPR)
1024 off = tree_to_double_int (mem_op->op0);
1025 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
1027 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1028 from .foo.bar to the preceeding MEM_REF offset and replace the
1029 address with &OBJ. */
1030 if (code == ADDR_EXPR)
1032 tree addr, addr_base;
1033 HOST_WIDE_INT addr_offset;
1035 addr = gimple_assign_rhs1 (def_stmt);
1036 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1039 || TREE_CODE (addr_base) != MEM_REF)
1042 off = double_int_add (off, shwi_to_double_int (addr_offset));
1043 off = double_int_add (off, mem_ref_offset (addr_base));
1044 op->op0 = TREE_OPERAND (addr_base, 0);
1049 ptr = gimple_assign_rhs1 (def_stmt);
1050 ptroff = gimple_assign_rhs2 (def_stmt);
1051 if (TREE_CODE (ptr) != SSA_NAME
1052 || TREE_CODE (ptroff) != INTEGER_CST)
1055 off = double_int_add (off, tree_to_double_int (ptroff));
1059 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
1060 if (host_integerp (mem_op->op0, 0))
1061 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1064 if (TREE_CODE (op->op0) == SSA_NAME)
1065 op->op0 = SSA_VAL (op->op0);
1066 if (TREE_CODE (op->op0) != SSA_NAME)
1067 op->opcode = TREE_CODE (op->op0);
1070 if (TREE_CODE (op->op0) == SSA_NAME)
1071 vn_reference_maybe_forwprop_address (ops, i_p);
1072 else if (TREE_CODE (op->op0) == ADDR_EXPR)
1073 vn_reference_fold_indirect (ops, i_p);
1076 /* Optimize the reference REF to a constant if possible or return
1077 NULL_TREE if not. */
1080 fully_constant_vn_reference_p (vn_reference_t ref)
1082 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1083 vn_reference_op_t op;
1085 /* Try to simplify the translated expression if it is
1086 a call to a builtin function with at most two arguments. */
1087 op = VEC_index (vn_reference_op_s, operands, 0);
1088 if (op->opcode == CALL_EXPR
1089 && TREE_CODE (op->op0) == ADDR_EXPR
1090 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1091 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1092 && VEC_length (vn_reference_op_s, operands) >= 2
1093 && VEC_length (vn_reference_op_s, operands) <= 3)
1095 vn_reference_op_t arg0, arg1 = NULL;
1096 bool anyconst = false;
1097 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1098 if (VEC_length (vn_reference_op_s, operands) > 2)
1099 arg1 = VEC_index (vn_reference_op_s, operands, 2);
1100 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1101 || (arg0->opcode == ADDR_EXPR
1102 && is_gimple_min_invariant (arg0->op0)))
1105 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1106 || (arg1->opcode == ADDR_EXPR
1107 && is_gimple_min_invariant (arg1->op0))))
1111 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1114 arg1 ? arg1->op0 : NULL);
1116 && TREE_CODE (folded) == NOP_EXPR)
1117 folded = TREE_OPERAND (folded, 0);
1119 && is_gimple_min_invariant (folded))
1124 /* Simplify reads from constant strings. */
1125 else if (op->opcode == ARRAY_REF
1126 && TREE_CODE (op->op0) == INTEGER_CST
1127 && integer_zerop (op->op1)
1128 && VEC_length (vn_reference_op_s, operands) == 2)
1130 vn_reference_op_t arg0;
1131 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1132 if (arg0->opcode == STRING_CST
1133 && (TYPE_MODE (op->type)
1134 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0->op0))))
1135 && GET_MODE_CLASS (TYPE_MODE (op->type)) == MODE_INT
1136 && GET_MODE_SIZE (TYPE_MODE (op->type)) == 1
1137 && compare_tree_int (op->op0, TREE_STRING_LENGTH (arg0->op0)) < 0)
1138 return build_int_cst_type (op->type,
1139 (TREE_STRING_POINTER (arg0->op0)
1140 [TREE_INT_CST_LOW (op->op0)]));
1146 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1147 structures into their value numbers. This is done in-place, and
1148 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1149 whether any operands were valueized. */
1151 static VEC (vn_reference_op_s, heap) *
1152 valueize_refs_1 (VEC (vn_reference_op_s, heap) *orig, bool *valueized_anything)
1154 vn_reference_op_t vro;
1157 *valueized_anything = false;
1159 FOR_EACH_VEC_ELT (vn_reference_op_s, orig, i, vro)
1161 if (vro->opcode == SSA_NAME
1162 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1164 tree tem = SSA_VAL (vro->op0);
1165 if (tem != vro->op0)
1167 *valueized_anything = true;
1170 /* If it transforms from an SSA_NAME to a constant, update
1172 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1173 vro->opcode = TREE_CODE (vro->op0);
1175 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1177 tree tem = SSA_VAL (vro->op1);
1178 if (tem != vro->op1)
1180 *valueized_anything = true;
1184 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1186 tree tem = SSA_VAL (vro->op2);
1187 if (tem != vro->op2)
1189 *valueized_anything = true;
1193 /* If it transforms from an SSA_NAME to an address, fold with
1194 a preceding indirect reference. */
1197 && TREE_CODE (vro->op0) == ADDR_EXPR
1198 && VEC_index (vn_reference_op_s,
1199 orig, i - 1)->opcode == MEM_REF)
1200 vn_reference_fold_indirect (&orig, &i);
1202 && vro->opcode == SSA_NAME
1203 && VEC_index (vn_reference_op_s,
1204 orig, i - 1)->opcode == MEM_REF)
1205 vn_reference_maybe_forwprop_address (&orig, &i);
1206 /* If it transforms a non-constant ARRAY_REF into a constant
1207 one, adjust the constant offset. */
1208 else if (vro->opcode == ARRAY_REF
1210 && TREE_CODE (vro->op0) == INTEGER_CST
1211 && TREE_CODE (vro->op1) == INTEGER_CST
1212 && TREE_CODE (vro->op2) == INTEGER_CST)
1214 double_int off = tree_to_double_int (vro->op0);
1215 off = double_int_add (off,
1217 (tree_to_double_int (vro->op1)));
1218 off = double_int_mul (off, tree_to_double_int (vro->op2));
1219 if (double_int_fits_in_shwi_p (off))
1227 static VEC (vn_reference_op_s, heap) *
1228 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
1231 return valueize_refs_1 (orig, &tem);
1234 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
1236 /* Create a vector of vn_reference_op_s structures from REF, a
1237 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1238 this function. *VALUEIZED_ANYTHING will specify whether any
1239 operands were valueized. */
1241 static VEC(vn_reference_op_s, heap) *
1242 valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything)
1246 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1247 copy_reference_ops_from_ref (ref, &shared_lookup_references);
1248 shared_lookup_references = valueize_refs_1 (shared_lookup_references,
1249 valueized_anything);
1250 return shared_lookup_references;
1253 /* Create a vector of vn_reference_op_s structures from CALL, a
1254 call statement. The vector is shared among all callers of
1257 static VEC(vn_reference_op_s, heap) *
1258 valueize_shared_reference_ops_from_call (gimple call)
1262 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1263 copy_reference_ops_from_call (call, &shared_lookup_references);
1264 shared_lookup_references = valueize_refs (shared_lookup_references);
1265 return shared_lookup_references;
1268 /* Lookup a SCCVN reference operation VR in the current hash table.
1269 Returns the resulting value number if it exists in the hash table,
1270 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1271 vn_reference_t stored in the hashtable if something is found. */
1274 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1279 hash = vr->hashcode;
1280 slot = htab_find_slot_with_hash (current_info->references, vr,
1282 if (!slot && current_info == optimistic_info)
1283 slot = htab_find_slot_with_hash (valid_info->references, vr,
1288 *vnresult = (vn_reference_t)*slot;
1289 return ((vn_reference_t)*slot)->result;
1295 static tree *last_vuse_ptr;
1296 static vn_lookup_kind vn_walk_kind;
1297 static vn_lookup_kind default_vn_walk_kind;
1299 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1300 with the current VUSE and performs the expression lookup. */
1303 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
1305 vn_reference_t vr = (vn_reference_t)vr_;
1310 *last_vuse_ptr = vuse;
1312 /* Fixup vuse and hash. */
1314 vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1315 vr->vuse = SSA_VAL (vuse);
1317 vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1319 hash = vr->hashcode;
1320 slot = htab_find_slot_with_hash (current_info->references, vr,
1322 if (!slot && current_info == optimistic_info)
1323 slot = htab_find_slot_with_hash (valid_info->references, vr,
1331 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1332 from the statement defining VUSE and if not successful tries to
1333 translate *REFP and VR_ through an aggregate copy at the defintion
1337 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_)
1339 vn_reference_t vr = (vn_reference_t)vr_;
1340 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1342 HOST_WIDE_INT offset, maxsize;
1343 static VEC (vn_reference_op_s, heap) *lhs_ops = NULL;
1345 bool lhs_ref_ok = false;
1347 /* First try to disambiguate after value-replacing in the definitions LHS. */
1348 if (is_gimple_assign (def_stmt))
1350 VEC (vn_reference_op_s, heap) *tem;
1351 tree lhs = gimple_assign_lhs (def_stmt);
1352 bool valueized_anything = false;
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_1 (lhs_ops, &valueized_anything);
1358 gcc_assert (lhs_ops == tem);
1359 if (valueized_anything)
1361 lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
1362 get_alias_set (lhs),
1363 TREE_TYPE (lhs), lhs_ops);
1365 && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1370 ao_ref_init (&lhs_ref, lhs);
1375 base = ao_ref_base (ref);
1376 offset = ref->offset;
1377 maxsize = ref->max_size;
1379 /* If we cannot constrain the size of the reference we cannot
1380 test if anything kills it. */
1384 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1385 from that defintion.
1387 if (is_gimple_reg_type (vr->type)
1388 && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
1389 && integer_zerop (gimple_call_arg (def_stmt, 1))
1390 && host_integerp (gimple_call_arg (def_stmt, 2), 1)
1391 && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1393 tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1395 HOST_WIDE_INT offset2, size2, maxsize2;
1396 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1397 size2 = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2)) * 8;
1398 if ((unsigned HOST_WIDE_INT)size2 / 8
1399 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2))
1401 && operand_equal_p (base, base2, 0)
1402 && offset2 <= offset
1403 && offset2 + size2 >= offset + maxsize)
1405 tree val = build_zero_cst (vr->type);
1406 unsigned int value_id = get_or_alloc_constant_value_id (val);
1407 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1408 VEC_copy (vn_reference_op_s,
1409 heap, vr->operands),
1414 /* 2) Assignment from an empty CONSTRUCTOR. */
1415 else if (is_gimple_reg_type (vr->type)
1416 && gimple_assign_single_p (def_stmt)
1417 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1418 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1421 HOST_WIDE_INT offset2, size2, maxsize2;
1422 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1423 &offset2, &size2, &maxsize2);
1425 && operand_equal_p (base, base2, 0)
1426 && offset2 <= offset
1427 && offset2 + size2 >= offset + maxsize)
1429 tree val = build_zero_cst (vr->type);
1430 unsigned int value_id = get_or_alloc_constant_value_id (val);
1431 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1432 VEC_copy (vn_reference_op_s,
1433 heap, vr->operands),
1438 /* 3) For aggregate copies translate the reference through them if
1439 the copy kills ref. */
1440 else if (vn_walk_kind == VN_WALKREWRITE
1441 && gimple_assign_single_p (def_stmt)
1442 && (DECL_P (gimple_assign_rhs1 (def_stmt))
1443 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
1444 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1447 HOST_WIDE_INT offset2, size2, maxsize2;
1449 VEC (vn_reference_op_s, heap) *rhs = NULL;
1450 vn_reference_op_t vro;
1456 /* See if the assignment kills REF. */
1457 base2 = ao_ref_base (&lhs_ref);
1458 offset2 = lhs_ref.offset;
1459 size2 = lhs_ref.size;
1460 maxsize2 = lhs_ref.max_size;
1462 || (base != base2 && !operand_equal_p (base, base2, 0))
1464 || offset2 + size2 < offset + maxsize)
1467 /* Find the common base of ref and the lhs. lhs_ops already
1468 contains valueized operands for the lhs. */
1469 i = VEC_length (vn_reference_op_s, vr->operands) - 1;
1470 j = VEC_length (vn_reference_op_s, lhs_ops) - 1;
1471 while (j >= 0 && i >= 0
1472 && vn_reference_op_eq (VEC_index (vn_reference_op_s,
1474 VEC_index (vn_reference_op_s, lhs_ops, j)))
1480 /* ??? The innermost op should always be a MEM_REF and we already
1481 checked that the assignment to the lhs kills vr. Thus for
1482 aggregate copies using char[] types the vn_reference_op_eq
1483 may fail when comparing types for compatibility. But we really
1484 don't care here - further lookups with the rewritten operands
1485 will simply fail if we messed up types too badly. */
1486 if (j == 0 && i >= 0
1487 && VEC_index (vn_reference_op_s, lhs_ops, 0)->opcode == MEM_REF
1488 && VEC_index (vn_reference_op_s, lhs_ops, 0)->off != -1
1489 && (VEC_index (vn_reference_op_s, lhs_ops, 0)->off
1490 == VEC_index (vn_reference_op_s, vr->operands, i)->off))
1493 /* i now points to the first additional op.
1494 ??? LHS may not be completely contained in VR, one or more
1495 VIEW_CONVERT_EXPRs could be in its way. We could at least
1496 try handling outermost VIEW_CONVERT_EXPRs. */
1500 /* Now re-write REF to be based on the rhs of the assignment. */
1501 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1502 /* We need to pre-pend vr->operands[0..i] to rhs. */
1503 if (i + 1 + VEC_length (vn_reference_op_s, rhs)
1504 > VEC_length (vn_reference_op_s, vr->operands))
1506 VEC (vn_reference_op_s, heap) *old = vr->operands;
1507 VEC_safe_grow (vn_reference_op_s, heap, vr->operands,
1508 i + 1 + VEC_length (vn_reference_op_s, rhs));
1509 if (old == shared_lookup_references
1510 && vr->operands != old)
1511 shared_lookup_references = NULL;
1514 VEC_truncate (vn_reference_op_s, vr->operands,
1515 i + 1 + VEC_length (vn_reference_op_s, rhs));
1516 FOR_EACH_VEC_ELT (vn_reference_op_s, rhs, j, vro)
1517 VEC_replace (vn_reference_op_s, vr->operands, i + 1 + j, vro);
1518 VEC_free (vn_reference_op_s, heap, rhs);
1519 vr->hashcode = vn_reference_compute_hash (vr);
1521 /* Adjust *ref from the new operands. */
1522 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1524 /* This can happen with bitfields. */
1525 if (ref->size != r.size)
1529 /* Do not update last seen VUSE after translating. */
1530 last_vuse_ptr = NULL;
1532 /* Keep looking for the adjusted *REF / VR pair. */
1536 /* 4) For memcpy copies translate the reference through them if
1537 the copy kills ref. */
1538 else if (vn_walk_kind == VN_WALKREWRITE
1539 && is_gimple_reg_type (vr->type)
1540 /* ??? Handle BCOPY as well. */
1541 && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
1542 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
1543 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
1544 && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
1545 || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
1546 && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
1547 || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
1548 && host_integerp (gimple_call_arg (def_stmt, 2), 1))
1552 HOST_WIDE_INT rhs_offset, copy_size, lhs_offset;
1553 vn_reference_op_s op;
1557 /* Only handle non-variable, addressable refs. */
1558 if (ref->size != maxsize
1559 || offset % BITS_PER_UNIT != 0
1560 || ref->size % BITS_PER_UNIT != 0)
1563 /* Extract a pointer base and an offset for the destination. */
1564 lhs = gimple_call_arg (def_stmt, 0);
1566 if (TREE_CODE (lhs) == SSA_NAME)
1567 lhs = SSA_VAL (lhs);
1568 if (TREE_CODE (lhs) == ADDR_EXPR)
1570 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
1574 if (TREE_CODE (tem) == MEM_REF
1575 && host_integerp (TREE_OPERAND (tem, 1), 1))
1577 lhs = TREE_OPERAND (tem, 0);
1578 lhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1580 else if (DECL_P (tem))
1581 lhs = build_fold_addr_expr (tem);
1585 if (TREE_CODE (lhs) != SSA_NAME
1586 && TREE_CODE (lhs) != ADDR_EXPR)
1589 /* Extract a pointer base and an offset for the source. */
1590 rhs = gimple_call_arg (def_stmt, 1);
1592 if (TREE_CODE (rhs) == SSA_NAME)
1593 rhs = SSA_VAL (rhs);
1594 if (TREE_CODE (rhs) == ADDR_EXPR)
1596 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
1600 if (TREE_CODE (tem) == MEM_REF
1601 && host_integerp (TREE_OPERAND (tem, 1), 1))
1603 rhs = TREE_OPERAND (tem, 0);
1604 rhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1606 else if (DECL_P (tem))
1607 rhs = build_fold_addr_expr (tem);
1611 if (TREE_CODE (rhs) != SSA_NAME
1612 && TREE_CODE (rhs) != ADDR_EXPR)
1615 copy_size = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2));
1617 /* The bases of the destination and the references have to agree. */
1618 if ((TREE_CODE (base) != MEM_REF
1620 || (TREE_CODE (base) == MEM_REF
1621 && (TREE_OPERAND (base, 0) != lhs
1622 || !host_integerp (TREE_OPERAND (base, 1), 1)))
1624 && (TREE_CODE (lhs) != ADDR_EXPR
1625 || TREE_OPERAND (lhs, 0) != base)))
1628 /* And the access has to be contained within the memcpy destination. */
1629 at = offset / BITS_PER_UNIT;
1630 if (TREE_CODE (base) == MEM_REF)
1631 at += TREE_INT_CST_LOW (TREE_OPERAND (base, 1));
1633 || lhs_offset + copy_size < at + maxsize / BITS_PER_UNIT)
1636 /* Make room for 2 operands in the new reference. */
1637 if (VEC_length (vn_reference_op_s, vr->operands) < 2)
1639 VEC (vn_reference_op_s, heap) *old = vr->operands;
1640 VEC_safe_grow (vn_reference_op_s, heap, vr->operands, 2);
1641 if (old == shared_lookup_references
1642 && vr->operands != old)
1643 shared_lookup_references = NULL;
1646 VEC_truncate (vn_reference_op_s, vr->operands, 2);
1648 /* The looked-through reference is a simple MEM_REF. */
1649 memset (&op, 0, sizeof (op));
1651 op.opcode = MEM_REF;
1652 op.op0 = build_int_cst (ptr_type_node, at - rhs_offset);
1653 op.off = at - lhs_offset + rhs_offset;
1654 VEC_replace (vn_reference_op_s, vr->operands, 0, &op);
1655 op.type = TREE_TYPE (rhs);
1656 op.opcode = TREE_CODE (rhs);
1659 VEC_replace (vn_reference_op_s, vr->operands, 1, &op);
1660 vr->hashcode = vn_reference_compute_hash (vr);
1662 /* Adjust *ref from the new operands. */
1663 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1665 /* This can happen with bitfields. */
1666 if (ref->size != r.size)
1670 /* Do not update last seen VUSE after translating. */
1671 last_vuse_ptr = NULL;
1673 /* Keep looking for the adjusted *REF / VR pair. */
1677 /* Bail out and stop walking. */
1681 /* Lookup a reference operation by it's parts, in the current hash table.
1682 Returns the resulting value number if it exists in the hash table,
1683 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1684 vn_reference_t stored in the hashtable if something is found. */
1687 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
1688 VEC (vn_reference_op_s, heap) *operands,
1689 vn_reference_t *vnresult, vn_lookup_kind kind)
1691 struct vn_reference_s vr1;
1699 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1700 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1701 VEC_safe_grow (vn_reference_op_s, heap, shared_lookup_references,
1702 VEC_length (vn_reference_op_s, operands));
1703 memcpy (VEC_address (vn_reference_op_s, shared_lookup_references),
1704 VEC_address (vn_reference_op_s, operands),
1705 sizeof (vn_reference_op_s)
1706 * VEC_length (vn_reference_op_s, operands));
1707 vr1.operands = operands = shared_lookup_references
1708 = valueize_refs (shared_lookup_references);
1711 vr1.hashcode = vn_reference_compute_hash (&vr1);
1712 if ((cst = fully_constant_vn_reference_p (&vr1)))
1715 vn_reference_lookup_1 (&vr1, vnresult);
1717 && kind != VN_NOWALK
1721 vn_walk_kind = kind;
1722 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
1724 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1725 vn_reference_lookup_2,
1726 vn_reference_lookup_3, &vr1);
1727 if (vr1.operands != operands)
1728 VEC_free (vn_reference_op_s, heap, vr1.operands);
1732 return (*vnresult)->result;
1737 /* Lookup OP in the current hash table, and return the resulting value
1738 number if it exists in the hash table. Return NULL_TREE if it does
1739 not exist in the hash table or if the result field of the structure
1740 was NULL.. VNRESULT will be filled in with the vn_reference_t
1741 stored in the hashtable if one exists. */
1744 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
1745 vn_reference_t *vnresult)
1747 VEC (vn_reference_op_s, heap) *operands;
1748 struct vn_reference_s vr1;
1750 bool valuezied_anything;
1755 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1756 vr1.operands = operands
1757 = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
1758 vr1.type = TREE_TYPE (op);
1759 vr1.set = get_alias_set (op);
1760 vr1.hashcode = vn_reference_compute_hash (&vr1);
1761 if ((cst = fully_constant_vn_reference_p (&vr1)))
1764 if (kind != VN_NOWALK
1767 vn_reference_t wvnresult;
1769 /* Make sure to use a valueized reference if we valueized anything.
1770 Otherwise preserve the full reference for advanced TBAA. */
1771 if (!valuezied_anything
1772 || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
1774 ao_ref_init (&r, op);
1775 vn_walk_kind = kind;
1777 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1778 vn_reference_lookup_2,
1779 vn_reference_lookup_3, &vr1);
1780 if (vr1.operands != operands)
1781 VEC_free (vn_reference_op_s, heap, vr1.operands);
1785 *vnresult = wvnresult;
1786 return wvnresult->result;
1792 return vn_reference_lookup_1 (&vr1, vnresult);
1796 /* Insert OP into the current hash table with a value number of
1797 RESULT, and return the resulting reference structure we created. */
1800 vn_reference_insert (tree op, tree result, tree vuse)
1805 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1806 if (TREE_CODE (result) == SSA_NAME)
1807 vr1->value_id = VN_INFO (result)->value_id;
1809 vr1->value_id = get_or_alloc_constant_value_id (result);
1810 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1811 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1812 vr1->type = TREE_TYPE (op);
1813 vr1->set = get_alias_set (op);
1814 vr1->hashcode = vn_reference_compute_hash (vr1);
1815 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1817 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1820 /* Because we lookup stores using vuses, and value number failures
1821 using the vdefs (see visit_reference_op_store for how and why),
1822 it's possible that on failure we may try to insert an already
1823 inserted store. This is not wrong, there is no ssa name for a
1824 store that we could use as a differentiator anyway. Thus, unlike
1825 the other lookup functions, you cannot gcc_assert (!*slot)
1828 /* But free the old slot in case of a collision. */
1830 free_reference (*slot);
1836 /* Insert a reference by it's pieces into the current hash table with
1837 a value number of RESULT. Return the resulting reference
1838 structure we created. */
1841 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
1842 VEC (vn_reference_op_s, heap) *operands,
1843 tree result, unsigned int value_id)
1849 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1850 vr1->value_id = value_id;
1851 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1852 vr1->operands = valueize_refs (operands);
1855 vr1->hashcode = vn_reference_compute_hash (vr1);
1856 if (result && TREE_CODE (result) == SSA_NAME)
1857 result = SSA_VAL (result);
1858 vr1->result = result;
1860 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1863 /* At this point we should have all the things inserted that we have
1864 seen before, and we should never try inserting something that
1866 gcc_assert (!*slot);
1868 free_reference (*slot);
1874 /* Compute and return the hash value for nary operation VBO1. */
1877 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1882 for (i = 0; i < vno1->length; ++i)
1883 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1884 vno1->op[i] = SSA_VAL (vno1->op[i]);
1886 if (vno1->length == 2
1887 && commutative_tree_code (vno1->opcode)
1888 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1890 tree temp = vno1->op[0];
1891 vno1->op[0] = vno1->op[1];
1895 hash = iterative_hash_hashval_t (vno1->opcode, 0);
1896 for (i = 0; i < vno1->length; ++i)
1897 hash = iterative_hash_expr (vno1->op[i], hash);
1902 /* Return the computed hashcode for nary operation P1. */
1905 vn_nary_op_hash (const void *p1)
1907 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1908 return vno1->hashcode;
1911 /* Compare nary operations P1 and P2 and return true if they are
1915 vn_nary_op_eq (const void *p1, const void *p2)
1917 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1918 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1921 if (vno1->hashcode != vno2->hashcode)
1924 if (vno1->length != vno2->length)
1927 if (vno1->opcode != vno2->opcode
1928 || !types_compatible_p (vno1->type, vno2->type))
1931 for (i = 0; i < vno1->length; ++i)
1932 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1938 /* Initialize VNO from the pieces provided. */
1941 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
1942 enum tree_code code, tree type, tree *ops)
1945 vno->length = length;
1947 memcpy (&vno->op[0], ops, sizeof (tree) * length);
1950 /* Initialize VNO from OP. */
1953 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
1957 vno->opcode = TREE_CODE (op);
1958 vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
1959 vno->type = TREE_TYPE (op);
1960 for (i = 0; i < vno->length; ++i)
1961 vno->op[i] = TREE_OPERAND (op, i);
1964 /* Return the number of operands for a vn_nary ops structure from STMT. */
1967 vn_nary_length_from_stmt (gimple stmt)
1969 switch (gimple_assign_rhs_code (stmt))
1973 case VIEW_CONVERT_EXPR:
1977 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
1980 return gimple_num_ops (stmt) - 1;
1984 /* Initialize VNO from STMT. */
1987 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple stmt)
1991 vno->opcode = gimple_assign_rhs_code (stmt);
1992 vno->type = gimple_expr_type (stmt);
1993 switch (vno->opcode)
1997 case VIEW_CONVERT_EXPR:
1999 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2003 vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2004 for (i = 0; i < vno->length; ++i)
2005 vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value;
2009 vno->length = gimple_num_ops (stmt) - 1;
2010 for (i = 0; i < vno->length; ++i)
2011 vno->op[i] = gimple_op (stmt, i + 1);
2015 /* Compute the hashcode for VNO and look for it in the hash table;
2016 return the resulting value number if it exists in the hash table.
2017 Return NULL_TREE if it does not exist in the hash table or if the
2018 result field of the operation is NULL. VNRESULT will contain the
2019 vn_nary_op_t from the hashtable if it exists. */
2022 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
2029 vno->hashcode = vn_nary_op_compute_hash (vno);
2030 slot = htab_find_slot_with_hash (current_info->nary, vno, vno->hashcode,
2032 if (!slot && current_info == optimistic_info)
2033 slot = htab_find_slot_with_hash (valid_info->nary, vno, vno->hashcode,
2038 *vnresult = (vn_nary_op_t)*slot;
2039 return ((vn_nary_op_t)*slot)->result;
2042 /* Lookup a n-ary operation by its pieces and return the resulting value
2043 number if it exists in the hash table. Return NULL_TREE if it does
2044 not exist in the hash table or if the result field of the operation
2045 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2049 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2050 tree type, tree *ops, vn_nary_op_t *vnresult)
2052 vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s,
2053 sizeof_vn_nary_op (length));
2054 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2055 return vn_nary_op_lookup_1 (vno1, vnresult);
2058 /* Lookup OP in the current hash table, and return the resulting value
2059 number if it exists in the hash table. Return NULL_TREE if it does
2060 not exist in the hash table or if the result field of the operation
2061 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2065 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2068 = XALLOCAVAR (struct vn_nary_op_s,
2069 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op))));
2070 init_vn_nary_op_from_op (vno1, op);
2071 return vn_nary_op_lookup_1 (vno1, vnresult);
2074 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2075 value number if it exists in the hash table. Return NULL_TREE if
2076 it does not exist in the hash table. VNRESULT will contain the
2077 vn_nary_op_t from the hashtable if it exists. */
2080 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
2083 = XALLOCAVAR (struct vn_nary_op_s,
2084 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt)));
2085 init_vn_nary_op_from_stmt (vno1, stmt);
2086 return vn_nary_op_lookup_1 (vno1, vnresult);
2089 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2092 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2094 return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
2097 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2101 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
2103 vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
2104 ¤t_info->nary_obstack);
2106 vno1->value_id = value_id;
2107 vno1->length = length;
2108 vno1->result = result;
2113 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2114 VNO->HASHCODE first. */
2117 vn_nary_op_insert_into (vn_nary_op_t vno, htab_t table, bool compute_hash)
2122 vno->hashcode = vn_nary_op_compute_hash (vno);
2124 slot = htab_find_slot_with_hash (table, vno, vno->hashcode, INSERT);
2125 gcc_assert (!*slot);
2131 /* Insert a n-ary operation into the current hash table using it's
2132 pieces. Return the vn_nary_op_t structure we created and put in
2136 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
2137 tree type, tree *ops,
2138 tree result, unsigned int value_id)
2140 vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id);
2141 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2142 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2145 /* Insert OP into the current hash table with a value number of
2146 RESULT. Return the vn_nary_op_t structure we created and put in
2150 vn_nary_op_insert (tree op, tree result)
2152 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
2155 vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2156 init_vn_nary_op_from_op (vno1, op);
2157 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2160 /* Insert the rhs of STMT into the current hash table with a value number of
2164 vn_nary_op_insert_stmt (gimple stmt, tree result)
2167 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt),
2168 result, VN_INFO (result)->value_id);
2169 init_vn_nary_op_from_stmt (vno1, stmt);
2170 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2173 /* Compute a hashcode for PHI operation VP1 and return it. */
2175 static inline hashval_t
2176 vn_phi_compute_hash (vn_phi_t vp1)
2183 result = vp1->block->index;
2185 /* If all PHI arguments are constants we need to distinguish
2186 the PHI node via its type. */
2187 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
2188 result += (INTEGRAL_TYPE_P (type)
2189 + (INTEGRAL_TYPE_P (type)
2190 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
2192 FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2194 if (phi1op == VN_TOP)
2196 result = iterative_hash_expr (phi1op, result);
2202 /* Return the computed hashcode for phi operation P1. */
2205 vn_phi_hash (const void *p1)
2207 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2208 return vp1->hashcode;
2211 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2214 vn_phi_eq (const void *p1, const void *p2)
2216 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2217 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
2219 if (vp1->hashcode != vp2->hashcode)
2222 if (vp1->block == vp2->block)
2227 /* If the PHI nodes do not have compatible types
2228 they are not the same. */
2229 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
2230 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
2233 /* Any phi in the same block will have it's arguments in the
2234 same edge order, because of how we store phi nodes. */
2235 FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2237 tree phi2op = VEC_index (tree, vp2->phiargs, i);
2238 if (phi1op == VN_TOP || phi2op == VN_TOP)
2240 if (!expressions_equal_p (phi1op, phi2op))
2248 static VEC(tree, heap) *shared_lookup_phiargs;
2250 /* Lookup PHI in the current hash table, and return the resulting
2251 value number if it exists in the hash table. Return NULL_TREE if
2252 it does not exist in the hash table. */
2255 vn_phi_lookup (gimple phi)
2258 struct vn_phi_s vp1;
2261 VEC_truncate (tree, shared_lookup_phiargs, 0);
2263 /* Canonicalize the SSA_NAME's to their value number. */
2264 for (i = 0; i < gimple_phi_num_args (phi); i++)
2266 tree def = PHI_ARG_DEF (phi, i);
2267 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2268 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
2270 vp1.phiargs = shared_lookup_phiargs;
2271 vp1.block = gimple_bb (phi);
2272 vp1.hashcode = vn_phi_compute_hash (&vp1);
2273 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
2275 if (!slot && current_info == optimistic_info)
2276 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
2280 return ((vn_phi_t)*slot)->result;
2283 /* Insert PHI into the current hash table with a value number of
2287 vn_phi_insert (gimple phi, tree result)
2290 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
2292 VEC (tree, heap) *args = NULL;
2294 /* Canonicalize the SSA_NAME's to their value number. */
2295 for (i = 0; i < gimple_phi_num_args (phi); i++)
2297 tree def = PHI_ARG_DEF (phi, i);
2298 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2299 VEC_safe_push (tree, heap, args, def);
2301 vp1->value_id = VN_INFO (result)->value_id;
2302 vp1->phiargs = args;
2303 vp1->block = gimple_bb (phi);
2304 vp1->result = result;
2305 vp1->hashcode = vn_phi_compute_hash (vp1);
2307 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
2310 /* Because we iterate over phi operations more than once, it's
2311 possible the slot might already exist here, hence no assert.*/
2317 /* Print set of components in strongly connected component SCC to OUT. */
2320 print_scc (FILE *out, VEC (tree, heap) *scc)
2325 fprintf (out, "SCC consists of: ");
2326 FOR_EACH_VEC_ELT (tree, scc, i, var)
2328 print_generic_expr (out, var, 0);
2331 fprintf (out, "\n");
2334 /* Set the value number of FROM to TO, return true if it has changed
2338 set_ssa_val_to (tree from, tree to)
2340 tree currval = SSA_VAL (from);
2344 if (currval == from)
2346 if (dump_file && (dump_flags & TDF_DETAILS))
2348 fprintf (dump_file, "Not changing value number of ");
2349 print_generic_expr (dump_file, from, 0);
2350 fprintf (dump_file, " from VARYING to ");
2351 print_generic_expr (dump_file, to, 0);
2352 fprintf (dump_file, "\n");
2356 else if (TREE_CODE (to) == SSA_NAME
2357 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
2361 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2362 and invariants. So assert that here. */
2363 gcc_assert (to != NULL_TREE
2365 || TREE_CODE (to) == SSA_NAME
2366 || is_gimple_min_invariant (to)));
2368 if (dump_file && (dump_flags & TDF_DETAILS))
2370 fprintf (dump_file, "Setting value number of ");
2371 print_generic_expr (dump_file, from, 0);
2372 fprintf (dump_file, " to ");
2373 print_generic_expr (dump_file, to, 0);
2376 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
2378 VN_INFO (from)->valnum = to;
2379 if (dump_file && (dump_flags & TDF_DETAILS))
2380 fprintf (dump_file, " (changed)\n");
2383 if (dump_file && (dump_flags & TDF_DETAILS))
2384 fprintf (dump_file, "\n");
2388 /* Set all definitions in STMT to value number to themselves.
2389 Return true if a value number changed. */
2392 defs_to_varying (gimple stmt)
2394 bool changed = false;
2398 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2400 tree def = DEF_FROM_PTR (defp);
2402 VN_INFO (def)->use_processed = true;
2403 changed |= set_ssa_val_to (def, def);
2408 static bool expr_has_constants (tree expr);
2409 static tree valueize_expr (tree expr);
2411 /* Visit a copy between LHS and RHS, return true if the value number
2415 visit_copy (tree lhs, tree rhs)
2417 /* Follow chains of copies to their destination. */
2418 while (TREE_CODE (rhs) == SSA_NAME
2419 && SSA_VAL (rhs) != rhs)
2420 rhs = SSA_VAL (rhs);
2422 /* The copy may have a more interesting constant filled expression
2423 (we don't, since we know our RHS is just an SSA name). */
2424 if (TREE_CODE (rhs) == SSA_NAME)
2426 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
2427 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
2430 return set_ssa_val_to (lhs, rhs);
2433 /* Visit a nary operator RHS, value number it, and return true if the
2434 value number of LHS has changed as a result. */
2437 visit_nary_op (tree lhs, gimple stmt)
2439 bool changed = false;
2440 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2443 changed = set_ssa_val_to (lhs, result);
2446 changed = set_ssa_val_to (lhs, lhs);
2447 vn_nary_op_insert_stmt (stmt, lhs);
2453 /* Visit a call STMT storing into LHS. Return true if the value number
2454 of the LHS has changed as a result. */
2457 visit_reference_op_call (tree lhs, gimple stmt)
2459 bool changed = false;
2460 struct vn_reference_s vr1;
2462 tree vuse = gimple_vuse (stmt);
2464 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2465 vr1.operands = valueize_shared_reference_ops_from_call (stmt);
2466 vr1.type = gimple_expr_type (stmt);
2468 vr1.hashcode = vn_reference_compute_hash (&vr1);
2469 result = vn_reference_lookup_1 (&vr1, NULL);
2472 changed = set_ssa_val_to (lhs, result);
2473 if (TREE_CODE (result) == SSA_NAME
2474 && VN_INFO (result)->has_constants)
2475 VN_INFO (lhs)->has_constants = true;
2481 changed = set_ssa_val_to (lhs, lhs);
2482 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
2483 vr2->vuse = vr1.vuse;
2484 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
2485 vr2->type = vr1.type;
2487 vr2->hashcode = vr1.hashcode;
2489 slot = htab_find_slot_with_hash (current_info->references,
2490 vr2, vr2->hashcode, INSERT);
2492 free_reference (*slot);
2499 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2500 and return true if the value number of the LHS has changed as a result. */
2503 visit_reference_op_load (tree lhs, tree op, gimple stmt)
2505 bool changed = false;
2509 last_vuse = gimple_vuse (stmt);
2510 last_vuse_ptr = &last_vuse;
2511 result = vn_reference_lookup (op, gimple_vuse (stmt),
2512 default_vn_walk_kind, NULL);
2513 last_vuse_ptr = NULL;
2515 /* If we have a VCE, try looking up its operand as it might be stored in
2516 a different type. */
2517 if (!result && TREE_CODE (op) == VIEW_CONVERT_EXPR)
2518 result = vn_reference_lookup (TREE_OPERAND (op, 0), gimple_vuse (stmt),
2519 default_vn_walk_kind, NULL);
2521 /* We handle type-punning through unions by value-numbering based
2522 on offset and size of the access. Be prepared to handle a
2523 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2525 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
2527 /* We will be setting the value number of lhs to the value number
2528 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2529 So first simplify and lookup this expression to see if it
2530 is already available. */
2531 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
2532 if ((CONVERT_EXPR_P (val)
2533 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
2534 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
2536 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
2537 if ((CONVERT_EXPR_P (tem)
2538 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
2539 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
2540 TREE_TYPE (val), tem)))
2544 if (!is_gimple_min_invariant (val)
2545 && TREE_CODE (val) != SSA_NAME)
2546 result = vn_nary_op_lookup (val, NULL);
2547 /* If the expression is not yet available, value-number lhs to
2548 a new SSA_NAME we create. */
2551 result = make_ssa_name (SSA_NAME_VAR (lhs), gimple_build_nop ());
2552 /* Initialize value-number information properly. */
2553 VN_INFO_GET (result)->valnum = result;
2554 VN_INFO (result)->value_id = get_next_value_id ();
2555 VN_INFO (result)->expr = val;
2556 VN_INFO (result)->has_constants = expr_has_constants (val);
2557 VN_INFO (result)->needs_insertion = true;
2558 /* As all "inserted" statements are singleton SCCs, insert
2559 to the valid table. This is strictly needed to
2560 avoid re-generating new value SSA_NAMEs for the same
2561 expression during SCC iteration over and over (the
2562 optimistic table gets cleared after each iteration).
2563 We do not need to insert into the optimistic table, as
2564 lookups there will fall back to the valid table. */
2565 if (current_info == optimistic_info)
2567 current_info = valid_info;
2568 vn_nary_op_insert (val, result);
2569 current_info = optimistic_info;
2572 vn_nary_op_insert (val, result);
2573 if (dump_file && (dump_flags & TDF_DETAILS))
2575 fprintf (dump_file, "Inserting name ");
2576 print_generic_expr (dump_file, result, 0);
2577 fprintf (dump_file, " for expression ");
2578 print_generic_expr (dump_file, val, 0);
2579 fprintf (dump_file, "\n");
2586 changed = set_ssa_val_to (lhs, result);
2587 if (TREE_CODE (result) == SSA_NAME
2588 && VN_INFO (result)->has_constants)
2590 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
2591 VN_INFO (lhs)->has_constants = true;
2596 changed = set_ssa_val_to (lhs, lhs);
2597 vn_reference_insert (op, lhs, last_vuse);
2604 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2605 and return true if the value number of the LHS has changed as a result. */
2608 visit_reference_op_store (tree lhs, tree op, gimple stmt)
2610 bool changed = false;
2612 bool resultsame = false;
2614 /* First we want to lookup using the *vuses* from the store and see
2615 if there the last store to this location with the same address
2618 The vuses represent the memory state before the store. If the
2619 memory state, address, and value of the store is the same as the
2620 last store to this location, then this store will produce the
2621 same memory state as that store.
2623 In this case the vdef versions for this store are value numbered to those
2624 vuse versions, since they represent the same memory state after
2627 Otherwise, the vdefs for the store are used when inserting into
2628 the table, since the store generates a new memory state. */
2630 result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL);
2634 if (TREE_CODE (result) == SSA_NAME)
2635 result = SSA_VAL (result);
2636 if (TREE_CODE (op) == SSA_NAME)
2638 resultsame = expressions_equal_p (result, op);
2641 if (!result || !resultsame)
2645 if (dump_file && (dump_flags & TDF_DETAILS))
2647 fprintf (dump_file, "No store match\n");
2648 fprintf (dump_file, "Value numbering store ");
2649 print_generic_expr (dump_file, lhs, 0);
2650 fprintf (dump_file, " to ");
2651 print_generic_expr (dump_file, op, 0);
2652 fprintf (dump_file, "\n");
2654 /* Have to set value numbers before insert, since insert is
2655 going to valueize the references in-place. */
2656 if ((vdef = gimple_vdef (stmt)))
2658 VN_INFO (vdef)->use_processed = true;
2659 changed |= set_ssa_val_to (vdef, vdef);
2662 /* Do not insert structure copies into the tables. */
2663 if (is_gimple_min_invariant (op)
2664 || is_gimple_reg (op))
2665 vn_reference_insert (lhs, op, vdef);
2669 /* We had a match, so value number the vdef to have the value
2670 number of the vuse it came from. */
2673 if (dump_file && (dump_flags & TDF_DETAILS))
2674 fprintf (dump_file, "Store matched earlier value,"
2675 "value numbering store vdefs to matching vuses.\n");
2677 def = gimple_vdef (stmt);
2678 use = gimple_vuse (stmt);
2680 VN_INFO (def)->use_processed = true;
2681 changed |= set_ssa_val_to (def, SSA_VAL (use));
2687 /* Visit and value number PHI, return true if the value number
2691 visit_phi (gimple phi)
2693 bool changed = false;
2695 tree sameval = VN_TOP;
2696 bool allsame = true;
2699 /* TODO: We could check for this in init_sccvn, and replace this
2700 with a gcc_assert. */
2701 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
2702 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2704 /* See if all non-TOP arguments have the same value. TOP is
2705 equivalent to everything, so we can ignore it. */
2706 for (i = 0; i < gimple_phi_num_args (phi); i++)
2708 tree def = PHI_ARG_DEF (phi, i);
2710 if (TREE_CODE (def) == SSA_NAME)
2711 def = SSA_VAL (def);
2714 if (sameval == VN_TOP)
2720 if (!expressions_equal_p (def, sameval))
2728 /* If all value numbered to the same value, the phi node has that
2732 if (is_gimple_min_invariant (sameval))
2734 VN_INFO (PHI_RESULT (phi))->has_constants = true;
2735 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2739 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2740 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2743 if (TREE_CODE (sameval) == SSA_NAME)
2744 return visit_copy (PHI_RESULT (phi), sameval);
2746 return set_ssa_val_to (PHI_RESULT (phi), sameval);
2749 /* Otherwise, see if it is equivalent to a phi node in this block. */
2750 result = vn_phi_lookup (phi);
2753 if (TREE_CODE (result) == SSA_NAME)
2754 changed = visit_copy (PHI_RESULT (phi), result);
2756 changed = set_ssa_val_to (PHI_RESULT (phi), result);
2760 vn_phi_insert (phi, PHI_RESULT (phi));
2761 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2762 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
2763 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2769 /* Return true if EXPR contains constants. */
2772 expr_has_constants (tree expr)
2774 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2777 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
2780 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
2781 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
2782 /* Constants inside reference ops are rarely interesting, but
2783 it can take a lot of looking to find them. */
2785 case tcc_declaration:
2788 return is_gimple_min_invariant (expr);
2793 /* Return true if STMT contains constants. */
2796 stmt_has_constants (gimple stmt)
2798 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2801 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2803 case GIMPLE_UNARY_RHS:
2804 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2806 case GIMPLE_BINARY_RHS:
2807 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2808 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
2809 case GIMPLE_TERNARY_RHS:
2810 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2811 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt))
2812 || is_gimple_min_invariant (gimple_assign_rhs3 (stmt)));
2813 case GIMPLE_SINGLE_RHS:
2814 /* Constants inside reference ops are rarely interesting, but
2815 it can take a lot of looking to find them. */
2816 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2823 /* Replace SSA_NAMES in expr with their value numbers, and return the
2825 This is performed in place. */
2828 valueize_expr (tree expr)
2830 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2833 TREE_OPERAND (expr, 1) = vn_valueize (TREE_OPERAND (expr, 1));
2836 TREE_OPERAND (expr, 0) = vn_valueize (TREE_OPERAND (expr, 0));
2843 /* Simplify the binary expression RHS, and return the result if
2847 simplify_binary_expression (gimple stmt)
2849 tree result = NULL_TREE;
2850 tree op0 = gimple_assign_rhs1 (stmt);
2851 tree op1 = gimple_assign_rhs2 (stmt);
2852 enum tree_code code = gimple_assign_rhs_code (stmt);
2854 /* This will not catch every single case we could combine, but will
2855 catch those with constants. The goal here is to simultaneously
2856 combine constants between expressions, but avoid infinite
2857 expansion of expressions during simplification. */
2858 if (TREE_CODE (op0) == SSA_NAME)
2860 if (VN_INFO (op0)->has_constants
2861 || TREE_CODE_CLASS (code) == tcc_comparison
2862 || code == COMPLEX_EXPR)
2863 op0 = valueize_expr (vn_get_expr_for (op0));
2865 op0 = vn_valueize (op0);
2868 if (TREE_CODE (op1) == SSA_NAME)
2870 if (VN_INFO (op1)->has_constants
2871 || code == COMPLEX_EXPR)
2872 op1 = valueize_expr (vn_get_expr_for (op1));
2874 op1 = vn_valueize (op1);
2877 /* Pointer plus constant can be represented as invariant address.
2878 Do so to allow further propatation, see also tree forwprop. */
2879 if (code == POINTER_PLUS_EXPR
2880 && host_integerp (op1, 1)
2881 && TREE_CODE (op0) == ADDR_EXPR
2882 && is_gimple_min_invariant (op0))
2883 return build_invariant_address (TREE_TYPE (op0),
2884 TREE_OPERAND (op0, 0),
2885 TREE_INT_CST_LOW (op1));
2887 /* Avoid folding if nothing changed. */
2888 if (op0 == gimple_assign_rhs1 (stmt)
2889 && op1 == gimple_assign_rhs2 (stmt))
2892 fold_defer_overflow_warnings ();
2894 result = fold_binary (code, gimple_expr_type (stmt), op0, op1);
2896 STRIP_USELESS_TYPE_CONVERSION (result);
2898 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2901 /* Make sure result is not a complex expression consisting
2902 of operators of operators (IE (a + b) + (a + c))
2903 Otherwise, we will end up with unbounded expressions if
2904 fold does anything at all. */
2905 if (result && valid_gimple_rhs_p (result))
2911 /* Simplify the unary expression RHS, and return the result if
2915 simplify_unary_expression (gimple stmt)
2917 tree result = NULL_TREE;
2918 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2919 enum tree_code code = gimple_assign_rhs_code (stmt);
2921 /* We handle some tcc_reference codes here that are all
2922 GIMPLE_ASSIGN_SINGLE codes. */
2923 if (code == REALPART_EXPR
2924 || code == IMAGPART_EXPR
2925 || code == VIEW_CONVERT_EXPR)
2926 op0 = TREE_OPERAND (op0, 0);
2928 if (TREE_CODE (op0) != SSA_NAME)
2932 if (VN_INFO (op0)->has_constants)
2933 op0 = valueize_expr (vn_get_expr_for (op0));
2934 else if (CONVERT_EXPR_CODE_P (code)
2935 || code == REALPART_EXPR
2936 || code == IMAGPART_EXPR
2937 || code == VIEW_CONVERT_EXPR)
2939 /* We want to do tree-combining on conversion-like expressions.
2940 Make sure we feed only SSA_NAMEs or constants to fold though. */
2941 tree tem = valueize_expr (vn_get_expr_for (op0));
2942 if (UNARY_CLASS_P (tem)
2943 || BINARY_CLASS_P (tem)
2944 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2945 || TREE_CODE (tem) == SSA_NAME
2946 || is_gimple_min_invariant (tem))
2950 /* Avoid folding if nothing changed, but remember the expression. */
2951 if (op0 == orig_op0)
2954 result = fold_unary_ignore_overflow (code, gimple_expr_type (stmt), op0);
2957 STRIP_USELESS_TYPE_CONVERSION (result);
2958 if (valid_gimple_rhs_p (result))
2965 /* Try to simplify RHS using equivalences and constant folding. */
2968 try_to_simplify (gimple stmt)
2972 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2973 in this case, there is no point in doing extra work. */
2974 if (gimple_assign_copy_p (stmt)
2975 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2978 /* First try constant folding based on our current lattice. */
2979 tem = gimple_fold_stmt_to_constant (stmt, vn_valueize);
2983 /* If that didn't work try combining multiple statements. */
2984 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2987 /* Fallthrough for some codes that can operate on registers. */
2988 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2989 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2990 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2992 /* We could do a little more with unary ops, if they expand
2993 into binary ops, but it's debatable whether it is worth it. */
2995 return simplify_unary_expression (stmt);
2997 case tcc_comparison:
2999 return simplify_binary_expression (stmt);
3008 /* Visit and value number USE, return true if the value number
3012 visit_use (tree use)
3014 bool changed = false;
3015 gimple stmt = SSA_NAME_DEF_STMT (use);
3017 VN_INFO (use)->use_processed = true;
3019 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
3020 if (dump_file && (dump_flags & TDF_DETAILS)
3021 && !SSA_NAME_IS_DEFAULT_DEF (use))
3023 fprintf (dump_file, "Value numbering ");
3024 print_generic_expr (dump_file, use, 0);
3025 fprintf (dump_file, " stmt = ");
3026 print_gimple_stmt (dump_file, stmt, 0, 0);
3029 /* Handle uninitialized uses. */
3030 if (SSA_NAME_IS_DEFAULT_DEF (use))
3031 changed = set_ssa_val_to (use, use);
3034 if (gimple_code (stmt) == GIMPLE_PHI)
3035 changed = visit_phi (stmt);
3036 else if (!gimple_has_lhs (stmt)
3037 || gimple_has_volatile_ops (stmt)
3038 || stmt_could_throw_p (stmt))
3039 changed = defs_to_varying (stmt);
3040 else if (is_gimple_assign (stmt))
3042 enum tree_code code = gimple_assign_rhs_code (stmt);
3043 tree lhs = gimple_assign_lhs (stmt);
3044 tree rhs1 = gimple_assign_rhs1 (stmt);
3047 /* Shortcut for copies. Simplifying copies is pointless,
3048 since we copy the expression and value they represent. */
3049 if (code == SSA_NAME
3050 && TREE_CODE (lhs) == SSA_NAME)
3052 changed = visit_copy (lhs, rhs1);
3055 simplified = try_to_simplify (stmt);
3058 if (dump_file && (dump_flags & TDF_DETAILS))
3060 fprintf (dump_file, "RHS ");
3061 print_gimple_expr (dump_file, stmt, 0, 0);
3062 fprintf (dump_file, " simplified to ");
3063 print_generic_expr (dump_file, simplified, 0);
3064 if (TREE_CODE (lhs) == SSA_NAME)
3065 fprintf (dump_file, " has constants %d\n",
3066 expr_has_constants (simplified));
3068 fprintf (dump_file, "\n");
3071 /* Setting value numbers to constants will occasionally
3072 screw up phi congruence because constants are not
3073 uniquely associated with a single ssa name that can be
3076 && is_gimple_min_invariant (simplified)
3077 && TREE_CODE (lhs) == SSA_NAME)
3079 VN_INFO (lhs)->expr = simplified;
3080 VN_INFO (lhs)->has_constants = true;
3081 changed = set_ssa_val_to (lhs, simplified);
3085 && TREE_CODE (simplified) == SSA_NAME
3086 && TREE_CODE (lhs) == SSA_NAME)
3088 changed = visit_copy (lhs, simplified);
3091 else if (simplified)
3093 if (TREE_CODE (lhs) == SSA_NAME)
3095 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
3096 /* We have to unshare the expression or else
3097 valuizing may change the IL stream. */
3098 VN_INFO (lhs)->expr = unshare_expr (simplified);
3101 else if (stmt_has_constants (stmt)
3102 && TREE_CODE (lhs) == SSA_NAME)
3103 VN_INFO (lhs)->has_constants = true;
3104 else if (TREE_CODE (lhs) == SSA_NAME)
3106 /* We reset expr and constantness here because we may
3107 have been value numbering optimistically, and
3108 iterating. They may become non-constant in this case,
3109 even if they were optimistically constant. */
3111 VN_INFO (lhs)->has_constants = false;
3112 VN_INFO (lhs)->expr = NULL_TREE;
3115 if ((TREE_CODE (lhs) == SSA_NAME
3116 /* We can substitute SSA_NAMEs that are live over
3117 abnormal edges with their constant value. */
3118 && !(gimple_assign_copy_p (stmt)
3119 && is_gimple_min_invariant (rhs1))
3121 && is_gimple_min_invariant (simplified))
3122 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3123 /* Stores or copies from SSA_NAMEs that are live over
3124 abnormal edges are a problem. */
3125 || (code == SSA_NAME
3126 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
3127 changed = defs_to_varying (stmt);
3128 else if (REFERENCE_CLASS_P (lhs)
3130 changed = visit_reference_op_store (lhs, rhs1, stmt);
3131 else if (TREE_CODE (lhs) == SSA_NAME)
3133 if ((gimple_assign_copy_p (stmt)
3134 && is_gimple_min_invariant (rhs1))
3136 && is_gimple_min_invariant (simplified)))
3138 VN_INFO (lhs)->has_constants = true;
3140 changed = set_ssa_val_to (lhs, simplified);
3142 changed = set_ssa_val_to (lhs, rhs1);
3146 switch (get_gimple_rhs_class (code))
3148 case GIMPLE_UNARY_RHS:
3149 case GIMPLE_BINARY_RHS:
3150 case GIMPLE_TERNARY_RHS:
3151 changed = visit_nary_op (lhs, stmt);
3153 case GIMPLE_SINGLE_RHS:
3154 switch (TREE_CODE_CLASS (code))
3157 /* VOP-less references can go through unary case. */
3158 if ((code == REALPART_EXPR
3159 || code == IMAGPART_EXPR
3160 || code == VIEW_CONVERT_EXPR)
3161 && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
3163 changed = visit_nary_op (lhs, stmt);
3167 case tcc_declaration:
3168 changed = visit_reference_op_load (lhs, rhs1, stmt);
3171 if (code == ADDR_EXPR)
3173 changed = visit_nary_op (lhs, stmt);
3176 else if (code == CONSTRUCTOR)
3178 changed = visit_nary_op (lhs, stmt);
3181 changed = defs_to_varying (stmt);
3185 changed = defs_to_varying (stmt);
3191 changed = defs_to_varying (stmt);
3193 else if (is_gimple_call (stmt))
3195 tree lhs = gimple_call_lhs (stmt);
3197 /* ??? We could try to simplify calls. */
3199 if (stmt_has_constants (stmt)
3200 && TREE_CODE (lhs) == SSA_NAME)
3201 VN_INFO (lhs)->has_constants = true;
3202 else if (TREE_CODE (lhs) == SSA_NAME)
3204 /* We reset expr and constantness here because we may
3205 have been value numbering optimistically, and
3206 iterating. They may become non-constant in this case,
3207 even if they were optimistically constant. */
3208 VN_INFO (lhs)->has_constants = false;
3209 VN_INFO (lhs)->expr = NULL_TREE;
3212 if (TREE_CODE (lhs) == SSA_NAME
3213 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3214 changed = defs_to_varying (stmt);
3215 /* ??? We should handle stores from calls. */
3216 else if (TREE_CODE (lhs) == SSA_NAME)
3218 if (!gimple_call_internal_p (stmt)
3219 && gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
3220 changed = visit_reference_op_call (lhs, stmt);
3222 changed = defs_to_varying (stmt);
3225 changed = defs_to_varying (stmt);
3232 /* Compare two operands by reverse postorder index */
3235 compare_ops (const void *pa, const void *pb)
3237 const tree opa = *((const tree *)pa);
3238 const tree opb = *((const tree *)pb);
3239 gimple opstmta = SSA_NAME_DEF_STMT (opa);
3240 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3244 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3245 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3246 else if (gimple_nop_p (opstmta))
3248 else if (gimple_nop_p (opstmtb))
3251 bba = gimple_bb (opstmta);
3252 bbb = gimple_bb (opstmtb);
3255 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3263 if (gimple_code (opstmta) == GIMPLE_PHI
3264 && gimple_code (opstmtb) == GIMPLE_PHI)
3265 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3266 else if (gimple_code (opstmta) == GIMPLE_PHI)
3268 else if (gimple_code (opstmtb) == GIMPLE_PHI)
3270 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3271 return gimple_uid (opstmta) - gimple_uid (opstmtb);
3273 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3275 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3278 /* Sort an array containing members of a strongly connected component
3279 SCC so that the members are ordered by RPO number.
3280 This means that when the sort is complete, iterating through the
3281 array will give you the members in RPO order. */
3284 sort_scc (VEC (tree, heap) *scc)
3286 VEC_qsort (tree, scc, compare_ops);
3289 /* Insert the no longer used nary ONARY to the hash INFO. */
3292 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3294 size_t size = sizeof_vn_nary_op (onary->length);
3295 vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
3296 &info->nary_obstack);
3297 memcpy (nary, onary, size);
3298 vn_nary_op_insert_into (nary, info->nary, false);
3301 /* Insert the no longer used phi OPHI to the hash INFO. */
3304 copy_phi (vn_phi_t ophi, vn_tables_t info)
3306 vn_phi_t phi = (vn_phi_t) pool_alloc (info->phis_pool);
3308 memcpy (phi, ophi, sizeof (*phi));
3309 ophi->phiargs = NULL;
3310 slot = htab_find_slot_with_hash (info->phis, phi, phi->hashcode, INSERT);
3311 gcc_assert (!*slot);
3315 /* Insert the no longer used reference OREF to the hash INFO. */
3318 copy_reference (vn_reference_t oref, vn_tables_t info)
3322 ref = (vn_reference_t) pool_alloc (info->references_pool);
3323 memcpy (ref, oref, sizeof (*ref));
3324 oref->operands = NULL;
3325 slot = htab_find_slot_with_hash (info->references, ref, ref->hashcode,
3328 free_reference (*slot);
3332 /* Process a strongly connected component in the SSA graph. */
3335 process_scc (VEC (tree, heap) *scc)
3339 unsigned int iterations = 0;
3340 bool changed = true;
3346 /* If the SCC has a single member, just visit it. */
3347 if (VEC_length (tree, scc) == 1)
3349 tree use = VEC_index (tree, scc, 0);
3350 if (VN_INFO (use)->use_processed)
3352 /* We need to make sure it doesn't form a cycle itself, which can
3353 happen for self-referential PHI nodes. In that case we would
3354 end up inserting an expression with VN_TOP operands into the
3355 valid table which makes us derive bogus equivalences later.
3356 The cheapest way to check this is to assume it for all PHI nodes. */
3357 if (gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_PHI)
3358 /* Fallthru to iteration. */ ;
3366 /* Iterate over the SCC with the optimistic table until it stops
3368 current_info = optimistic_info;
3373 if (dump_file && (dump_flags & TDF_DETAILS))
3374 fprintf (dump_file, "Starting iteration %d\n", iterations);
3375 /* As we are value-numbering optimistically we have to
3376 clear the expression tables and the simplified expressions
3377 in each iteration until we converge. */
3378 htab_empty (optimistic_info->nary);
3379 htab_empty (optimistic_info->phis);
3380 htab_empty (optimistic_info->references);
3381 obstack_free (&optimistic_info->nary_obstack, NULL);
3382 gcc_obstack_init (&optimistic_info->nary_obstack);
3383 empty_alloc_pool (optimistic_info->phis_pool);
3384 empty_alloc_pool (optimistic_info->references_pool);
3385 FOR_EACH_VEC_ELT (tree, scc, i, var)
3386 VN_INFO (var)->expr = NULL_TREE;
3387 FOR_EACH_VEC_ELT (tree, scc, i, var)
3388 changed |= visit_use (var);
3391 statistics_histogram_event (cfun, "SCC iterations", iterations);
3393 /* Finally, copy the contents of the no longer used optimistic
3394 table to the valid table. */
3395 FOR_EACH_HTAB_ELEMENT (optimistic_info->nary, nary, vn_nary_op_t, hi)
3396 copy_nary (nary, valid_info);
3397 FOR_EACH_HTAB_ELEMENT (optimistic_info->phis, phi, vn_phi_t, hi)
3398 copy_phi (phi, valid_info);
3399 FOR_EACH_HTAB_ELEMENT (optimistic_info->references, ref, vn_reference_t, hi)
3400 copy_reference (ref, valid_info);
3402 current_info = valid_info;
3405 DEF_VEC_O(ssa_op_iter);
3406 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
3408 /* Pop the components of the found SCC for NAME off the SCC stack
3409 and process them. Returns true if all went well, false if
3410 we run into resource limits. */
3413 extract_and_process_scc_for_name (tree name)
3415 VEC (tree, heap) *scc = NULL;
3418 /* Found an SCC, pop the components off the SCC stack and
3422 x = VEC_pop (tree, sccstack);
3424 VN_INFO (x)->on_sccstack = false;
3425 VEC_safe_push (tree, heap, scc, x);
3426 } while (x != name);
3428 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3429 if (VEC_length (tree, scc)
3430 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
3433 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
3434 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
3435 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
3439 if (VEC_length (tree, scc) > 1)
3442 if (dump_file && (dump_flags & TDF_DETAILS))
3443 print_scc (dump_file, scc);
3447 VEC_free (tree, heap, scc);
3452 /* Depth first search on NAME to discover and process SCC's in the SSA
3454 Execution of this algorithm relies on the fact that the SCC's are
3455 popped off the stack in topological order.
3456 Returns true if successful, false if we stopped processing SCC's due
3457 to resource constraints. */
3462 VEC(ssa_op_iter, heap) *itervec = NULL;
3463 VEC(tree, heap) *namevec = NULL;
3464 use_operand_p usep = NULL;
3471 VN_INFO (name)->dfsnum = next_dfs_num++;
3472 VN_INFO (name)->visited = true;
3473 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
3475 VEC_safe_push (tree, heap, sccstack, name);
3476 VN_INFO (name)->on_sccstack = true;
3477 defstmt = SSA_NAME_DEF_STMT (name);
3479 /* Recursively DFS on our operands, looking for SCC's. */
3480 if (!gimple_nop_p (defstmt))
3482 /* Push a new iterator. */
3483 if (gimple_code (defstmt) == GIMPLE_PHI)
3484 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
3486 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
3489 clear_and_done_ssa_iter (&iter);
3493 /* If we are done processing uses of a name, go up the stack
3494 of iterators and process SCCs as we found them. */
3495 if (op_iter_done (&iter))
3497 /* See if we found an SCC. */
3498 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
3499 if (!extract_and_process_scc_for_name (name))
3501 VEC_free (tree, heap, namevec);
3502 VEC_free (ssa_op_iter, heap, itervec);
3506 /* Check if we are done. */
3507 if (VEC_empty (tree, namevec))
3509 VEC_free (tree, heap, namevec);
3510 VEC_free (ssa_op_iter, heap, itervec);
3514 /* Restore the last use walker and continue walking there. */
3516 name = VEC_pop (tree, namevec);
3517 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
3518 sizeof (ssa_op_iter));
3519 VEC_pop (ssa_op_iter, itervec);
3520 goto continue_walking;
3523 use = USE_FROM_PTR (usep);
3525 /* Since we handle phi nodes, we will sometimes get
3526 invariants in the use expression. */
3527 if (TREE_CODE (use) == SSA_NAME)
3529 if (! (VN_INFO (use)->visited))
3531 /* Recurse by pushing the current use walking state on
3532 the stack and starting over. */
3533 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
3534 VEC_safe_push(tree, heap, namevec, name);
3539 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
3540 VN_INFO (use)->low);
3542 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
3543 && VN_INFO (use)->on_sccstack)
3545 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
3546 VN_INFO (name)->low);
3550 usep = op_iter_next_use (&iter);
3554 /* Allocate a value number table. */
3557 allocate_vn_table (vn_tables_t table)
3559 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
3560 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
3561 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
3564 gcc_obstack_init (&table->nary_obstack);
3565 table->phis_pool = create_alloc_pool ("VN phis",
3566 sizeof (struct vn_phi_s),
3568 table->references_pool = create_alloc_pool ("VN references",
3569 sizeof (struct vn_reference_s),
3573 /* Free a value number table. */
3576 free_vn_table (vn_tables_t table)
3578 htab_delete (table->phis);
3579 htab_delete (table->nary);
3580 htab_delete (table->references);
3581 obstack_free (&table->nary_obstack, NULL);
3582 free_alloc_pool (table->phis_pool);
3583 free_alloc_pool (table->references_pool);
3591 int *rpo_numbers_temp;
3593 calculate_dominance_info (CDI_DOMINATORS);
3595 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
3598 constant_value_ids = BITMAP_ALLOC (NULL);
3603 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
3604 /* VEC_alloc doesn't actually grow it to the right size, it just
3605 preallocates the space to do so. */
3606 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
3607 gcc_obstack_init (&vn_ssa_aux_obstack);
3609 shared_lookup_phiargs = NULL;
3610 shared_lookup_references = NULL;
3611 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3612 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3613 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
3615 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3616 the i'th block in RPO order is bb. We want to map bb's to RPO
3617 numbers, so we need to rearrange this array. */
3618 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
3619 rpo_numbers[rpo_numbers_temp[j]] = j;
3621 XDELETE (rpo_numbers_temp);
3623 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
3625 /* Create the VN_INFO structures, and initialize value numbers to
3627 for (i = 0; i < num_ssa_names; i++)
3629 tree name = ssa_name (i);
3632 VN_INFO_GET (name)->valnum = VN_TOP;
3633 VN_INFO (name)->expr = NULL_TREE;
3634 VN_INFO (name)->value_id = 0;
3638 renumber_gimple_stmt_uids ();
3640 /* Create the valid and optimistic value numbering tables. */
3641 valid_info = XCNEW (struct vn_tables_s);
3642 allocate_vn_table (valid_info);
3643 optimistic_info = XCNEW (struct vn_tables_s);
3644 allocate_vn_table (optimistic_info);
3652 htab_delete (constant_to_value_id);
3653 BITMAP_FREE (constant_value_ids);
3654 VEC_free (tree, heap, shared_lookup_phiargs);
3655 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
3656 XDELETEVEC (rpo_numbers);
3658 for (i = 0; i < num_ssa_names; i++)
3660 tree name = ssa_name (i);
3662 && VN_INFO (name)->needs_insertion)
3663 release_ssa_name (name);
3665 obstack_free (&vn_ssa_aux_obstack, NULL);
3666 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
3668 VEC_free (tree, heap, sccstack);
3669 free_vn_table (valid_info);
3670 XDELETE (valid_info);
3671 free_vn_table (optimistic_info);
3672 XDELETE (optimistic_info);
3675 /* Set *ID if we computed something useful in RESULT. */
3678 set_value_id_for_result (tree result, unsigned int *id)
3682 if (TREE_CODE (result) == SSA_NAME)
3683 *id = VN_INFO (result)->value_id;
3684 else if (is_gimple_min_invariant (result))
3685 *id = get_or_alloc_constant_value_id (result);
3689 /* Set the value ids in the valid hash tables. */
3692 set_hashtable_value_ids (void)
3699 /* Now set the value ids of the things we had put in the hash
3702 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
3703 vno, vn_nary_op_t, hi)
3704 set_value_id_for_result (vno->result, &vno->value_id);
3706 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
3708 set_value_id_for_result (vp->result, &vp->value_id);
3710 FOR_EACH_HTAB_ELEMENT (valid_info->references,
3711 vr, vn_reference_t, hi)
3712 set_value_id_for_result (vr->result, &vr->value_id);
3715 /* Do SCCVN. Returns true if it finished, false if we bailed out
3716 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
3717 how we use the alias oracle walking during the VN process. */
3720 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
3724 bool changed = true;
3726 default_vn_walk_kind = default_vn_walk_kind_;
3729 current_info = valid_info;
3731 for (param = DECL_ARGUMENTS (current_function_decl);
3733 param = DECL_CHAIN (param))
3735 if (gimple_default_def (cfun, param) != NULL)
3737 tree def = gimple_default_def (cfun, param);
3738 VN_INFO (def)->valnum = def;
3742 for (i = 1; i < num_ssa_names; ++i)
3744 tree name = ssa_name (i);
3746 && VN_INFO (name)->visited == false
3747 && !has_zero_uses (name))
3755 /* Initialize the value ids. */
3757 for (i = 1; i < num_ssa_names; ++i)
3759 tree name = ssa_name (i);
3763 info = VN_INFO (name);
3764 if (info->valnum == name
3765 || info->valnum == VN_TOP)
3766 info->value_id = get_next_value_id ();
3767 else if (is_gimple_min_invariant (info->valnum))
3768 info->value_id = get_or_alloc_constant_value_id (info->valnum);
3771 /* Propagate until they stop changing. */
3775 for (i = 1; i < num_ssa_names; ++i)
3777 tree name = ssa_name (i);
3781 info = VN_INFO (name);
3782 if (TREE_CODE (info->valnum) == SSA_NAME
3783 && info->valnum != name
3784 && info->value_id != VN_INFO (info->valnum)->value_id)
3787 info->value_id = VN_INFO (info->valnum)->value_id;
3792 set_hashtable_value_ids ();
3794 if (dump_file && (dump_flags & TDF_DETAILS))
3796 fprintf (dump_file, "Value numbers:\n");
3797 for (i = 0; i < num_ssa_names; i++)
3799 tree name = ssa_name (i);
3801 && VN_INFO (name)->visited
3802 && SSA_VAL (name) != name)
3804 print_generic_expr (dump_file, name, 0);
3805 fprintf (dump_file, " = ");
3806 print_generic_expr (dump_file, SSA_VAL (name), 0);
3807 fprintf (dump_file, "\n");
3815 /* Return the maximum value id we have ever seen. */
3818 get_max_value_id (void)
3820 return next_value_id;
3823 /* Return the next unique value id. */
3826 get_next_value_id (void)
3828 return next_value_id++;
3832 /* Compare two expressions E1 and E2 and return true if they are equal. */
3835 expressions_equal_p (tree e1, tree e2)
3837 /* The obvious case. */
3841 /* If only one of them is null, they cannot be equal. */
3845 /* Now perform the actual comparison. */
3846 if (TREE_CODE (e1) == TREE_CODE (e2)
3847 && operand_equal_p (e1, e2, OEP_PURE_SAME))
3854 /* Return true if the nary operation NARY may trap. This is a copy
3855 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
3858 vn_nary_may_trap (vn_nary_op_t nary)
3861 tree rhs2 = NULL_TREE;
3862 bool honor_nans = false;
3863 bool honor_snans = false;
3864 bool fp_operation = false;
3865 bool honor_trapv = false;
3869 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
3870 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
3871 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
3874 fp_operation = FLOAT_TYPE_P (type);
3877 honor_nans = flag_trapping_math && !flag_finite_math_only;
3878 honor_snans = flag_signaling_nans != 0;
3880 else if (INTEGRAL_TYPE_P (type)
3881 && TYPE_OVERFLOW_TRAPS (type))
3884 if (nary->length >= 2)
3886 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
3888 honor_nans, honor_snans, rhs2,
3894 for (i = 0; i < nary->length; ++i)
3895 if (tree_could_trap_p (nary->op[i]))