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"
48 /* This algorithm is based on the SCC algorithm presented by Keith
49 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
50 (http://citeseer.ist.psu.edu/41805.html). In
51 straight line code, it is equivalent to a regular hash based value
52 numbering that is performed in reverse postorder.
54 For code with cycles, there are two alternatives, both of which
55 require keeping the hashtables separate from the actual list of
56 value numbers for SSA names.
58 1. Iterate value numbering in an RPO walk of the blocks, removing
59 all the entries from the hashtable after each iteration (but
60 keeping the SSA name->value number mapping between iterations).
61 Iterate until it does not change.
63 2. Perform value numbering as part of an SCC walk on the SSA graph,
64 iterating only the cycles in the SSA graph until they do not change
65 (using a separate, optimistic hashtable for value numbering the SCC
68 The second is not just faster in practice (because most SSA graph
69 cycles do not involve all the variables in the graph), it also has
72 One of these nice properties is that when we pop an SCC off the
73 stack, we are guaranteed to have processed all the operands coming from
74 *outside of that SCC*, so we do not need to do anything special to
75 ensure they have value numbers.
77 Another nice property is that the SCC walk is done as part of a DFS
78 of the SSA graph, which makes it easy to perform combining and
79 simplifying operations at the same time.
81 The code below is deliberately written in a way that makes it easy
82 to separate the SCC walk from the other work it does.
84 In order to propagate constants through the code, we track which
85 expressions contain constants, and use those while folding. In
86 theory, we could also track expressions whose value numbers are
87 replaced, in case we end up folding based on expression
90 In order to value number memory, we assign value numbers to vuses.
91 This enables us to note that, for example, stores to the same
92 address of the same value from the same starting memory states are
96 1. We can iterate only the changing portions of the SCC's, but
97 I have not seen an SCC big enough for this to be a win.
98 2. If you differentiate between phi nodes for loops and phi nodes
99 for if-then-else, you can properly consider phi nodes in different
100 blocks for equivalence.
101 3. We could value number vuses in more cases, particularly, whole
105 /* The set of hashtables and alloc_pool's for their items. */
107 typedef struct vn_tables_s
112 struct obstack nary_obstack;
113 alloc_pool phis_pool;
114 alloc_pool references_pool;
117 static htab_t constant_to_value_id;
118 static bitmap constant_value_ids;
121 /* Valid hashtables storing information we have proven to be
124 static vn_tables_t valid_info;
126 /* Optimistic hashtables storing information we are making assumptions about
127 during iterations. */
129 static vn_tables_t optimistic_info;
131 /* Pointer to the set of hashtables that is currently being used.
132 Should always point to either the optimistic_info, or the
135 static vn_tables_t current_info;
138 /* Reverse post order index for each basic block. */
140 static int *rpo_numbers;
142 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
144 /* This represents the top of the VN lattice, which is the universal
149 /* Unique counter for our value ids. */
151 static unsigned int next_value_id;
153 /* Next DFS number and the stack for strongly connected component
156 static unsigned int next_dfs_num;
157 static VEC (tree, heap) *sccstack;
160 DEF_VEC_P(vn_ssa_aux_t);
161 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
163 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
164 are allocated on an obstack for locality reasons, and to free them
165 without looping over the VEC. */
167 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
168 static struct obstack vn_ssa_aux_obstack;
170 /* Return the value numbering information for a given SSA name. */
175 vn_ssa_aux_t res = VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
176 SSA_NAME_VERSION (name));
177 gcc_checking_assert (res);
181 /* Set the value numbering info for a given SSA name to a given
185 VN_INFO_SET (tree name, vn_ssa_aux_t value)
187 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
188 SSA_NAME_VERSION (name), value);
191 /* Initialize the value numbering info for a given SSA name.
192 This should be called just once for every SSA name. */
195 VN_INFO_GET (tree name)
197 vn_ssa_aux_t newinfo;
199 newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
200 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
201 if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
202 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
203 SSA_NAME_VERSION (name) + 1);
204 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
205 SSA_NAME_VERSION (name), newinfo);
210 /* Get the representative expression for the SSA_NAME NAME. Returns
211 the representative SSA_NAME if there is no expression associated with it. */
214 vn_get_expr_for (tree name)
216 vn_ssa_aux_t vn = VN_INFO (name);
218 tree expr = NULL_TREE;
220 if (vn->valnum == VN_TOP)
223 /* If the value-number is a constant it is the representative
225 if (TREE_CODE (vn->valnum) != SSA_NAME)
228 /* Get to the information of the value of this SSA_NAME. */
229 vn = VN_INFO (vn->valnum);
231 /* If the value-number is a constant it is the representative
233 if (TREE_CODE (vn->valnum) != SSA_NAME)
236 /* Else if we have an expression, return it. */
237 if (vn->expr != NULL_TREE)
240 /* Otherwise use the defining statement to build the expression. */
241 def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
243 /* If the value number is a default-definition or a PHI result
245 if (gimple_nop_p (def_stmt)
246 || gimple_code (def_stmt) == GIMPLE_PHI)
249 if (!is_gimple_assign (def_stmt))
252 /* FIXME tuples. This is incomplete and likely will miss some
254 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)))
257 if ((gimple_assign_rhs_code (def_stmt) == VIEW_CONVERT_EXPR
258 || gimple_assign_rhs_code (def_stmt) == REALPART_EXPR
259 || gimple_assign_rhs_code (def_stmt) == IMAGPART_EXPR)
260 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
261 expr = fold_build1 (gimple_assign_rhs_code (def_stmt),
262 gimple_expr_type (def_stmt),
263 TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0));
267 expr = fold_build1 (gimple_assign_rhs_code (def_stmt),
268 gimple_expr_type (def_stmt),
269 gimple_assign_rhs1 (def_stmt));
273 expr = fold_build2 (gimple_assign_rhs_code (def_stmt),
274 gimple_expr_type (def_stmt),
275 gimple_assign_rhs1 (def_stmt),
276 gimple_assign_rhs2 (def_stmt));
281 if (expr == NULL_TREE)
284 /* Cache the expression. */
291 /* Free a phi operation structure VP. */
296 vn_phi_t phi = (vn_phi_t) vp;
297 VEC_free (tree, heap, phi->phiargs);
300 /* Free a reference operation structure VP. */
303 free_reference (void *vp)
305 vn_reference_t vr = (vn_reference_t) vp;
306 VEC_free (vn_reference_op_s, heap, vr->operands);
309 /* Hash table equality function for vn_constant_t. */
312 vn_constant_eq (const void *p1, const void *p2)
314 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
315 const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
317 if (vc1->hashcode != vc2->hashcode)
320 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
323 /* Hash table hash function for vn_constant_t. */
326 vn_constant_hash (const void *p1)
328 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
329 return vc1->hashcode;
332 /* Lookup a value id for CONSTANT and return it. If it does not
336 get_constant_value_id (tree constant)
339 struct vn_constant_s vc;
341 vc.hashcode = vn_hash_constant_with_type (constant);
342 vc.constant = constant;
343 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
344 vc.hashcode, NO_INSERT);
346 return ((vn_constant_t)*slot)->value_id;
350 /* Lookup a value id for CONSTANT, and if it does not exist, create a
351 new one and return it. If it does exist, return it. */
354 get_or_alloc_constant_value_id (tree constant)
357 struct vn_constant_s vc;
360 vc.hashcode = vn_hash_constant_with_type (constant);
361 vc.constant = constant;
362 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
363 vc.hashcode, INSERT);
365 return ((vn_constant_t)*slot)->value_id;
367 vcp = XNEW (struct vn_constant_s);
368 vcp->hashcode = vc.hashcode;
369 vcp->constant = constant;
370 vcp->value_id = get_next_value_id ();
371 *slot = (void *) vcp;
372 bitmap_set_bit (constant_value_ids, vcp->value_id);
373 return vcp->value_id;
376 /* Return true if V is a value id for a constant. */
379 value_id_constant_p (unsigned int v)
381 return bitmap_bit_p (constant_value_ids, v);
384 /* Compare two reference operands P1 and P2 for equality. Return true if
385 they are equal, and false otherwise. */
388 vn_reference_op_eq (const void *p1, const void *p2)
390 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
391 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
393 return vro1->opcode == vro2->opcode
394 && types_compatible_p (vro1->type, vro2->type)
395 && expressions_equal_p (vro1->op0, vro2->op0)
396 && expressions_equal_p (vro1->op1, vro2->op1)
397 && expressions_equal_p (vro1->op2, vro2->op2);
400 /* Compute the hash for a reference operand VRO1. */
403 vn_reference_op_compute_hash (const vn_reference_op_t vro1, hashval_t result)
405 result = iterative_hash_hashval_t (vro1->opcode, result);
407 result = iterative_hash_expr (vro1->op0, result);
409 result = iterative_hash_expr (vro1->op1, result);
411 result = iterative_hash_expr (vro1->op2, result);
415 /* Return the hashcode for a given reference operation P1. */
418 vn_reference_hash (const void *p1)
420 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
421 return vr1->hashcode;
424 /* Compute a hash for the reference operation VR1 and return it. */
427 vn_reference_compute_hash (const vn_reference_t vr1)
429 hashval_t result = 0;
431 vn_reference_op_t vro;
432 HOST_WIDE_INT off = -1;
435 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
437 if (vro->opcode == MEM_REF)
439 else if (vro->opcode != ADDR_EXPR)
451 result = iterative_hash_hashval_t (off, result);
454 && vro->opcode == ADDR_EXPR)
458 tree op = TREE_OPERAND (vro->op0, 0);
459 result = iterative_hash_hashval_t (TREE_CODE (op), result);
460 result = iterative_hash_expr (op, result);
464 result = vn_reference_op_compute_hash (vro, result);
468 result += SSA_NAME_VERSION (vr1->vuse);
473 /* Return true if reference operations P1 and P2 are equivalent. This
474 means they have the same set of operands and vuses. */
477 vn_reference_eq (const void *p1, const void *p2)
481 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
482 const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
483 if (vr1->hashcode != vr2->hashcode)
486 /* Early out if this is not a hash collision. */
487 if (vr1->hashcode != vr2->hashcode)
490 /* The VOP needs to be the same. */
491 if (vr1->vuse != vr2->vuse)
494 /* If the operands are the same we are done. */
495 if (vr1->operands == vr2->operands)
498 if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
501 if (INTEGRAL_TYPE_P (vr1->type)
502 && INTEGRAL_TYPE_P (vr2->type))
504 if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
507 else if (INTEGRAL_TYPE_P (vr1->type)
508 && (TYPE_PRECISION (vr1->type)
509 != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
511 else if (INTEGRAL_TYPE_P (vr2->type)
512 && (TYPE_PRECISION (vr2->type)
513 != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
520 HOST_WIDE_INT off1 = 0, off2 = 0;
521 vn_reference_op_t vro1, vro2;
522 vn_reference_op_s tem1, tem2;
523 bool deref1 = false, deref2 = false;
524 for (; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro1); i++)
526 if (vro1->opcode == MEM_REF)
532 for (; VEC_iterate (vn_reference_op_s, vr2->operands, j, vro2); j++)
534 if (vro2->opcode == MEM_REF)
542 if (deref1 && vro1->opcode == ADDR_EXPR)
544 memset (&tem1, 0, sizeof (tem1));
545 tem1.op0 = TREE_OPERAND (vro1->op0, 0);
546 tem1.type = TREE_TYPE (tem1.op0);
547 tem1.opcode = TREE_CODE (tem1.op0);
550 if (deref2 && vro2->opcode == ADDR_EXPR)
552 memset (&tem2, 0, sizeof (tem2));
553 tem2.op0 = TREE_OPERAND (vro2->op0, 0);
554 tem2.type = TREE_TYPE (tem2.op0);
555 tem2.opcode = TREE_CODE (tem2.op0);
558 if (!vn_reference_op_eq (vro1, vro2))
563 while (VEC_length (vn_reference_op_s, vr1->operands) != i
564 || VEC_length (vn_reference_op_s, vr2->operands) != j);
569 /* Copy the operations present in load/store REF into RESULT, a vector of
570 vn_reference_op_s's. */
573 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
575 if (TREE_CODE (ref) == TARGET_MEM_REF)
577 vn_reference_op_s temp;
580 base = TMR_SYMBOL (ref) ? TMR_SYMBOL (ref) : TMR_BASE (ref);
582 base = null_pointer_node;
584 memset (&temp, 0, sizeof (temp));
585 /* We do not care for spurious type qualifications. */
586 temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
587 temp.opcode = TREE_CODE (ref);
588 temp.op0 = TMR_INDEX (ref);
589 temp.op1 = TMR_STEP (ref);
590 temp.op2 = TMR_OFFSET (ref);
592 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
594 memset (&temp, 0, sizeof (temp));
595 temp.type = NULL_TREE;
596 temp.opcode = TREE_CODE (base);
599 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
603 /* For non-calls, store the information that makes up the address. */
607 vn_reference_op_s temp;
609 memset (&temp, 0, sizeof (temp));
610 /* We do not care for spurious type qualifications. */
611 temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
612 temp.opcode = TREE_CODE (ref);
617 case MISALIGNED_INDIRECT_REF:
618 temp.op0 = TREE_OPERAND (ref, 1);
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),
650 uhwi_to_double_int (BITS_PER_UNIT),
652 if (double_int_fits_in_shwi_p (off))
658 case ARRAY_RANGE_REF:
660 /* Record index as operand. */
661 temp.op0 = TREE_OPERAND (ref, 1);
662 /* Always record lower bounds and element size. */
663 temp.op1 = array_ref_low_bound (ref);
664 temp.op2 = array_ref_element_size (ref);
665 if (TREE_CODE (temp.op0) == INTEGER_CST
666 && TREE_CODE (temp.op1) == INTEGER_CST
667 && TREE_CODE (temp.op2) == INTEGER_CST)
669 double_int off = tree_to_double_int (temp.op0);
670 off = double_int_add (off,
672 (tree_to_double_int (temp.op1)));
673 off = double_int_mul (off, tree_to_double_int (temp.op2));
674 if (double_int_fits_in_shwi_p (off))
692 if (is_gimple_min_invariant (ref))
698 /* These are only interesting for their operands, their
699 existence, and their type. They will never be the last
700 ref in the chain of references (IE they require an
701 operand), so we don't have to put anything
702 for op* as it will be handled by the iteration */
704 case VIEW_CONVERT_EXPR:
708 /* This is only interesting for its constant offset. */
709 temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
714 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
716 if (REFERENCE_CLASS_P (ref)
717 || (TREE_CODE (ref) == ADDR_EXPR
718 && !is_gimple_min_invariant (ref)))
719 ref = TREE_OPERAND (ref, 0);
725 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
726 operands in *OPS, the reference alias set SET and the reference type TYPE.
727 Return true if something useful was produced. */
730 ao_ref_init_from_vn_reference (ao_ref *ref,
731 alias_set_type set, tree type,
732 VEC (vn_reference_op_s, heap) *ops)
734 vn_reference_op_t op;
736 tree base = NULL_TREE;
738 HOST_WIDE_INT offset = 0;
739 HOST_WIDE_INT max_size;
740 HOST_WIDE_INT size = -1;
741 tree size_tree = NULL_TREE;
742 alias_set_type base_alias_set = -1;
744 /* First get the final access size from just the outermost expression. */
745 op = VEC_index (vn_reference_op_s, ops, 0);
746 if (op->opcode == COMPONENT_REF)
747 size_tree = DECL_SIZE (op->op0);
748 else if (op->opcode == BIT_FIELD_REF)
752 enum machine_mode mode = TYPE_MODE (type);
754 size_tree = TYPE_SIZE (type);
756 size = GET_MODE_BITSIZE (mode);
758 if (size_tree != NULL_TREE)
760 if (!host_integerp (size_tree, 1))
763 size = TREE_INT_CST_LOW (size_tree);
766 /* Initially, maxsize is the same as the accessed element size.
767 In the following it will only grow (or become -1). */
770 /* Compute cumulative bit-offset for nested component-refs and array-refs,
771 and find the ultimate containing object. */
772 for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
776 /* These may be in the reference ops, but we cannot do anything
777 sensible with them here. */
779 /* Apart from ADDR_EXPR arguments to MEM_REF. */
780 if (base != NULL_TREE
781 && TREE_CODE (base) == MEM_REF
783 && DECL_P (TREE_OPERAND (op->op0, 0)))
785 vn_reference_op_t pop = VEC_index (vn_reference_op_s, ops, i-1);
786 base = TREE_OPERAND (op->op0, 0);
793 offset += pop->off * BITS_PER_UNIT;
801 /* Record the base objects. */
802 case MISALIGNED_INDIRECT_REF:
803 *op0_p = build2 (MISALIGNED_INDIRECT_REF, op->type,
805 op0_p = &TREE_OPERAND (*op0_p, 0);
809 base_alias_set = get_deref_alias_set (op->op0);
810 *op0_p = build2 (MEM_REF, op->type,
812 op0_p = &TREE_OPERAND (*op0_p, 0);
823 /* And now the usual component-reference style ops. */
825 offset += tree_low_cst (op->op1, 0);
830 tree field = op->op0;
831 /* We do not have a complete COMPONENT_REF tree here so we
832 cannot use component_ref_field_offset. Do the interesting
836 || !host_integerp (DECL_FIELD_OFFSET (field), 1))
840 offset += (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field))
842 offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
847 case ARRAY_RANGE_REF:
849 /* We recorded the lower bound and the element size. */
850 if (!host_integerp (op->op0, 0)
851 || !host_integerp (op->op1, 0)
852 || !host_integerp (op->op2, 0))
856 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (op->op0);
857 hindex -= TREE_INT_CST_LOW (op->op1);
858 hindex *= TREE_INT_CST_LOW (op->op2);
859 hindex *= BITS_PER_UNIT;
871 case VIEW_CONVERT_EXPR:
888 if (base == NULL_TREE)
891 ref->ref = NULL_TREE;
893 ref->offset = offset;
895 ref->max_size = max_size;
896 ref->ref_alias_set = set;
897 if (base_alias_set != -1)
898 ref->base_alias_set = base_alias_set;
900 ref->base_alias_set = get_alias_set (base);
905 /* Copy the operations present in load/store/call REF into RESULT, a vector of
906 vn_reference_op_s's. */
909 copy_reference_ops_from_call (gimple call,
910 VEC(vn_reference_op_s, heap) **result)
912 vn_reference_op_s temp;
915 /* Copy the type, opcode, function being called and static chain. */
916 memset (&temp, 0, sizeof (temp));
917 temp.type = gimple_call_return_type (call);
918 temp.opcode = CALL_EXPR;
919 temp.op0 = gimple_call_fn (call);
920 temp.op1 = gimple_call_chain (call);
922 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
924 /* Copy the call arguments. As they can be references as well,
925 just chain them together. */
926 for (i = 0; i < gimple_call_num_args (call); ++i)
928 tree callarg = gimple_call_arg (call, i);
929 copy_reference_ops_from_ref (callarg, result);
933 /* Create a vector of vn_reference_op_s structures from REF, a
934 REFERENCE_CLASS_P tree. The vector is not shared. */
936 static VEC(vn_reference_op_s, heap) *
937 create_reference_ops_from_ref (tree ref)
939 VEC (vn_reference_op_s, heap) *result = NULL;
941 copy_reference_ops_from_ref (ref, &result);
945 /* Create a vector of vn_reference_op_s structures from CALL, a
946 call statement. The vector is not shared. */
948 static VEC(vn_reference_op_s, heap) *
949 create_reference_ops_from_call (gimple call)
951 VEC (vn_reference_op_s, heap) *result = NULL;
953 copy_reference_ops_from_call (call, &result);
957 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
958 *I_P to point to the last element of the replacement. */
960 vn_reference_fold_indirect (VEC (vn_reference_op_s, heap) **ops,
963 unsigned int i = *i_p;
964 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
965 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
967 HOST_WIDE_INT addr_offset;
969 /* The only thing we have to do is from &OBJ.foo.bar add the offset
970 from .foo.bar to the preceeding MEM_REF offset and replace the
971 address with &OBJ. */
972 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
974 gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
975 if (addr_base != op->op0)
977 double_int off = tree_to_double_int (mem_op->op0);
978 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
979 off = double_int_add (off, shwi_to_double_int (addr_offset));
980 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
981 op->op0 = build_fold_addr_expr (addr_base);
982 if (host_integerp (mem_op->op0, 0))
983 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
989 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
990 *I_P to point to the last element of the replacement. */
992 vn_reference_maybe_forwprop_address (VEC (vn_reference_op_s, heap) **ops,
995 unsigned int i = *i_p;
996 vn_reference_op_t op = VEC_index (vn_reference_op_s, *ops, i);
997 vn_reference_op_t mem_op = VEC_index (vn_reference_op_s, *ops, i - 1);
1002 def_stmt = SSA_NAME_DEF_STMT (op->op0);
1003 if (!is_gimple_assign (def_stmt))
1006 code = gimple_assign_rhs_code (def_stmt);
1007 if (code != ADDR_EXPR
1008 && code != POINTER_PLUS_EXPR)
1011 off = tree_to_double_int (mem_op->op0);
1012 off = double_int_sext (off, TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
1014 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1015 from .foo.bar to the preceeding MEM_REF offset and replace the
1016 address with &OBJ. */
1017 if (code == ADDR_EXPR)
1019 tree addr, addr_base;
1020 HOST_WIDE_INT addr_offset;
1022 addr = gimple_assign_rhs1 (def_stmt);
1023 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1026 || TREE_CODE (addr_base) != MEM_REF)
1029 off = double_int_add (off, shwi_to_double_int (addr_offset));
1030 off = double_int_add (off, mem_ref_offset (addr_base));
1031 op->op0 = TREE_OPERAND (addr_base, 0);
1036 ptr = gimple_assign_rhs1 (def_stmt);
1037 ptroff = gimple_assign_rhs2 (def_stmt);
1038 if (TREE_CODE (ptr) != SSA_NAME
1039 || TREE_CODE (ptroff) != INTEGER_CST)
1042 off = double_int_add (off, tree_to_double_int (ptroff));
1046 mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
1047 if (host_integerp (mem_op->op0, 0))
1048 mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1051 if (TREE_CODE (op->op0) == SSA_NAME)
1052 op->op0 = SSA_VAL (op->op0);
1053 if (TREE_CODE (op->op0) != SSA_NAME)
1054 op->opcode = TREE_CODE (op->op0);
1057 if (TREE_CODE (op->op0) == SSA_NAME)
1058 vn_reference_maybe_forwprop_address (ops, i_p);
1059 else if (TREE_CODE (op->op0) == ADDR_EXPR)
1060 vn_reference_fold_indirect (ops, i_p);
1063 /* Optimize the reference REF to a constant if possible or return
1064 NULL_TREE if not. */
1067 fully_constant_vn_reference_p (vn_reference_t ref)
1069 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1070 vn_reference_op_t op;
1072 /* Try to simplify the translated expression if it is
1073 a call to a builtin function with at most two arguments. */
1074 op = VEC_index (vn_reference_op_s, operands, 0);
1075 if (op->opcode == CALL_EXPR
1076 && TREE_CODE (op->op0) == ADDR_EXPR
1077 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1078 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1079 && VEC_length (vn_reference_op_s, operands) >= 2
1080 && VEC_length (vn_reference_op_s, operands) <= 3)
1082 vn_reference_op_t arg0, arg1 = NULL;
1083 bool anyconst = false;
1084 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1085 if (VEC_length (vn_reference_op_s, operands) > 2)
1086 arg1 = VEC_index (vn_reference_op_s, operands, 2);
1087 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1088 || (arg0->opcode == ADDR_EXPR
1089 && is_gimple_min_invariant (arg0->op0)))
1092 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1093 || (arg1->opcode == ADDR_EXPR
1094 && is_gimple_min_invariant (arg1->op0))))
1098 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1101 arg1 ? arg1->op0 : NULL);
1103 && TREE_CODE (folded) == NOP_EXPR)
1104 folded = TREE_OPERAND (folded, 0);
1106 && is_gimple_min_invariant (folded))
1111 /* Simplify reads from constant strings. */
1112 else if (op->opcode == ARRAY_REF
1113 && TREE_CODE (op->op0) == INTEGER_CST
1114 && integer_zerop (op->op1)
1115 && VEC_length (vn_reference_op_s, operands) == 2)
1117 vn_reference_op_t arg0;
1118 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1119 if (arg0->opcode == STRING_CST
1120 && (TYPE_MODE (op->type)
1121 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0->op0))))
1122 && GET_MODE_CLASS (TYPE_MODE (op->type)) == MODE_INT
1123 && GET_MODE_SIZE (TYPE_MODE (op->type)) == 1
1124 && compare_tree_int (op->op0, TREE_STRING_LENGTH (arg0->op0)) < 0)
1125 return build_int_cst_type (op->type,
1126 (TREE_STRING_POINTER (arg0->op0)
1127 [TREE_INT_CST_LOW (op->op0)]));
1133 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1134 structures into their value numbers. This is done in-place, and
1135 the vector passed in is returned. */
1137 static VEC (vn_reference_op_s, heap) *
1138 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
1140 vn_reference_op_t vro;
1143 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
1145 if (vro->opcode == SSA_NAME
1146 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1148 vro->op0 = SSA_VAL (vro->op0);
1149 /* If it transforms from an SSA_NAME to a constant, update
1151 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1152 vro->opcode = TREE_CODE (vro->op0);
1154 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1155 vro->op1 = SSA_VAL (vro->op1);
1156 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1157 vro->op2 = SSA_VAL (vro->op2);
1158 /* If it transforms from an SSA_NAME to an address, fold with
1159 a preceding indirect reference. */
1162 && TREE_CODE (vro->op0) == ADDR_EXPR
1163 && VEC_index (vn_reference_op_s,
1164 orig, i - 1)->opcode == MEM_REF)
1165 vn_reference_fold_indirect (&orig, &i);
1167 && vro->opcode == SSA_NAME
1168 && VEC_index (vn_reference_op_s,
1169 orig, i - 1)->opcode == MEM_REF)
1170 vn_reference_maybe_forwprop_address (&orig, &i);
1171 /* If it transforms a non-constant ARRAY_REF into a constant
1172 one, adjust the constant offset. */
1173 else if (vro->opcode == ARRAY_REF
1175 && TREE_CODE (vro->op0) == INTEGER_CST
1176 && TREE_CODE (vro->op1) == INTEGER_CST
1177 && TREE_CODE (vro->op2) == INTEGER_CST)
1179 double_int off = tree_to_double_int (vro->op0);
1180 off = double_int_add (off,
1182 (tree_to_double_int (vro->op1)));
1183 off = double_int_mul (off, tree_to_double_int (vro->op2));
1184 if (double_int_fits_in_shwi_p (off))
1192 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
1194 /* Create a vector of vn_reference_op_s structures from REF, a
1195 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1198 static VEC(vn_reference_op_s, heap) *
1199 valueize_shared_reference_ops_from_ref (tree ref)
1203 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1204 copy_reference_ops_from_ref (ref, &shared_lookup_references);
1205 shared_lookup_references = valueize_refs (shared_lookup_references);
1206 return shared_lookup_references;
1209 /* Create a vector of vn_reference_op_s structures from CALL, a
1210 call statement. The vector is shared among all callers of
1213 static VEC(vn_reference_op_s, heap) *
1214 valueize_shared_reference_ops_from_call (gimple call)
1218 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1219 copy_reference_ops_from_call (call, &shared_lookup_references);
1220 shared_lookup_references = valueize_refs (shared_lookup_references);
1221 return shared_lookup_references;
1224 /* Lookup a SCCVN reference operation VR in the current hash table.
1225 Returns the resulting value number if it exists in the hash table,
1226 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1227 vn_reference_t stored in the hashtable if something is found. */
1230 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1235 hash = vr->hashcode;
1236 slot = htab_find_slot_with_hash (current_info->references, vr,
1238 if (!slot && current_info == optimistic_info)
1239 slot = htab_find_slot_with_hash (valid_info->references, vr,
1244 *vnresult = (vn_reference_t)*slot;
1245 return ((vn_reference_t)*slot)->result;
1251 static tree *last_vuse_ptr;
1253 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1254 with the current VUSE and performs the expression lookup. */
1257 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
1259 vn_reference_t vr = (vn_reference_t)vr_;
1264 *last_vuse_ptr = vuse;
1266 /* Fixup vuse and hash. */
1268 vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1269 vr->vuse = SSA_VAL (vuse);
1271 vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1273 hash = vr->hashcode;
1274 slot = htab_find_slot_with_hash (current_info->references, vr,
1276 if (!slot && current_info == optimistic_info)
1277 slot = htab_find_slot_with_hash (valid_info->references, vr,
1285 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1286 from the statement defining VUSE and if not successful tries to
1287 translate *REFP and VR_ through an aggregate copy at the defintion
1291 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_)
1293 vn_reference_t vr = (vn_reference_t)vr_;
1294 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1297 HOST_WIDE_INT offset, maxsize;
1299 /* First try to disambiguate after value-replacing in the definitions LHS. */
1300 if (is_gimple_assign (def_stmt))
1302 tree lhs = gimple_assign_lhs (def_stmt);
1304 VEC (vn_reference_op_s, heap) *operands = NULL;
1306 copy_reference_ops_from_ref (lhs, &operands);
1307 operands = valueize_refs (operands);
1308 if (ao_ref_init_from_vn_reference (&ref1, get_alias_set (lhs),
1309 TREE_TYPE (lhs), operands))
1310 res = refs_may_alias_p_1 (ref, &ref1, true);
1311 VEC_free (vn_reference_op_s, heap, operands);
1316 base = ao_ref_base (ref);
1317 offset = ref->offset;
1318 maxsize = ref->max_size;
1320 /* If we cannot constrain the size of the reference we cannot
1321 test if anything kills it. */
1325 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1326 from that defintion.
1328 if (is_gimple_reg_type (vr->type)
1329 && is_gimple_call (def_stmt)
1330 && (fndecl = gimple_call_fndecl (def_stmt))
1331 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1332 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
1333 && integer_zerop (gimple_call_arg (def_stmt, 1))
1334 && host_integerp (gimple_call_arg (def_stmt, 2), 1)
1335 && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1337 tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1339 HOST_WIDE_INT offset2, size2, maxsize2;
1340 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1341 size2 = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2)) * 8;
1342 if ((unsigned HOST_WIDE_INT)size2 / 8
1343 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2))
1344 && operand_equal_p (base, base2, 0)
1345 && offset2 <= offset
1346 && offset2 + size2 >= offset + maxsize)
1348 tree val = fold_convert (vr->type, integer_zero_node);
1349 unsigned int value_id = get_or_alloc_constant_value_id (val);
1350 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1351 VEC_copy (vn_reference_op_s,
1352 heap, vr->operands),
1357 /* 2) Assignment from an empty CONSTRUCTOR. */
1358 else if (is_gimple_reg_type (vr->type)
1359 && gimple_assign_single_p (def_stmt)
1360 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1361 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1364 HOST_WIDE_INT offset2, size2, maxsize2;
1365 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1366 &offset2, &size2, &maxsize2);
1367 if (operand_equal_p (base, base2, 0)
1368 && offset2 <= offset
1369 && offset2 + size2 >= offset + maxsize)
1371 tree val = fold_convert (vr->type, integer_zero_node);
1372 unsigned int value_id = get_or_alloc_constant_value_id (val);
1373 return vn_reference_insert_pieces (vuse, vr->set, vr->type,
1374 VEC_copy (vn_reference_op_s,
1375 heap, vr->operands),
1380 /* For aggregate copies translate the reference through them if
1381 the copy kills ref. */
1382 else if (gimple_assign_single_p (def_stmt)
1383 && (DECL_P (gimple_assign_rhs1 (def_stmt))
1384 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
1385 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1388 HOST_WIDE_INT offset2, size2, maxsize2;
1390 VEC (vn_reference_op_s, heap) *lhs = NULL, *rhs = NULL;
1391 vn_reference_op_t vro;
1394 /* See if the assignment kills REF. */
1395 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1396 &offset2, &size2, &maxsize2);
1397 if (!operand_equal_p (base, base2, 0)
1399 || offset2 + size2 < offset + maxsize)
1402 /* Find the common base of ref and the lhs. */
1403 copy_reference_ops_from_ref (gimple_assign_lhs (def_stmt), &lhs);
1404 i = VEC_length (vn_reference_op_s, vr->operands) - 1;
1405 j = VEC_length (vn_reference_op_s, lhs) - 1;
1406 while (j >= 0 && i >= 0
1407 && vn_reference_op_eq (VEC_index (vn_reference_op_s,
1409 VEC_index (vn_reference_op_s, lhs, j)))
1415 VEC_free (vn_reference_op_s, heap, lhs);
1416 /* i now points to the first additional op.
1417 ??? LHS may not be completely contained in VR, one or more
1418 VIEW_CONVERT_EXPRs could be in its way. We could at least
1419 try handling outermost VIEW_CONVERT_EXPRs. */
1423 /* Now re-write REF to be based on the rhs of the assignment. */
1424 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1425 /* We need to pre-pend vr->operands[0..i] to rhs. */
1426 if (i + 1 + VEC_length (vn_reference_op_s, rhs)
1427 > VEC_length (vn_reference_op_s, vr->operands))
1429 VEC (vn_reference_op_s, heap) *old = vr->operands;
1430 VEC_safe_grow (vn_reference_op_s, heap, vr->operands,
1431 i + 1 + VEC_length (vn_reference_op_s, rhs));
1432 if (old == shared_lookup_references
1433 && vr->operands != old)
1434 shared_lookup_references = NULL;
1437 VEC_truncate (vn_reference_op_s, vr->operands,
1438 i + 1 + VEC_length (vn_reference_op_s, rhs));
1439 for (j = 0; VEC_iterate (vn_reference_op_s, rhs, j, vro); ++j)
1440 VEC_replace (vn_reference_op_s, vr->operands, i + 1 + j, vro);
1441 VEC_free (vn_reference_op_s, heap, rhs);
1442 vr->hashcode = vn_reference_compute_hash (vr);
1444 /* Adjust *ref from the new operands. */
1445 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1447 /* This can happen with bitfields. */
1448 if (ref->size != r.size)
1452 /* Do not update last seen VUSE after translating. */
1453 last_vuse_ptr = NULL;
1455 /* Keep looking for the adjusted *REF / VR pair. */
1459 /* Bail out and stop walking. */
1463 /* Lookup a reference operation by it's parts, in the current hash table.
1464 Returns the resulting value number if it exists in the hash table,
1465 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1466 vn_reference_t stored in the hashtable if something is found. */
1469 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
1470 VEC (vn_reference_op_s, heap) *operands,
1471 vn_reference_t *vnresult, bool maywalk)
1473 struct vn_reference_s vr1;
1481 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1482 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1483 VEC_safe_grow (vn_reference_op_s, heap, shared_lookup_references,
1484 VEC_length (vn_reference_op_s, operands));
1485 memcpy (VEC_address (vn_reference_op_s, shared_lookup_references),
1486 VEC_address (vn_reference_op_s, operands),
1487 sizeof (vn_reference_op_s)
1488 * VEC_length (vn_reference_op_s, operands));
1489 vr1.operands = operands = shared_lookup_references
1490 = valueize_refs (shared_lookup_references);
1493 vr1.hashcode = vn_reference_compute_hash (&vr1);
1494 if ((cst = fully_constant_vn_reference_p (&vr1)))
1497 vn_reference_lookup_1 (&vr1, vnresult);
1503 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
1505 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1506 vn_reference_lookup_2,
1507 vn_reference_lookup_3, &vr1);
1508 if (vr1.operands != operands)
1509 VEC_free (vn_reference_op_s, heap, vr1.operands);
1513 return (*vnresult)->result;
1518 /* Lookup OP in the current hash table, and return the resulting value
1519 number if it exists in the hash table. Return NULL_TREE if it does
1520 not exist in the hash table or if the result field of the structure
1521 was NULL.. VNRESULT will be filled in with the vn_reference_t
1522 stored in the hashtable if one exists. */
1525 vn_reference_lookup (tree op, tree vuse, bool maywalk,
1526 vn_reference_t *vnresult)
1528 VEC (vn_reference_op_s, heap) *operands;
1529 struct vn_reference_s vr1;
1535 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1536 vr1.operands = operands = valueize_shared_reference_ops_from_ref (op);
1537 vr1.type = TREE_TYPE (op);
1538 vr1.set = get_alias_set (op);
1539 vr1.hashcode = vn_reference_compute_hash (&vr1);
1540 if ((cst = fully_constant_vn_reference_p (&vr1)))
1546 vn_reference_t wvnresult;
1548 ao_ref_init (&r, op);
1550 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1551 vn_reference_lookup_2,
1552 vn_reference_lookup_3, &vr1);
1553 if (vr1.operands != operands)
1554 VEC_free (vn_reference_op_s, heap, vr1.operands);
1558 *vnresult = wvnresult;
1559 return wvnresult->result;
1565 return vn_reference_lookup_1 (&vr1, vnresult);
1569 /* Insert OP into the current hash table with a value number of
1570 RESULT, and return the resulting reference structure we created. */
1573 vn_reference_insert (tree op, tree result, tree vuse)
1578 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1579 if (TREE_CODE (result) == SSA_NAME)
1580 vr1->value_id = VN_INFO (result)->value_id;
1582 vr1->value_id = get_or_alloc_constant_value_id (result);
1583 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1584 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1585 vr1->type = TREE_TYPE (op);
1586 vr1->set = get_alias_set (op);
1587 vr1->hashcode = vn_reference_compute_hash (vr1);
1588 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1590 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1593 /* Because we lookup stores using vuses, and value number failures
1594 using the vdefs (see visit_reference_op_store for how and why),
1595 it's possible that on failure we may try to insert an already
1596 inserted store. This is not wrong, there is no ssa name for a
1597 store that we could use as a differentiator anyway. Thus, unlike
1598 the other lookup functions, you cannot gcc_assert (!*slot)
1601 /* But free the old slot in case of a collision. */
1603 free_reference (*slot);
1609 /* Insert a reference by it's pieces into the current hash table with
1610 a value number of RESULT. Return the resulting reference
1611 structure we created. */
1614 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
1615 VEC (vn_reference_op_s, heap) *operands,
1616 tree result, unsigned int value_id)
1622 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1623 vr1->value_id = value_id;
1624 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1625 vr1->operands = valueize_refs (operands);
1628 vr1->hashcode = vn_reference_compute_hash (vr1);
1629 if (result && TREE_CODE (result) == SSA_NAME)
1630 result = SSA_VAL (result);
1631 vr1->result = result;
1633 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1636 /* At this point we should have all the things inserted that we have
1637 seen before, and we should never try inserting something that
1639 gcc_assert (!*slot);
1641 free_reference (*slot);
1647 /* Compute and return the hash value for nary operation VBO1. */
1650 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1655 for (i = 0; i < vno1->length; ++i)
1656 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1657 vno1->op[i] = SSA_VAL (vno1->op[i]);
1659 if (vno1->length == 2
1660 && commutative_tree_code (vno1->opcode)
1661 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1663 tree temp = vno1->op[0];
1664 vno1->op[0] = vno1->op[1];
1668 hash = iterative_hash_hashval_t (vno1->opcode, 0);
1669 for (i = 0; i < vno1->length; ++i)
1670 hash = iterative_hash_expr (vno1->op[i], hash);
1675 /* Return the computed hashcode for nary operation P1. */
1678 vn_nary_op_hash (const void *p1)
1680 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1681 return vno1->hashcode;
1684 /* Compare nary operations P1 and P2 and return true if they are
1688 vn_nary_op_eq (const void *p1, const void *p2)
1690 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1691 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1694 if (vno1->hashcode != vno2->hashcode)
1697 if (vno1->opcode != vno2->opcode
1698 || !types_compatible_p (vno1->type, vno2->type))
1701 for (i = 0; i < vno1->length; ++i)
1702 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1708 /* Lookup a n-ary operation by its pieces and return the resulting value
1709 number if it exists in the hash table. Return NULL_TREE if it does
1710 not exist in the hash table or if the result field of the operation
1711 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1715 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
1716 tree type, tree op0, tree op1, tree op2,
1717 tree op3, vn_nary_op_t *vnresult)
1720 struct vn_nary_op_s vno1;
1724 vno1.length = length;
1730 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1731 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1733 if (!slot && current_info == optimistic_info)
1734 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1739 *vnresult = (vn_nary_op_t)*slot;
1740 return ((vn_nary_op_t)*slot)->result;
1743 /* Lookup OP in the current hash table, and return the resulting value
1744 number if it exists in the hash table. Return NULL_TREE if it does
1745 not exist in the hash table or if the result field of the operation
1746 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1750 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
1753 struct vn_nary_op_s vno1;
1758 vno1.opcode = TREE_CODE (op);
1759 vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
1760 vno1.type = TREE_TYPE (op);
1761 for (i = 0; i < vno1.length; ++i)
1762 vno1.op[i] = TREE_OPERAND (op, i);
1763 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1764 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1766 if (!slot && current_info == optimistic_info)
1767 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1772 *vnresult = (vn_nary_op_t)*slot;
1773 return ((vn_nary_op_t)*slot)->result;
1776 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1777 value number if it exists in the hash table. Return NULL_TREE if
1778 it does not exist in the hash table. VNRESULT will contain the
1779 vn_nary_op_t from the hashtable if it exists. */
1782 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
1785 struct vn_nary_op_s vno1;
1790 vno1.opcode = gimple_assign_rhs_code (stmt);
1791 vno1.length = gimple_num_ops (stmt) - 1;
1792 vno1.type = gimple_expr_type (stmt);
1793 for (i = 0; i < vno1.length; ++i)
1794 vno1.op[i] = gimple_op (stmt, i + 1);
1795 if (vno1.opcode == REALPART_EXPR
1796 || vno1.opcode == IMAGPART_EXPR
1797 || vno1.opcode == VIEW_CONVERT_EXPR)
1798 vno1.op[0] = TREE_OPERAND (vno1.op[0], 0);
1799 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1800 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1802 if (!slot && current_info == optimistic_info)
1803 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1808 *vnresult = (vn_nary_op_t)*slot;
1809 return ((vn_nary_op_t)*slot)->result;
1812 /* Insert a n-ary operation into the current hash table using it's
1813 pieces. Return the vn_nary_op_t structure we created and put in
1817 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
1818 tree type, tree op0,
1819 tree op1, tree op2, tree op3,
1821 unsigned int value_id)
1826 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1827 (sizeof (struct vn_nary_op_s)
1828 - sizeof (tree) * (4 - length)));
1829 vno1->value_id = value_id;
1830 vno1->opcode = code;
1831 vno1->length = length;
1841 vno1->result = result;
1842 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1843 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1845 gcc_assert (!*slot);
1852 /* Insert OP into the current hash table with a value number of
1853 RESULT. Return the vn_nary_op_t structure we created and put in
1857 vn_nary_op_insert (tree op, tree result)
1859 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
1864 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1865 (sizeof (struct vn_nary_op_s)
1866 - sizeof (tree) * (4 - length)));
1867 vno1->value_id = VN_INFO (result)->value_id;
1868 vno1->opcode = TREE_CODE (op);
1869 vno1->length = length;
1870 vno1->type = TREE_TYPE (op);
1871 for (i = 0; i < vno1->length; ++i)
1872 vno1->op[i] = TREE_OPERAND (op, i);
1873 vno1->result = result;
1874 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1875 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1877 gcc_assert (!*slot);
1883 /* Insert the rhs of STMT into the current hash table with a value number of
1887 vn_nary_op_insert_stmt (gimple stmt, tree result)
1889 unsigned length = gimple_num_ops (stmt) - 1;
1894 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1895 (sizeof (struct vn_nary_op_s)
1896 - sizeof (tree) * (4 - length)));
1897 vno1->value_id = VN_INFO (result)->value_id;
1898 vno1->opcode = gimple_assign_rhs_code (stmt);
1899 vno1->length = length;
1900 vno1->type = gimple_expr_type (stmt);
1901 for (i = 0; i < vno1->length; ++i)
1902 vno1->op[i] = gimple_op (stmt, i + 1);
1903 if (vno1->opcode == REALPART_EXPR
1904 || vno1->opcode == IMAGPART_EXPR
1905 || vno1->opcode == VIEW_CONVERT_EXPR)
1906 vno1->op[0] = TREE_OPERAND (vno1->op[0], 0);
1907 vno1->result = result;
1908 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1909 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1911 gcc_assert (!*slot);
1917 /* Compute a hashcode for PHI operation VP1 and return it. */
1919 static inline hashval_t
1920 vn_phi_compute_hash (vn_phi_t vp1)
1927 result = vp1->block->index;
1929 /* If all PHI arguments are constants we need to distinguish
1930 the PHI node via its type. */
1931 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
1932 result += (INTEGRAL_TYPE_P (type)
1933 + (INTEGRAL_TYPE_P (type)
1934 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
1936 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1938 if (phi1op == VN_TOP)
1940 result = iterative_hash_expr (phi1op, result);
1946 /* Return the computed hashcode for phi operation P1. */
1949 vn_phi_hash (const void *p1)
1951 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1952 return vp1->hashcode;
1955 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1958 vn_phi_eq (const void *p1, const void *p2)
1960 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1961 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
1963 if (vp1->hashcode != vp2->hashcode)
1966 if (vp1->block == vp2->block)
1971 /* If the PHI nodes do not have compatible types
1972 they are not the same. */
1973 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
1974 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
1977 /* Any phi in the same block will have it's arguments in the
1978 same edge order, because of how we store phi nodes. */
1979 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1981 tree phi2op = VEC_index (tree, vp2->phiargs, i);
1982 if (phi1op == VN_TOP || phi2op == VN_TOP)
1984 if (!expressions_equal_p (phi1op, phi2op))
1992 static VEC(tree, heap) *shared_lookup_phiargs;
1994 /* Lookup PHI in the current hash table, and return the resulting
1995 value number if it exists in the hash table. Return NULL_TREE if
1996 it does not exist in the hash table. */
1999 vn_phi_lookup (gimple phi)
2002 struct vn_phi_s vp1;
2005 VEC_truncate (tree, shared_lookup_phiargs, 0);
2007 /* Canonicalize the SSA_NAME's to their value number. */
2008 for (i = 0; i < gimple_phi_num_args (phi); i++)
2010 tree def = PHI_ARG_DEF (phi, i);
2011 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2012 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
2014 vp1.phiargs = shared_lookup_phiargs;
2015 vp1.block = gimple_bb (phi);
2016 vp1.hashcode = vn_phi_compute_hash (&vp1);
2017 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
2019 if (!slot && current_info == optimistic_info)
2020 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
2024 return ((vn_phi_t)*slot)->result;
2027 /* Insert PHI into the current hash table with a value number of
2031 vn_phi_insert (gimple phi, tree result)
2034 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
2036 VEC (tree, heap) *args = NULL;
2038 /* Canonicalize the SSA_NAME's to their value number. */
2039 for (i = 0; i < gimple_phi_num_args (phi); i++)
2041 tree def = PHI_ARG_DEF (phi, i);
2042 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2043 VEC_safe_push (tree, heap, args, def);
2045 vp1->value_id = VN_INFO (result)->value_id;
2046 vp1->phiargs = args;
2047 vp1->block = gimple_bb (phi);
2048 vp1->result = result;
2049 vp1->hashcode = vn_phi_compute_hash (vp1);
2051 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
2054 /* Because we iterate over phi operations more than once, it's
2055 possible the slot might already exist here, hence no assert.*/
2061 /* Print set of components in strongly connected component SCC to OUT. */
2064 print_scc (FILE *out, VEC (tree, heap) *scc)
2069 fprintf (out, "SCC consists of: ");
2070 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2072 print_generic_expr (out, var, 0);
2075 fprintf (out, "\n");
2078 /* Set the value number of FROM to TO, return true if it has changed
2082 set_ssa_val_to (tree from, tree to)
2087 && TREE_CODE (to) == SSA_NAME
2088 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
2091 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2092 and invariants. So assert that here. */
2093 gcc_assert (to != NULL_TREE
2095 || TREE_CODE (to) == SSA_NAME
2096 || is_gimple_min_invariant (to)));
2098 if (dump_file && (dump_flags & TDF_DETAILS))
2100 fprintf (dump_file, "Setting value number of ");
2101 print_generic_expr (dump_file, from, 0);
2102 fprintf (dump_file, " to ");
2103 print_generic_expr (dump_file, to, 0);
2106 currval = SSA_VAL (from);
2108 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
2110 VN_INFO (from)->valnum = to;
2111 if (dump_file && (dump_flags & TDF_DETAILS))
2112 fprintf (dump_file, " (changed)\n");
2115 if (dump_file && (dump_flags & TDF_DETAILS))
2116 fprintf (dump_file, "\n");
2120 /* Set all definitions in STMT to value number to themselves.
2121 Return true if a value number changed. */
2124 defs_to_varying (gimple stmt)
2126 bool changed = false;
2130 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2132 tree def = DEF_FROM_PTR (defp);
2134 VN_INFO (def)->use_processed = true;
2135 changed |= set_ssa_val_to (def, def);
2140 static bool expr_has_constants (tree expr);
2141 static tree valueize_expr (tree expr);
2143 /* Visit a copy between LHS and RHS, return true if the value number
2147 visit_copy (tree lhs, tree rhs)
2149 /* Follow chains of copies to their destination. */
2150 while (TREE_CODE (rhs) == SSA_NAME
2151 && SSA_VAL (rhs) != rhs)
2152 rhs = SSA_VAL (rhs);
2154 /* The copy may have a more interesting constant filled expression
2155 (we don't, since we know our RHS is just an SSA name). */
2156 if (TREE_CODE (rhs) == SSA_NAME)
2158 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
2159 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
2162 return set_ssa_val_to (lhs, rhs);
2165 /* Visit a unary operator RHS, value number it, and return true if the
2166 value number of LHS has changed as a result. */
2169 visit_unary_op (tree lhs, gimple stmt)
2171 bool changed = false;
2172 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2176 changed = set_ssa_val_to (lhs, result);
2180 changed = set_ssa_val_to (lhs, lhs);
2181 vn_nary_op_insert_stmt (stmt, lhs);
2187 /* Visit a binary operator RHS, value number it, and return true if the
2188 value number of LHS has changed as a result. */
2191 visit_binary_op (tree lhs, gimple stmt)
2193 bool changed = false;
2194 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2198 changed = set_ssa_val_to (lhs, result);
2202 changed = set_ssa_val_to (lhs, lhs);
2203 vn_nary_op_insert_stmt (stmt, lhs);
2209 /* Visit a call STMT storing into LHS. Return true if the value number
2210 of the LHS has changed as a result. */
2213 visit_reference_op_call (tree lhs, gimple stmt)
2215 bool changed = false;
2216 struct vn_reference_s vr1;
2218 tree vuse = gimple_vuse (stmt);
2220 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2221 vr1.operands = valueize_shared_reference_ops_from_call (stmt);
2222 vr1.type = gimple_expr_type (stmt);
2224 vr1.hashcode = vn_reference_compute_hash (&vr1);
2225 result = vn_reference_lookup_1 (&vr1, NULL);
2228 changed = set_ssa_val_to (lhs, result);
2229 if (TREE_CODE (result) == SSA_NAME
2230 && VN_INFO (result)->has_constants)
2231 VN_INFO (lhs)->has_constants = true;
2237 changed = set_ssa_val_to (lhs, lhs);
2238 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
2239 vr2->vuse = vr1.vuse;
2240 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
2241 vr2->type = vr1.type;
2243 vr2->hashcode = vr1.hashcode;
2245 slot = htab_find_slot_with_hash (current_info->references,
2246 vr2, vr2->hashcode, INSERT);
2248 free_reference (*slot);
2255 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2256 and return true if the value number of the LHS has changed as a result. */
2259 visit_reference_op_load (tree lhs, tree op, gimple stmt)
2261 bool changed = false;
2265 last_vuse = gimple_vuse (stmt);
2266 last_vuse_ptr = &last_vuse;
2267 result = vn_reference_lookup (op, gimple_vuse (stmt), true, NULL);
2268 last_vuse_ptr = NULL;
2270 /* If we have a VCE, try looking up its operand as it might be stored in
2271 a different type. */
2272 if (!result && TREE_CODE (op) == VIEW_CONVERT_EXPR)
2273 result = vn_reference_lookup (TREE_OPERAND (op, 0), gimple_vuse (stmt),
2276 /* We handle type-punning through unions by value-numbering based
2277 on offset and size of the access. Be prepared to handle a
2278 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2280 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
2282 /* We will be setting the value number of lhs to the value number
2283 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2284 So first simplify and lookup this expression to see if it
2285 is already available. */
2286 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
2287 if ((CONVERT_EXPR_P (val)
2288 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
2289 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
2291 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
2292 if ((CONVERT_EXPR_P (tem)
2293 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
2294 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
2295 TREE_TYPE (val), tem)))
2299 if (!is_gimple_min_invariant (val)
2300 && TREE_CODE (val) != SSA_NAME)
2301 result = vn_nary_op_lookup (val, NULL);
2302 /* If the expression is not yet available, value-number lhs to
2303 a new SSA_NAME we create. */
2306 result = make_ssa_name (SSA_NAME_VAR (lhs), gimple_build_nop ());
2307 /* Initialize value-number information properly. */
2308 VN_INFO_GET (result)->valnum = result;
2309 VN_INFO (result)->value_id = get_next_value_id ();
2310 VN_INFO (result)->expr = val;
2311 VN_INFO (result)->has_constants = expr_has_constants (val);
2312 VN_INFO (result)->needs_insertion = true;
2313 /* As all "inserted" statements are singleton SCCs, insert
2314 to the valid table. This is strictly needed to
2315 avoid re-generating new value SSA_NAMEs for the same
2316 expression during SCC iteration over and over (the
2317 optimistic table gets cleared after each iteration).
2318 We do not need to insert into the optimistic table, as
2319 lookups there will fall back to the valid table. */
2320 if (current_info == optimistic_info)
2322 current_info = valid_info;
2323 vn_nary_op_insert (val, result);
2324 current_info = optimistic_info;
2327 vn_nary_op_insert (val, result);
2328 if (dump_file && (dump_flags & TDF_DETAILS))
2330 fprintf (dump_file, "Inserting name ");
2331 print_generic_expr (dump_file, result, 0);
2332 fprintf (dump_file, " for expression ");
2333 print_generic_expr (dump_file, val, 0);
2334 fprintf (dump_file, "\n");
2341 changed = set_ssa_val_to (lhs, result);
2342 if (TREE_CODE (result) == SSA_NAME
2343 && VN_INFO (result)->has_constants)
2345 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
2346 VN_INFO (lhs)->has_constants = true;
2351 changed = set_ssa_val_to (lhs, lhs);
2352 vn_reference_insert (op, lhs, last_vuse);
2359 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2360 and return true if the value number of the LHS has changed as a result. */
2363 visit_reference_op_store (tree lhs, tree op, gimple stmt)
2365 bool changed = false;
2367 bool resultsame = false;
2369 /* First we want to lookup using the *vuses* from the store and see
2370 if there the last store to this location with the same address
2373 The vuses represent the memory state before the store. If the
2374 memory state, address, and value of the store is the same as the
2375 last store to this location, then this store will produce the
2376 same memory state as that store.
2378 In this case the vdef versions for this store are value numbered to those
2379 vuse versions, since they represent the same memory state after
2382 Otherwise, the vdefs for the store are used when inserting into
2383 the table, since the store generates a new memory state. */
2385 result = vn_reference_lookup (lhs, gimple_vuse (stmt), false, NULL);
2389 if (TREE_CODE (result) == SSA_NAME)
2390 result = SSA_VAL (result);
2391 if (TREE_CODE (op) == SSA_NAME)
2393 resultsame = expressions_equal_p (result, op);
2396 if (!result || !resultsame)
2400 if (dump_file && (dump_flags & TDF_DETAILS))
2402 fprintf (dump_file, "No store match\n");
2403 fprintf (dump_file, "Value numbering store ");
2404 print_generic_expr (dump_file, lhs, 0);
2405 fprintf (dump_file, " to ");
2406 print_generic_expr (dump_file, op, 0);
2407 fprintf (dump_file, "\n");
2409 /* Have to set value numbers before insert, since insert is
2410 going to valueize the references in-place. */
2411 if ((vdef = gimple_vdef (stmt)))
2413 VN_INFO (vdef)->use_processed = true;
2414 changed |= set_ssa_val_to (vdef, vdef);
2417 /* Do not insert structure copies into the tables. */
2418 if (is_gimple_min_invariant (op)
2419 || is_gimple_reg (op))
2420 vn_reference_insert (lhs, op, vdef);
2424 /* We had a match, so value number the vdef to have the value
2425 number of the vuse it came from. */
2428 if (dump_file && (dump_flags & TDF_DETAILS))
2429 fprintf (dump_file, "Store matched earlier value,"
2430 "value numbering store vdefs to matching vuses.\n");
2432 def = gimple_vdef (stmt);
2433 use = gimple_vuse (stmt);
2435 VN_INFO (def)->use_processed = true;
2436 changed |= set_ssa_val_to (def, SSA_VAL (use));
2442 /* Visit and value number PHI, return true if the value number
2446 visit_phi (gimple phi)
2448 bool changed = false;
2450 tree sameval = VN_TOP;
2451 bool allsame = true;
2454 /* TODO: We could check for this in init_sccvn, and replace this
2455 with a gcc_assert. */
2456 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
2457 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2459 /* See if all non-TOP arguments have the same value. TOP is
2460 equivalent to everything, so we can ignore it. */
2461 for (i = 0; i < gimple_phi_num_args (phi); i++)
2463 tree def = PHI_ARG_DEF (phi, i);
2465 if (TREE_CODE (def) == SSA_NAME)
2466 def = SSA_VAL (def);
2469 if (sameval == VN_TOP)
2475 if (!expressions_equal_p (def, sameval))
2483 /* If all value numbered to the same value, the phi node has that
2487 if (is_gimple_min_invariant (sameval))
2489 VN_INFO (PHI_RESULT (phi))->has_constants = true;
2490 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2494 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2495 VN_INFO (PHI_RESULT (phi))->expr = sameval;
2498 if (TREE_CODE (sameval) == SSA_NAME)
2499 return visit_copy (PHI_RESULT (phi), sameval);
2501 return set_ssa_val_to (PHI_RESULT (phi), sameval);
2504 /* Otherwise, see if it is equivalent to a phi node in this block. */
2505 result = vn_phi_lookup (phi);
2508 if (TREE_CODE (result) == SSA_NAME)
2509 changed = visit_copy (PHI_RESULT (phi), result);
2511 changed = set_ssa_val_to (PHI_RESULT (phi), result);
2515 vn_phi_insert (phi, PHI_RESULT (phi));
2516 VN_INFO (PHI_RESULT (phi))->has_constants = false;
2517 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
2518 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2524 /* Return true if EXPR contains constants. */
2527 expr_has_constants (tree expr)
2529 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2532 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
2535 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
2536 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
2537 /* Constants inside reference ops are rarely interesting, but
2538 it can take a lot of looking to find them. */
2540 case tcc_declaration:
2543 return is_gimple_min_invariant (expr);
2548 /* Return true if STMT contains constants. */
2551 stmt_has_constants (gimple stmt)
2553 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2556 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2558 case GIMPLE_UNARY_RHS:
2559 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2561 case GIMPLE_BINARY_RHS:
2562 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2563 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
2564 case GIMPLE_TERNARY_RHS:
2565 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2566 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt))
2567 || is_gimple_min_invariant (gimple_assign_rhs3 (stmt)));
2568 case GIMPLE_SINGLE_RHS:
2569 /* Constants inside reference ops are rarely interesting, but
2570 it can take a lot of looking to find them. */
2571 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2578 /* Replace SSA_NAMES in expr with their value numbers, and return the
2580 This is performed in place. */
2583 valueize_expr (tree expr)
2585 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2588 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2589 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2590 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2593 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2594 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2595 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2596 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
2597 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
2598 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
2606 /* Simplify the binary expression RHS, and return the result if
2610 simplify_binary_expression (gimple stmt)
2612 tree result = NULL_TREE;
2613 tree op0 = gimple_assign_rhs1 (stmt);
2614 tree op1 = gimple_assign_rhs2 (stmt);
2616 /* This will not catch every single case we could combine, but will
2617 catch those with constants. The goal here is to simultaneously
2618 combine constants between expressions, but avoid infinite
2619 expansion of expressions during simplification. */
2620 if (TREE_CODE (op0) == SSA_NAME)
2622 if (VN_INFO (op0)->has_constants
2623 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
2624 op0 = valueize_expr (vn_get_expr_for (op0));
2625 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
2626 op0 = SSA_VAL (op0);
2629 if (TREE_CODE (op1) == SSA_NAME)
2631 if (VN_INFO (op1)->has_constants)
2632 op1 = valueize_expr (vn_get_expr_for (op1));
2633 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
2634 op1 = SSA_VAL (op1);
2637 /* Avoid folding if nothing changed. */
2638 if (op0 == gimple_assign_rhs1 (stmt)
2639 && op1 == gimple_assign_rhs2 (stmt))
2642 fold_defer_overflow_warnings ();
2644 result = fold_binary (gimple_assign_rhs_code (stmt),
2645 gimple_expr_type (stmt), op0, op1);
2647 STRIP_USELESS_TYPE_CONVERSION (result);
2649 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2652 /* Make sure result is not a complex expression consisting
2653 of operators of operators (IE (a + b) + (a + c))
2654 Otherwise, we will end up with unbounded expressions if
2655 fold does anything at all. */
2656 if (result && valid_gimple_rhs_p (result))
2662 /* Simplify the unary expression RHS, and return the result if
2666 simplify_unary_expression (gimple stmt)
2668 tree result = NULL_TREE;
2669 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2671 /* We handle some tcc_reference codes here that are all
2672 GIMPLE_ASSIGN_SINGLE codes. */
2673 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2674 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2675 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2676 op0 = TREE_OPERAND (op0, 0);
2678 if (TREE_CODE (op0) != SSA_NAME)
2682 if (VN_INFO (op0)->has_constants)
2683 op0 = valueize_expr (vn_get_expr_for (op0));
2684 else if (gimple_assign_cast_p (stmt)
2685 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2686 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2687 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2689 /* We want to do tree-combining on conversion-like expressions.
2690 Make sure we feed only SSA_NAMEs or constants to fold though. */
2691 tree tem = valueize_expr (vn_get_expr_for (op0));
2692 if (UNARY_CLASS_P (tem)
2693 || BINARY_CLASS_P (tem)
2694 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2695 || TREE_CODE (tem) == SSA_NAME
2696 || is_gimple_min_invariant (tem))
2700 /* Avoid folding if nothing changed, but remember the expression. */
2701 if (op0 == orig_op0)
2704 result = fold_unary_ignore_overflow (gimple_assign_rhs_code (stmt),
2705 gimple_expr_type (stmt), op0);
2708 STRIP_USELESS_TYPE_CONVERSION (result);
2709 if (valid_gimple_rhs_p (result))
2716 /* Try to simplify RHS using equivalences and constant folding. */
2719 try_to_simplify (gimple stmt)
2723 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2724 in this case, there is no point in doing extra work. */
2725 if (gimple_assign_copy_p (stmt)
2726 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2729 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2731 case tcc_declaration:
2732 tem = get_symbol_constant_value (gimple_assign_rhs1 (stmt));
2738 /* Do not do full-blown reference lookup here, but simplify
2739 reads from constant aggregates. */
2740 tem = fold_const_aggregate_ref (gimple_assign_rhs1 (stmt));
2744 /* Fallthrough for some codes that can operate on registers. */
2745 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2746 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2747 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2749 /* We could do a little more with unary ops, if they expand
2750 into binary ops, but it's debatable whether it is worth it. */
2752 return simplify_unary_expression (stmt);
2754 case tcc_comparison:
2756 return simplify_binary_expression (stmt);
2765 /* Visit and value number USE, return true if the value number
2769 visit_use (tree use)
2771 bool changed = false;
2772 gimple stmt = SSA_NAME_DEF_STMT (use);
2774 VN_INFO (use)->use_processed = true;
2776 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
2777 if (dump_file && (dump_flags & TDF_DETAILS)
2778 && !SSA_NAME_IS_DEFAULT_DEF (use))
2780 fprintf (dump_file, "Value numbering ");
2781 print_generic_expr (dump_file, use, 0);
2782 fprintf (dump_file, " stmt = ");
2783 print_gimple_stmt (dump_file, stmt, 0, 0);
2786 /* Handle uninitialized uses. */
2787 if (SSA_NAME_IS_DEFAULT_DEF (use))
2788 changed = set_ssa_val_to (use, use);
2791 if (gimple_code (stmt) == GIMPLE_PHI)
2792 changed = visit_phi (stmt);
2793 else if (!gimple_has_lhs (stmt)
2794 || gimple_has_volatile_ops (stmt)
2795 || stmt_could_throw_p (stmt))
2796 changed = defs_to_varying (stmt);
2797 else if (is_gimple_assign (stmt))
2799 tree lhs = gimple_assign_lhs (stmt);
2802 /* Shortcut for copies. Simplifying copies is pointless,
2803 since we copy the expression and value they represent. */
2804 if (gimple_assign_copy_p (stmt)
2805 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2806 && TREE_CODE (lhs) == SSA_NAME)
2808 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
2811 simplified = try_to_simplify (stmt);
2814 if (dump_file && (dump_flags & TDF_DETAILS))
2816 fprintf (dump_file, "RHS ");
2817 print_gimple_expr (dump_file, stmt, 0, 0);
2818 fprintf (dump_file, " simplified to ");
2819 print_generic_expr (dump_file, simplified, 0);
2820 if (TREE_CODE (lhs) == SSA_NAME)
2821 fprintf (dump_file, " has constants %d\n",
2822 expr_has_constants (simplified));
2824 fprintf (dump_file, "\n");
2827 /* Setting value numbers to constants will occasionally
2828 screw up phi congruence because constants are not
2829 uniquely associated with a single ssa name that can be
2832 && is_gimple_min_invariant (simplified)
2833 && TREE_CODE (lhs) == SSA_NAME)
2835 VN_INFO (lhs)->expr = simplified;
2836 VN_INFO (lhs)->has_constants = true;
2837 changed = set_ssa_val_to (lhs, simplified);
2841 && TREE_CODE (simplified) == SSA_NAME
2842 && TREE_CODE (lhs) == SSA_NAME)
2844 changed = visit_copy (lhs, simplified);
2847 else if (simplified)
2849 if (TREE_CODE (lhs) == SSA_NAME)
2851 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
2852 /* We have to unshare the expression or else
2853 valuizing may change the IL stream. */
2854 VN_INFO (lhs)->expr = unshare_expr (simplified);
2857 else if (stmt_has_constants (stmt)
2858 && TREE_CODE (lhs) == SSA_NAME)
2859 VN_INFO (lhs)->has_constants = true;
2860 else if (TREE_CODE (lhs) == SSA_NAME)
2862 /* We reset expr and constantness here because we may
2863 have been value numbering optimistically, and
2864 iterating. They may become non-constant in this case,
2865 even if they were optimistically constant. */
2867 VN_INFO (lhs)->has_constants = false;
2868 VN_INFO (lhs)->expr = NULL_TREE;
2871 if ((TREE_CODE (lhs) == SSA_NAME
2872 /* We can substitute SSA_NAMEs that are live over
2873 abnormal edges with their constant value. */
2874 && !(gimple_assign_copy_p (stmt)
2875 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2877 && is_gimple_min_invariant (simplified))
2878 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2879 /* Stores or copies from SSA_NAMEs that are live over
2880 abnormal edges are a problem. */
2881 || (gimple_assign_single_p (stmt)
2882 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2883 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))))
2884 changed = defs_to_varying (stmt);
2885 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
2887 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
2889 else if (TREE_CODE (lhs) == SSA_NAME)
2891 if ((gimple_assign_copy_p (stmt)
2892 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2894 && is_gimple_min_invariant (simplified)))
2896 VN_INFO (lhs)->has_constants = true;
2898 changed = set_ssa_val_to (lhs, simplified);
2900 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
2904 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2906 case GIMPLE_UNARY_RHS:
2907 changed = visit_unary_op (lhs, stmt);
2909 case GIMPLE_BINARY_RHS:
2910 changed = visit_binary_op (lhs, stmt);
2912 case GIMPLE_SINGLE_RHS:
2913 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2916 /* VOP-less references can go through unary case. */
2917 if ((gimple_assign_rhs_code (stmt) == REALPART_EXPR
2918 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2919 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR )
2920 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (stmt), 0)) == SSA_NAME)
2922 changed = visit_unary_op (lhs, stmt);
2926 case tcc_declaration:
2927 changed = visit_reference_op_load
2928 (lhs, gimple_assign_rhs1 (stmt), stmt);
2930 case tcc_expression:
2931 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
2933 changed = visit_unary_op (lhs, stmt);
2938 changed = defs_to_varying (stmt);
2942 changed = defs_to_varying (stmt);
2948 changed = defs_to_varying (stmt);
2950 else if (is_gimple_call (stmt))
2952 tree lhs = gimple_call_lhs (stmt);
2954 /* ??? We could try to simplify calls. */
2956 if (stmt_has_constants (stmt)
2957 && TREE_CODE (lhs) == SSA_NAME)
2958 VN_INFO (lhs)->has_constants = true;
2959 else if (TREE_CODE (lhs) == SSA_NAME)
2961 /* We reset expr and constantness here because we may
2962 have been value numbering optimistically, and
2963 iterating. They may become non-constant in this case,
2964 even if they were optimistically constant. */
2965 VN_INFO (lhs)->has_constants = false;
2966 VN_INFO (lhs)->expr = NULL_TREE;
2969 if (TREE_CODE (lhs) == SSA_NAME
2970 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2971 changed = defs_to_varying (stmt);
2972 /* ??? We should handle stores from calls. */
2973 else if (TREE_CODE (lhs) == SSA_NAME)
2975 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2976 changed = visit_reference_op_call (lhs, stmt);
2978 changed = defs_to_varying (stmt);
2981 changed = defs_to_varying (stmt);
2988 /* Compare two operands by reverse postorder index */
2991 compare_ops (const void *pa, const void *pb)
2993 const tree opa = *((const tree *)pa);
2994 const tree opb = *((const tree *)pb);
2995 gimple opstmta = SSA_NAME_DEF_STMT (opa);
2996 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3000 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3001 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3002 else if (gimple_nop_p (opstmta))
3004 else if (gimple_nop_p (opstmtb))
3007 bba = gimple_bb (opstmta);
3008 bbb = gimple_bb (opstmtb);
3011 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3019 if (gimple_code (opstmta) == GIMPLE_PHI
3020 && gimple_code (opstmtb) == GIMPLE_PHI)
3021 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3022 else if (gimple_code (opstmta) == GIMPLE_PHI)
3024 else if (gimple_code (opstmtb) == GIMPLE_PHI)
3026 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3027 return gimple_uid (opstmta) - gimple_uid (opstmtb);
3029 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3031 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3034 /* Sort an array containing members of a strongly connected component
3035 SCC so that the members are ordered by RPO number.
3036 This means that when the sort is complete, iterating through the
3037 array will give you the members in RPO order. */
3040 sort_scc (VEC (tree, heap) *scc)
3042 qsort (VEC_address (tree, scc),
3043 VEC_length (tree, scc),
3048 /* Insert the no longer used nary ONARY to the hash INFO. */
3051 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3053 size_t size = (sizeof (struct vn_nary_op_s)
3054 - sizeof (tree) * (4 - onary->length));
3055 vn_nary_op_t nary = (vn_nary_op_t) obstack_alloc (&info->nary_obstack, size);
3057 memcpy (nary, onary, size);
3058 slot = htab_find_slot_with_hash (info->nary, nary, nary->hashcode, INSERT);
3059 gcc_assert (!*slot);
3063 /* Insert the no longer used phi OPHI to the hash INFO. */
3066 copy_phi (vn_phi_t ophi, vn_tables_t info)
3068 vn_phi_t phi = (vn_phi_t) pool_alloc (info->phis_pool);
3070 memcpy (phi, ophi, sizeof (*phi));
3071 ophi->phiargs = NULL;
3072 slot = htab_find_slot_with_hash (info->phis, phi, phi->hashcode, INSERT);
3073 gcc_assert (!*slot);
3077 /* Insert the no longer used reference OREF to the hash INFO. */
3080 copy_reference (vn_reference_t oref, vn_tables_t info)
3084 ref = (vn_reference_t) pool_alloc (info->references_pool);
3085 memcpy (ref, oref, sizeof (*ref));
3086 oref->operands = NULL;
3087 slot = htab_find_slot_with_hash (info->references, ref, ref->hashcode,
3090 free_reference (*slot);
3094 /* Process a strongly connected component in the SSA graph. */
3097 process_scc (VEC (tree, heap) *scc)
3101 unsigned int iterations = 0;
3102 bool changed = true;
3108 /* If the SCC has a single member, just visit it. */
3109 if (VEC_length (tree, scc) == 1)
3111 tree use = VEC_index (tree, scc, 0);
3112 if (!VN_INFO (use)->use_processed)
3117 /* Iterate over the SCC with the optimistic table until it stops
3119 current_info = optimistic_info;
3124 /* As we are value-numbering optimistically we have to
3125 clear the expression tables and the simplified expressions
3126 in each iteration until we converge. */
3127 htab_empty (optimistic_info->nary);
3128 htab_empty (optimistic_info->phis);
3129 htab_empty (optimistic_info->references);
3130 obstack_free (&optimistic_info->nary_obstack, NULL);
3131 gcc_obstack_init (&optimistic_info->nary_obstack);
3132 empty_alloc_pool (optimistic_info->phis_pool);
3133 empty_alloc_pool (optimistic_info->references_pool);
3134 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
3135 VN_INFO (var)->expr = NULL_TREE;
3136 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
3137 changed |= visit_use (var);
3140 statistics_histogram_event (cfun, "SCC iterations", iterations);
3142 /* Finally, copy the contents of the no longer used optimistic
3143 table to the valid table. */
3144 FOR_EACH_HTAB_ELEMENT (optimistic_info->nary, nary, vn_nary_op_t, hi)
3145 copy_nary (nary, valid_info);
3146 FOR_EACH_HTAB_ELEMENT (optimistic_info->phis, phi, vn_phi_t, hi)
3147 copy_phi (phi, valid_info);
3148 FOR_EACH_HTAB_ELEMENT (optimistic_info->references, ref, vn_reference_t, hi)
3149 copy_reference (ref, valid_info);
3151 current_info = valid_info;
3154 DEF_VEC_O(ssa_op_iter);
3155 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
3157 /* Pop the components of the found SCC for NAME off the SCC stack
3158 and process them. Returns true if all went well, false if
3159 we run into resource limits. */
3162 extract_and_process_scc_for_name (tree name)
3164 VEC (tree, heap) *scc = NULL;
3167 /* Found an SCC, pop the components off the SCC stack and
3171 x = VEC_pop (tree, sccstack);
3173 VN_INFO (x)->on_sccstack = false;
3174 VEC_safe_push (tree, heap, scc, x);
3175 } while (x != name);
3177 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3178 if (VEC_length (tree, scc)
3179 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
3182 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
3183 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
3184 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
3188 if (VEC_length (tree, scc) > 1)
3191 if (dump_file && (dump_flags & TDF_DETAILS))
3192 print_scc (dump_file, scc);
3196 VEC_free (tree, heap, scc);
3201 /* Depth first search on NAME to discover and process SCC's in the SSA
3203 Execution of this algorithm relies on the fact that the SCC's are
3204 popped off the stack in topological order.
3205 Returns true if successful, false if we stopped processing SCC's due
3206 to resource constraints. */
3211 VEC(ssa_op_iter, heap) *itervec = NULL;
3212 VEC(tree, heap) *namevec = NULL;
3213 use_operand_p usep = NULL;
3220 VN_INFO (name)->dfsnum = next_dfs_num++;
3221 VN_INFO (name)->visited = true;
3222 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
3224 VEC_safe_push (tree, heap, sccstack, name);
3225 VN_INFO (name)->on_sccstack = true;
3226 defstmt = SSA_NAME_DEF_STMT (name);
3228 /* Recursively DFS on our operands, looking for SCC's. */
3229 if (!gimple_nop_p (defstmt))
3231 /* Push a new iterator. */
3232 if (gimple_code (defstmt) == GIMPLE_PHI)
3233 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
3235 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
3238 clear_and_done_ssa_iter (&iter);
3242 /* If we are done processing uses of a name, go up the stack
3243 of iterators and process SCCs as we found them. */
3244 if (op_iter_done (&iter))
3246 /* See if we found an SCC. */
3247 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
3248 if (!extract_and_process_scc_for_name (name))
3250 VEC_free (tree, heap, namevec);
3251 VEC_free (ssa_op_iter, heap, itervec);
3255 /* Check if we are done. */
3256 if (VEC_empty (tree, namevec))
3258 VEC_free (tree, heap, namevec);
3259 VEC_free (ssa_op_iter, heap, itervec);
3263 /* Restore the last use walker and continue walking there. */
3265 name = VEC_pop (tree, namevec);
3266 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
3267 sizeof (ssa_op_iter));
3268 VEC_pop (ssa_op_iter, itervec);
3269 goto continue_walking;
3272 use = USE_FROM_PTR (usep);
3274 /* Since we handle phi nodes, we will sometimes get
3275 invariants in the use expression. */
3276 if (TREE_CODE (use) == SSA_NAME)
3278 if (! (VN_INFO (use)->visited))
3280 /* Recurse by pushing the current use walking state on
3281 the stack and starting over. */
3282 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
3283 VEC_safe_push(tree, heap, namevec, name);
3288 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
3289 VN_INFO (use)->low);
3291 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
3292 && VN_INFO (use)->on_sccstack)
3294 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
3295 VN_INFO (name)->low);
3299 usep = op_iter_next_use (&iter);
3303 /* Allocate a value number table. */
3306 allocate_vn_table (vn_tables_t table)
3308 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
3309 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
3310 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
3313 gcc_obstack_init (&table->nary_obstack);
3314 table->phis_pool = create_alloc_pool ("VN phis",
3315 sizeof (struct vn_phi_s),
3317 table->references_pool = create_alloc_pool ("VN references",
3318 sizeof (struct vn_reference_s),
3322 /* Free a value number table. */
3325 free_vn_table (vn_tables_t table)
3327 htab_delete (table->phis);
3328 htab_delete (table->nary);
3329 htab_delete (table->references);
3330 obstack_free (&table->nary_obstack, NULL);
3331 free_alloc_pool (table->phis_pool);
3332 free_alloc_pool (table->references_pool);
3340 int *rpo_numbers_temp;
3342 calculate_dominance_info (CDI_DOMINATORS);
3344 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
3347 constant_value_ids = BITMAP_ALLOC (NULL);
3352 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
3353 /* VEC_alloc doesn't actually grow it to the right size, it just
3354 preallocates the space to do so. */
3355 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
3356 gcc_obstack_init (&vn_ssa_aux_obstack);
3358 shared_lookup_phiargs = NULL;
3359 shared_lookup_references = NULL;
3360 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3361 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
3362 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
3364 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3365 the i'th block in RPO order is bb. We want to map bb's to RPO
3366 numbers, so we need to rearrange this array. */
3367 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
3368 rpo_numbers[rpo_numbers_temp[j]] = j;
3370 XDELETE (rpo_numbers_temp);
3372 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
3374 /* Create the VN_INFO structures, and initialize value numbers to
3376 for (i = 0; i < num_ssa_names; i++)
3378 tree name = ssa_name (i);
3381 VN_INFO_GET (name)->valnum = VN_TOP;
3382 VN_INFO (name)->expr = NULL_TREE;
3383 VN_INFO (name)->value_id = 0;
3387 renumber_gimple_stmt_uids ();
3389 /* Create the valid and optimistic value numbering tables. */
3390 valid_info = XCNEW (struct vn_tables_s);
3391 allocate_vn_table (valid_info);
3392 optimistic_info = XCNEW (struct vn_tables_s);
3393 allocate_vn_table (optimistic_info);
3401 htab_delete (constant_to_value_id);
3402 BITMAP_FREE (constant_value_ids);
3403 VEC_free (tree, heap, shared_lookup_phiargs);
3404 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
3405 XDELETEVEC (rpo_numbers);
3407 for (i = 0; i < num_ssa_names; i++)
3409 tree name = ssa_name (i);
3411 && VN_INFO (name)->needs_insertion)
3412 release_ssa_name (name);
3414 obstack_free (&vn_ssa_aux_obstack, NULL);
3415 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
3417 VEC_free (tree, heap, sccstack);
3418 free_vn_table (valid_info);
3419 XDELETE (valid_info);
3420 free_vn_table (optimistic_info);
3421 XDELETE (optimistic_info);
3424 /* Set the value ids in the valid hash tables. */
3427 set_hashtable_value_ids (void)
3434 /* Now set the value ids of the things we had put in the hash
3437 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
3438 vno, vn_nary_op_t, hi)
3442 if (TREE_CODE (vno->result) == SSA_NAME)
3443 vno->value_id = VN_INFO (vno->result)->value_id;
3444 else if (is_gimple_min_invariant (vno->result))
3445 vno->value_id = get_or_alloc_constant_value_id (vno->result);
3449 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
3454 if (TREE_CODE (vp->result) == SSA_NAME)
3455 vp->value_id = VN_INFO (vp->result)->value_id;
3456 else if (is_gimple_min_invariant (vp->result))
3457 vp->value_id = get_or_alloc_constant_value_id (vp->result);
3461 FOR_EACH_HTAB_ELEMENT (valid_info->references,
3462 vr, vn_reference_t, hi)
3466 if (TREE_CODE (vr->result) == SSA_NAME)
3467 vr->value_id = VN_INFO (vr->result)->value_id;
3468 else if (is_gimple_min_invariant (vr->result))
3469 vr->value_id = get_or_alloc_constant_value_id (vr->result);
3474 /* Do SCCVN. Returns true if it finished, false if we bailed out
3475 due to resource constraints. */
3482 bool changed = true;
3485 current_info = valid_info;
3487 for (param = DECL_ARGUMENTS (current_function_decl);
3489 param = DECL_CHAIN (param))
3491 if (gimple_default_def (cfun, param) != NULL)
3493 tree def = gimple_default_def (cfun, param);
3494 VN_INFO (def)->valnum = def;
3498 for (i = 1; i < num_ssa_names; ++i)
3500 tree name = ssa_name (i);
3502 && VN_INFO (name)->visited == false
3503 && !has_zero_uses (name))
3511 /* Initialize the value ids. */
3513 for (i = 1; i < num_ssa_names; ++i)
3515 tree name = ssa_name (i);
3519 info = VN_INFO (name);
3520 if (info->valnum == name
3521 || info->valnum == VN_TOP)
3522 info->value_id = get_next_value_id ();
3523 else if (is_gimple_min_invariant (info->valnum))
3524 info->value_id = get_or_alloc_constant_value_id (info->valnum);
3527 /* Propagate until they stop changing. */
3531 for (i = 1; i < num_ssa_names; ++i)
3533 tree name = ssa_name (i);
3537 info = VN_INFO (name);
3538 if (TREE_CODE (info->valnum) == SSA_NAME
3539 && info->valnum != name
3540 && info->value_id != VN_INFO (info->valnum)->value_id)
3543 info->value_id = VN_INFO (info->valnum)->value_id;
3548 set_hashtable_value_ids ();
3550 if (dump_file && (dump_flags & TDF_DETAILS))
3552 fprintf (dump_file, "Value numbers:\n");
3553 for (i = 0; i < num_ssa_names; i++)
3555 tree name = ssa_name (i);
3557 && VN_INFO (name)->visited
3558 && SSA_VAL (name) != name)
3560 print_generic_expr (dump_file, name, 0);
3561 fprintf (dump_file, " = ");
3562 print_generic_expr (dump_file, SSA_VAL (name), 0);
3563 fprintf (dump_file, "\n");
3571 /* Return the maximum value id we have ever seen. */
3574 get_max_value_id (void)
3576 return next_value_id;
3579 /* Return the next unique value id. */
3582 get_next_value_id (void)
3584 return next_value_id++;
3588 /* Compare two expressions E1 and E2 and return true if they are equal. */
3591 expressions_equal_p (tree e1, tree e2)
3593 /* The obvious case. */
3597 /* If only one of them is null, they cannot be equal. */
3601 /* Now perform the actual comparison. */
3602 if (TREE_CODE (e1) == TREE_CODE (e2)
3603 && operand_equal_p (e1, e2, OEP_PURE_SAME))
3610 /* Return true if the nary operation NARY may trap. This is a copy
3611 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
3614 vn_nary_may_trap (vn_nary_op_t nary)
3617 tree rhs2 = NULL_TREE;
3618 bool honor_nans = false;
3619 bool honor_snans = false;
3620 bool fp_operation = false;
3621 bool honor_trapv = false;
3625 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
3626 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
3627 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
3630 fp_operation = FLOAT_TYPE_P (type);
3633 honor_nans = flag_trapping_math && !flag_finite_math_only;
3634 honor_snans = flag_signaling_nans != 0;
3636 else if (INTEGRAL_TYPE_P (type)
3637 && TYPE_OVERFLOW_TRAPS (type))
3640 if (nary->length >= 2)
3642 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
3644 honor_nans, honor_snans, rhs2,
3650 for (i = 0; i < nary->length; ++i)
3651 if (tree_could_trap_p (nary->op[i]))