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 /* Valueize NAME if it is an SSA name, otherwise just return it. */
2826 vn_valueize (tree name)
2828 if (TREE_CODE (name) == SSA_NAME)
2830 tree tem = SSA_VAL (name);
2831 return tem == VN_TOP ? name : tem;
2836 /* Replace SSA_NAMES in expr with their value numbers, and return the
2838 This is performed in place. */
2841 valueize_expr (tree expr)
2843 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2846 TREE_OPERAND (expr, 1) = vn_valueize (TREE_OPERAND (expr, 1));
2849 TREE_OPERAND (expr, 0) = vn_valueize (TREE_OPERAND (expr, 0));
2856 /* Simplify the binary expression RHS, and return the result if
2860 simplify_binary_expression (gimple stmt)
2862 tree result = NULL_TREE;
2863 tree op0 = gimple_assign_rhs1 (stmt);
2864 tree op1 = gimple_assign_rhs2 (stmt);
2865 enum tree_code code = gimple_assign_rhs_code (stmt);
2867 /* This will not catch every single case we could combine, but will
2868 catch those with constants. The goal here is to simultaneously
2869 combine constants between expressions, but avoid infinite
2870 expansion of expressions during simplification. */
2871 if (TREE_CODE (op0) == SSA_NAME)
2873 if (VN_INFO (op0)->has_constants
2874 || TREE_CODE_CLASS (code) == tcc_comparison
2875 || code == COMPLEX_EXPR)
2876 op0 = valueize_expr (vn_get_expr_for (op0));
2878 op0 = vn_valueize (op0);
2881 if (TREE_CODE (op1) == SSA_NAME)
2883 if (VN_INFO (op1)->has_constants
2884 || code == COMPLEX_EXPR)
2885 op1 = valueize_expr (vn_get_expr_for (op1));
2887 op1 = vn_valueize (op1);
2890 /* Pointer plus constant can be represented as invariant address.
2891 Do so to allow further propatation, see also tree forwprop. */
2892 if (code == POINTER_PLUS_EXPR
2893 && host_integerp (op1, 1)
2894 && TREE_CODE (op0) == ADDR_EXPR
2895 && is_gimple_min_invariant (op0))
2896 return build_invariant_address (TREE_TYPE (op0),
2897 TREE_OPERAND (op0, 0),
2898 TREE_INT_CST_LOW (op1));
2900 /* Avoid folding if nothing changed. */
2901 if (op0 == gimple_assign_rhs1 (stmt)
2902 && op1 == gimple_assign_rhs2 (stmt))
2905 fold_defer_overflow_warnings ();
2907 result = fold_binary (code, gimple_expr_type (stmt), op0, op1);
2909 STRIP_USELESS_TYPE_CONVERSION (result);
2911 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2914 /* Make sure result is not a complex expression consisting
2915 of operators of operators (IE (a + b) + (a + c))
2916 Otherwise, we will end up with unbounded expressions if
2917 fold does anything at all. */
2918 if (result && valid_gimple_rhs_p (result))
2924 /* Simplify the unary expression RHS, and return the result if
2928 simplify_unary_expression (gimple stmt)
2930 tree result = NULL_TREE;
2931 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2932 enum tree_code code = gimple_assign_rhs_code (stmt);
2934 /* We handle some tcc_reference codes here that are all
2935 GIMPLE_ASSIGN_SINGLE codes. */
2936 if (code == REALPART_EXPR
2937 || code == IMAGPART_EXPR
2938 || code == VIEW_CONVERT_EXPR)
2939 op0 = TREE_OPERAND (op0, 0);
2941 if (TREE_CODE (op0) != SSA_NAME)
2945 if (VN_INFO (op0)->has_constants)
2946 op0 = valueize_expr (vn_get_expr_for (op0));
2947 else if (CONVERT_EXPR_CODE_P (code)
2948 || code == REALPART_EXPR
2949 || code == IMAGPART_EXPR
2950 || code == VIEW_CONVERT_EXPR)
2952 /* We want to do tree-combining on conversion-like expressions.
2953 Make sure we feed only SSA_NAMEs or constants to fold though. */
2954 tree tem = valueize_expr (vn_get_expr_for (op0));
2955 if (UNARY_CLASS_P (tem)
2956 || BINARY_CLASS_P (tem)
2957 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2958 || TREE_CODE (tem) == SSA_NAME
2959 || is_gimple_min_invariant (tem))
2963 /* Avoid folding if nothing changed, but remember the expression. */
2964 if (op0 == orig_op0)
2967 result = fold_unary_ignore_overflow (code, gimple_expr_type (stmt), op0);
2970 STRIP_USELESS_TYPE_CONVERSION (result);
2971 if (valid_gimple_rhs_p (result))
2978 /* Try to simplify RHS using equivalences and constant folding. */
2981 try_to_simplify (gimple stmt)
2985 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2986 in this case, there is no point in doing extra work. */
2987 if (gimple_assign_copy_p (stmt)
2988 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2991 /* First try constant folding based on our current lattice. */
2992 tem = gimple_fold_stmt_to_constant (stmt, vn_valueize);
2996 /* If that didn't work try combining multiple statements. */
2997 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
3000 /* Fallthrough for some codes that can operate on registers. */
3001 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
3002 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
3003 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
3005 /* We could do a little more with unary ops, if they expand
3006 into binary ops, but it's debatable whether it is worth it. */
3008 return simplify_unary_expression (stmt);
3010 case tcc_comparison:
3012 return simplify_binary_expression (stmt);
3021 /* Visit and value number USE, return true if the value number
3025 visit_use (tree use)
3027 bool changed = false;
3028 gimple stmt = SSA_NAME_DEF_STMT (use);
3030 VN_INFO (use)->use_processed = true;
3032 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
3033 if (dump_file && (dump_flags & TDF_DETAILS)
3034 && !SSA_NAME_IS_DEFAULT_DEF (use))
3036 fprintf (dump_file, "Value numbering ");
3037 print_generic_expr (dump_file, use, 0);
3038 fprintf (dump_file, " stmt = ");
3039 print_gimple_stmt (dump_file, stmt, 0, 0);
3042 /* Handle uninitialized uses. */
3043 if (SSA_NAME_IS_DEFAULT_DEF (use))
3044 changed = set_ssa_val_to (use, use);
3047 if (gimple_code (stmt) == GIMPLE_PHI)
3048 changed = visit_phi (stmt);
3049 else if (!gimple_has_lhs (stmt)
3050 || gimple_has_volatile_ops (stmt)
3051 || stmt_could_throw_p (stmt))
3052 changed = defs_to_varying (stmt);
3053 else if (is_gimple_assign (stmt))
3055 enum tree_code code = gimple_assign_rhs_code (stmt);
3056 tree lhs = gimple_assign_lhs (stmt);
3057 tree rhs1 = gimple_assign_rhs1 (stmt);
3060 /* Shortcut for copies. Simplifying copies is pointless,
3061 since we copy the expression and value they represent. */
3062 if (code == SSA_NAME
3063 && TREE_CODE (lhs) == SSA_NAME)
3065 changed = visit_copy (lhs, rhs1);
3068 simplified = try_to_simplify (stmt);
3071 if (dump_file && (dump_flags & TDF_DETAILS))
3073 fprintf (dump_file, "RHS ");
3074 print_gimple_expr (dump_file, stmt, 0, 0);
3075 fprintf (dump_file, " simplified to ");
3076 print_generic_expr (dump_file, simplified, 0);
3077 if (TREE_CODE (lhs) == SSA_NAME)
3078 fprintf (dump_file, " has constants %d\n",
3079 expr_has_constants (simplified));
3081 fprintf (dump_file, "\n");
3084 /* Setting value numbers to constants will occasionally
3085 screw up phi congruence because constants are not
3086 uniquely associated with a single ssa name that can be
3089 && is_gimple_min_invariant (simplified)
3090 && TREE_CODE (lhs) == SSA_NAME)
3092 VN_INFO (lhs)->expr = simplified;
3093 VN_INFO (lhs)->has_constants = true;
3094 changed = set_ssa_val_to (lhs, simplified);
3098 && TREE_CODE (simplified) == SSA_NAME
3099 && TREE_CODE (lhs) == SSA_NAME)
3101 changed = visit_copy (lhs, simplified);
3104 else if (simplified)
3106 if (TREE_CODE (lhs) == SSA_NAME)
3108 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
3109 /* We have to unshare the expression or else
3110 valuizing may change the IL stream. */
3111 VN_INFO (lhs)->expr = unshare_expr (simplified);
3114 else if (stmt_has_constants (stmt)
3115 && TREE_CODE (lhs) == SSA_NAME)
3116 VN_INFO (lhs)->has_constants = true;
3117 else if (TREE_CODE (lhs) == SSA_NAME)
3119 /* We reset expr and constantness here because we may
3120 have been value numbering optimistically, and
3121 iterating. They may become non-constant in this case,
3122 even if they were optimistically constant. */
3124 VN_INFO (lhs)->has_constants = false;
3125 VN_INFO (lhs)->expr = NULL_TREE;
3128 if ((TREE_CODE (lhs) == SSA_NAME
3129 /* We can substitute SSA_NAMEs that are live over
3130 abnormal edges with their constant value. */
3131 && !(gimple_assign_copy_p (stmt)
3132 && is_gimple_min_invariant (rhs1))
3134 && is_gimple_min_invariant (simplified))
3135 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3136 /* Stores or copies from SSA_NAMEs that are live over
3137 abnormal edges are a problem. */
3138 || (code == SSA_NAME
3139 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
3140 changed = defs_to_varying (stmt);
3141 else if (REFERENCE_CLASS_P (lhs)
3143 changed = visit_reference_op_store (lhs, rhs1, stmt);
3144 else if (TREE_CODE (lhs) == SSA_NAME)
3146 if ((gimple_assign_copy_p (stmt)
3147 && is_gimple_min_invariant (rhs1))
3149 && is_gimple_min_invariant (simplified)))
3151 VN_INFO (lhs)->has_constants = true;
3153 changed = set_ssa_val_to (lhs, simplified);
3155 changed = set_ssa_val_to (lhs, rhs1);
3159 switch (get_gimple_rhs_class (code))
3161 case GIMPLE_UNARY_RHS:
3162 case GIMPLE_BINARY_RHS:
3163 case GIMPLE_TERNARY_RHS:
3164 changed = visit_nary_op (lhs, stmt);
3166 case GIMPLE_SINGLE_RHS:
3167 switch (TREE_CODE_CLASS (code))
3170 /* VOP-less references can go through unary case. */
3171 if ((code == REALPART_EXPR
3172 || code == IMAGPART_EXPR
3173 || code == VIEW_CONVERT_EXPR)
3174 && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
3176 changed = visit_nary_op (lhs, stmt);
3180 case tcc_declaration:
3181 changed = visit_reference_op_load (lhs, rhs1, stmt);
3184 if (code == ADDR_EXPR)
3186 changed = visit_nary_op (lhs, stmt);
3189 else if (code == CONSTRUCTOR)
3191 changed = visit_nary_op (lhs, stmt);
3194 changed = defs_to_varying (stmt);
3198 changed = defs_to_varying (stmt);
3204 changed = defs_to_varying (stmt);
3206 else if (is_gimple_call (stmt))
3208 tree lhs = gimple_call_lhs (stmt);
3210 /* ??? We could try to simplify calls. */
3212 if (stmt_has_constants (stmt)
3213 && TREE_CODE (lhs) == SSA_NAME)
3214 VN_INFO (lhs)->has_constants = true;
3215 else if (TREE_CODE (lhs) == SSA_NAME)
3217 /* We reset expr and constantness here because we may
3218 have been value numbering optimistically, and
3219 iterating. They may become non-constant in this case,
3220 even if they were optimistically constant. */
3221 VN_INFO (lhs)->has_constants = false;
3222 VN_INFO (lhs)->expr = NULL_TREE;
3225 if (TREE_CODE (lhs) == SSA_NAME
3226 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3227 changed = defs_to_varying (stmt);
3228 /* ??? We should handle stores from calls. */
3229 else if (TREE_CODE (lhs) == SSA_NAME)
3231 if (!gimple_call_internal_p (stmt)
3232 && gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
3233 changed = visit_reference_op_call (lhs, stmt);
3235 changed = defs_to_varying (stmt);
3238 changed = defs_to_varying (stmt);
3245 /* Compare two operands by reverse postorder index */
3248 compare_ops (const void *pa, const void *pb)
3250 const tree opa = *((const tree *)pa);
3251 const tree opb = *((const tree *)pb);
3252 gimple opstmta = SSA_NAME_DEF_STMT (opa);
3253 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3257 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3258 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3259 else if (gimple_nop_p (opstmta))
3261 else if (gimple_nop_p (opstmtb))
3264 bba = gimple_bb (opstmta);
3265 bbb = gimple_bb (opstmtb);
3268 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3276 if (gimple_code (opstmta) == GIMPLE_PHI
3277 && gimple_code (opstmtb) == GIMPLE_PHI)
3278 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3279 else if (gimple_code (opstmta) == GIMPLE_PHI)
3281 else if (gimple_code (opstmtb) == GIMPLE_PHI)
3283 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3284 return gimple_uid (opstmta) - gimple_uid (opstmtb);
3286 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3288 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3291 /* Sort an array containing members of a strongly connected component
3292 SCC so that the members are ordered by RPO number.
3293 This means that when the sort is complete, iterating through the
3294 array will give you the members in RPO order. */
3297 sort_scc (VEC (tree, heap) *scc)
3299 VEC_qsort (tree, scc, compare_ops);
3302 /* Insert the no longer used nary ONARY to the hash INFO. */
3305 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3307 size_t size = sizeof_vn_nary_op (onary->length);
3308 vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
3309 &info->nary_obstack);
3310 memcpy (nary, onary, size);
3311 vn_nary_op_insert_into (nary, info->nary, false);
3314 /* Insert the no longer used phi OPHI to the hash INFO. */
3317 copy_phi (vn_phi_t ophi, vn_tables_t info)
3319 vn_phi_t phi = (vn_phi_t) pool_alloc (info->phis_pool);
3321 memcpy (phi, ophi, sizeof (*phi));
3322 ophi->phiargs = NULL;
3323 slot = htab_find_slot_with_hash (info->phis, phi, phi->hashcode, INSERT);
3324 gcc_assert (!*slot);
3328 /* Insert the no longer used reference OREF to the hash INFO. */
3331 copy_reference (vn_reference_t oref, vn_tables_t info)
3335 ref = (vn_reference_t) pool_alloc (info->references_pool);
3336 memcpy (ref, oref, sizeof (*ref));
3337 oref->operands = NULL;
3338 slot = htab_find_slot_with_hash (info->references, ref, ref->hashcode,
3341 free_reference (*slot);
3345 /* Process a strongly connected component in the SSA graph. */
3348 process_scc (VEC (tree, heap) *scc)
3352 unsigned int iterations = 0;
3353 bool changed = true;
3359 /* If the SCC has a single member, just visit it. */
3360 if (VEC_length (tree, scc) == 1)
3362 tree use = VEC_index (tree, scc, 0);
3363 if (VN_INFO (use)->use_processed)
3365 /* We need to make sure it doesn't form a cycle itself, which can
3366 happen for self-referential PHI nodes. In that case we would
3367 end up inserting an expression with VN_TOP operands into the
3368 valid table which makes us derive bogus equivalences later.
3369 The cheapest way to check this is to assume it for all PHI nodes. */
3370 if (gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_PHI)
3371 /* Fallthru to iteration. */ ;
3379 /* Iterate over the SCC with the optimistic table until it stops
3381 current_info = optimistic_info;
3386 if (dump_file && (dump_flags & TDF_DETAILS))
3387 fprintf (dump_file, "Starting iteration %d\n", iterations);
3388 /* As we are value-numbering optimistically we have to
3389 clear the expression tables and the simplified expressions
3390 in each iteration until we converge. */
3391 htab_empty (optimistic_info->nary);
3392 htab_empty (optimistic_info->phis);
3393 htab_empty (optimistic_info->references);
3394 obstack_free (&optimistic_info->nary_obstack, NULL);
3395 gcc_obstack_init (&optimistic_info->nary_obstack);
3396 empty_alloc_pool (optimistic_info->phis_pool);
3397 empty_alloc_pool (optimistic_info->references_pool);
3398 FOR_EACH_VEC_ELT (tree, scc, i, var)
3399 VN_INFO (var)->expr = NULL_TREE;
3400 FOR_EACH_VEC_ELT (tree, scc, i, var)
3401 changed |= visit_use (var);
3404 statistics_histogram_event (cfun, "SCC iterations", iterations);
3406 /* Finally, copy the contents of the no longer used optimistic
3407 table to the valid table. */
3408 FOR_EACH_HTAB_ELEMENT (optimistic_info->nary, nary, vn_nary_op_t, hi)
3409 copy_nary (nary, valid_info);
3410 FOR_EACH_HTAB_ELEMENT (optimistic_info->phis, phi, vn_phi_t, hi)
3411 copy_phi (phi, valid_info);
3412 FOR_EACH_HTAB_ELEMENT (optimistic_info->references, ref, vn_reference_t, hi)
3413 copy_reference (ref, valid_info);
3415 current_info = valid_info;
3418 DEF_VEC_O(ssa_op_iter);
3419 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
3421 /* Pop the components of the found SCC for NAME off the SCC stack
3422 and process them. Returns true if all went well, false if
3423 we run into resource limits. */
3426 extract_and_process_scc_for_name (tree name)
3428 VEC (tree, heap) *scc = NULL;
3431 /* Found an SCC, pop the components off the SCC stack and
3435 x = VEC_pop (tree, sccstack);
3437 VN_INFO (x)->on_sccstack = false;
3438 VEC_safe_push (tree, heap, scc, x);
3439 } while (x != name);
3441 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3442 if (VEC_length (tree, scc)
3443 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
3446 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
3447 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
3448 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
3452 if (VEC_length (tree, scc) > 1)
3455 if (dump_file && (dump_flags & TDF_DETAILS))
3456 print_scc (dump_file, scc);
3460 VEC_free (tree, heap, scc);
3465 /* Depth first search on NAME to discover and process SCC's in the SSA
3467 Execution of this algorithm relies on the fact that the SCC's are
3468 popped off the stack in topological order.
3469 Returns true if successful, false if we stopped processing SCC's due
3470 to resource constraints. */
3475 VEC(ssa_op_iter, heap) *itervec = NULL;
3476 VEC(tree, heap) *namevec = NULL;
3477 use_operand_p usep = NULL;
3484 VN_INFO (name)->dfsnum = next_dfs_num++;
3485 VN_INFO (name)->visited = true;
3486 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
3488 VEC_safe_push (tree, heap, sccstack, name);
3489 VN_INFO (name)->on_sccstack = true;
3490 defstmt = SSA_NAME_DEF_STMT (name);
3492 /* Recursively DFS on our operands, looking for SCC's. */
3493 if (!gimple_nop_p (defstmt))
3495 /* Push a new iterator. */
3496 if (gimple_code (defstmt) == GIMPLE_PHI)
3497 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
3499 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
3502 clear_and_done_ssa_iter (&iter);
3506 /* If we are done processing uses of a name, go up the stack
3507 of iterators and process SCCs as we found them. */
3508 if (op_iter_done (&iter))
3510 /* See if we found an SCC. */
3511 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
3512 if (!extract_and_process_scc_for_name (name))
3514 VEC_free (tree, heap, namevec);
3515 VEC_free (ssa_op_iter, heap, itervec);
3519 /* Check if we are done. */
3520 if (VEC_empty (tree, namevec))
3522 VEC_free (tree, heap, namevec);
3523 VEC_free (ssa_op_iter, heap, itervec);
3527 /* Restore the last use walker and continue walking there. */
3529 name = VEC_pop (tree, namevec);
3530 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
3531 sizeof (ssa_op_iter));
3532 VEC_pop (ssa_op_iter, itervec);
3533 goto continue_walking;
3536 use = USE_FROM_PTR (usep);
3538 /* Since we handle phi nodes, we will sometimes get
3539 invariants in the use expression. */
3540 if (TREE_CODE (use) == SSA_NAME)
3542 if (! (VN_INFO (use)->visited))
3544 /* Recurse by pushing the current use walking state on
3545 the stack and starting over. */
3546 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
3547 VEC_safe_push(tree, heap, namevec, name);
3552 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
3553 VN_INFO (use)->low);
3555 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
3556 && VN_INFO (use)->on_sccstack)
3558 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
3559 VN_INFO (name)->low);
3563 usep = op_iter_next_use (&iter);
3567 /* Allocate a value number table. */
3570 allocate_vn_table (vn_tables_t table)
3572 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
3573 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
3574 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
3577 gcc_obstack_init (&table->nary_obstack);
3578 table->phis_pool = create_alloc_pool ("VN phis",
3579 sizeof (struct vn_phi_s),
3581 table->references_pool = create_alloc_pool ("VN references",
3582 sizeof (struct vn_reference_s),
3586 /* Free a value number table. */
3589 free_vn_table (vn_tables_t table)
3591 htab_delete (table->phis);
3592 htab_delete (table->nary);
3593 htab_delete (table->references);
3594 obstack_free (&table->nary_obstack, NULL);
3595 free_alloc_pool (table->phis_pool);
3596 free_alloc_pool (table->references_pool);
3604 int *rpo_numbers_temp;
3606 calculate_dominance_info (CDI_DOMINATORS);
3608 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
3611 constant_value_ids = BITMAP_ALLOC (NULL);
3616 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
3617 /* VEC_alloc doesn't actually grow it to the right size, it just
3618 preallocates the space to do so. */
3619 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
3620 gcc_obstack_init (&vn_ssa_aux_obstack);
3622 shared_lookup_phiargs = NULL;
3623 shared_lookup_references = NULL;
3624 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3625 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3626 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
3628 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3629 the i'th block in RPO order is bb. We want to map bb's to RPO
3630 numbers, so we need to rearrange this array. */
3631 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
3632 rpo_numbers[rpo_numbers_temp[j]] = j;
3634 XDELETE (rpo_numbers_temp);
3636 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
3638 /* Create the VN_INFO structures, and initialize value numbers to
3640 for (i = 0; i < num_ssa_names; i++)
3642 tree name = ssa_name (i);
3645 VN_INFO_GET (name)->valnum = VN_TOP;
3646 VN_INFO (name)->expr = NULL_TREE;
3647 VN_INFO (name)->value_id = 0;
3651 renumber_gimple_stmt_uids ();
3653 /* Create the valid and optimistic value numbering tables. */
3654 valid_info = XCNEW (struct vn_tables_s);
3655 allocate_vn_table (valid_info);
3656 optimistic_info = XCNEW (struct vn_tables_s);
3657 allocate_vn_table (optimistic_info);
3665 htab_delete (constant_to_value_id);
3666 BITMAP_FREE (constant_value_ids);
3667 VEC_free (tree, heap, shared_lookup_phiargs);
3668 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
3669 XDELETEVEC (rpo_numbers);
3671 for (i = 0; i < num_ssa_names; i++)
3673 tree name = ssa_name (i);
3675 && VN_INFO (name)->needs_insertion)
3676 release_ssa_name (name);
3678 obstack_free (&vn_ssa_aux_obstack, NULL);
3679 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
3681 VEC_free (tree, heap, sccstack);
3682 free_vn_table (valid_info);
3683 XDELETE (valid_info);
3684 free_vn_table (optimistic_info);
3685 XDELETE (optimistic_info);
3688 /* Set *ID if we computed something useful in RESULT. */
3691 set_value_id_for_result (tree result, unsigned int *id)
3695 if (TREE_CODE (result) == SSA_NAME)
3696 *id = VN_INFO (result)->value_id;
3697 else if (is_gimple_min_invariant (result))
3698 *id = get_or_alloc_constant_value_id (result);
3702 /* Set the value ids in the valid hash tables. */
3705 set_hashtable_value_ids (void)
3712 /* Now set the value ids of the things we had put in the hash
3715 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
3716 vno, vn_nary_op_t, hi)
3717 set_value_id_for_result (vno->result, &vno->value_id);
3719 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
3721 set_value_id_for_result (vp->result, &vp->value_id);
3723 FOR_EACH_HTAB_ELEMENT (valid_info->references,
3724 vr, vn_reference_t, hi)
3725 set_value_id_for_result (vr->result, &vr->value_id);
3728 /* Do SCCVN. Returns true if it finished, false if we bailed out
3729 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
3730 how we use the alias oracle walking during the VN process. */
3733 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
3737 bool changed = true;
3739 default_vn_walk_kind = default_vn_walk_kind_;
3742 current_info = valid_info;
3744 for (param = DECL_ARGUMENTS (current_function_decl);
3746 param = DECL_CHAIN (param))
3748 if (gimple_default_def (cfun, param) != NULL)
3750 tree def = gimple_default_def (cfun, param);
3751 VN_INFO (def)->valnum = def;
3755 for (i = 1; i < num_ssa_names; ++i)
3757 tree name = ssa_name (i);
3759 && VN_INFO (name)->visited == false
3760 && !has_zero_uses (name))
3768 /* Initialize the value ids. */
3770 for (i = 1; i < num_ssa_names; ++i)
3772 tree name = ssa_name (i);
3776 info = VN_INFO (name);
3777 if (info->valnum == name
3778 || info->valnum == VN_TOP)
3779 info->value_id = get_next_value_id ();
3780 else if (is_gimple_min_invariant (info->valnum))
3781 info->value_id = get_or_alloc_constant_value_id (info->valnum);
3784 /* Propagate until they stop changing. */
3788 for (i = 1; i < num_ssa_names; ++i)
3790 tree name = ssa_name (i);
3794 info = VN_INFO (name);
3795 if (TREE_CODE (info->valnum) == SSA_NAME
3796 && info->valnum != name
3797 && info->value_id != VN_INFO (info->valnum)->value_id)
3800 info->value_id = VN_INFO (info->valnum)->value_id;
3805 set_hashtable_value_ids ();
3807 if (dump_file && (dump_flags & TDF_DETAILS))
3809 fprintf (dump_file, "Value numbers:\n");
3810 for (i = 0; i < num_ssa_names; i++)
3812 tree name = ssa_name (i);
3814 && VN_INFO (name)->visited
3815 && SSA_VAL (name) != name)
3817 print_generic_expr (dump_file, name, 0);
3818 fprintf (dump_file, " = ");
3819 print_generic_expr (dump_file, SSA_VAL (name), 0);
3820 fprintf (dump_file, "\n");
3828 /* Return the maximum value id we have ever seen. */
3831 get_max_value_id (void)
3833 return next_value_id;
3836 /* Return the next unique value id. */
3839 get_next_value_id (void)
3841 return next_value_id++;
3845 /* Compare two expressions E1 and E2 and return true if they are equal. */
3848 expressions_equal_p (tree e1, tree e2)
3850 /* The obvious case. */
3854 /* If only one of them is null, they cannot be equal. */
3858 /* Now perform the actual comparison. */
3859 if (TREE_CODE (e1) == TREE_CODE (e2)
3860 && operand_equal_p (e1, e2, OEP_PURE_SAME))
3867 /* Return true if the nary operation NARY may trap. This is a copy
3868 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
3871 vn_nary_may_trap (vn_nary_op_t nary)
3874 tree rhs2 = NULL_TREE;
3875 bool honor_nans = false;
3876 bool honor_snans = false;
3877 bool fp_operation = false;
3878 bool honor_trapv = false;
3882 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
3883 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
3884 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
3887 fp_operation = FLOAT_TYPE_P (type);
3890 honor_nans = flag_trapping_math && !flag_finite_math_only;
3891 honor_snans = flag_signaling_nans != 0;
3893 else if (INTEGRAL_TYPE_P (type)
3894 && TYPE_OVERFLOW_TRAPS (type))
3897 if (nary->length >= 2)
3899 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
3901 honor_nans, honor_snans, rhs2,
3907 for (i = 0; i < nary->length; ++i)
3908 if (tree_could_trap_p (nary->op[i]))