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 "gimple-pretty-print.h"
29 #include "tree-inline.h"
30 #include "tree-flow.h"
34 #include "alloc-pool.h"
39 #include "tree-ssa-propagate.h"
40 #include "tree-ssa-sccvn.h"
41 #include "gimple-fold.h"
43 /* This algorithm is based on the SCC algorithm presented by Keith
44 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
45 (http://citeseer.ist.psu.edu/41805.html). In
46 straight line code, it is equivalent to a regular hash based value
47 numbering that is performed in reverse postorder.
49 For code with cycles, there are two alternatives, both of which
50 require keeping the hashtables separate from the actual list of
51 value numbers for SSA names.
53 1. Iterate value numbering in an RPO walk of the blocks, removing
54 all the entries from the hashtable after each iteration (but
55 keeping the SSA name->value number mapping between iterations).
56 Iterate until it does not change.
58 2. Perform value numbering as part of an SCC walk on the SSA graph,
59 iterating only the cycles in the SSA graph until they do not change
60 (using a separate, optimistic hashtable for value numbering the SCC
63 The second is not just faster in practice (because most SSA graph
64 cycles do not involve all the variables in the graph), it also has
67 One of these nice properties is that when we pop an SCC off the
68 stack, we are guaranteed to have processed all the operands coming from
69 *outside of that SCC*, so we do not need to do anything special to
70 ensure they have value numbers.
72 Another nice property is that the SCC walk is done as part of a DFS
73 of the SSA graph, which makes it easy to perform combining and
74 simplifying operations at the same time.
76 The code below is deliberately written in a way that makes it easy
77 to separate the SCC walk from the other work it does.
79 In order to propagate constants through the code, we track which
80 expressions contain constants, and use those while folding. In
81 theory, we could also track expressions whose value numbers are
82 replaced, in case we end up folding based on expression
85 In order to value number memory, we assign value numbers to vuses.
86 This enables us to note that, for example, stores to the same
87 address of the same value from the same starting memory states are
91 1. We can iterate only the changing portions of the SCC's, but
92 I have not seen an SCC big enough for this to be a win.
93 2. If you differentiate between phi nodes for loops and phi nodes
94 for if-then-else, you can properly consider phi nodes in different
95 blocks for equivalence.
96 3. We could value number vuses in more cases, particularly, whole
100 /* The set of hashtables and alloc_pool's for their items. */
102 typedef struct vn_tables_s
107 struct obstack nary_obstack
;
108 alloc_pool phis_pool
;
109 alloc_pool references_pool
;
112 static htab_t constant_to_value_id
;
113 static bitmap constant_value_ids
;
116 /* Valid hashtables storing information we have proven to be
119 static vn_tables_t valid_info
;
121 /* Optimistic hashtables storing information we are making assumptions about
122 during iterations. */
124 static vn_tables_t optimistic_info
;
126 /* Pointer to the set of hashtables that is currently being used.
127 Should always point to either the optimistic_info, or the
130 static vn_tables_t current_info
;
133 /* Reverse post order index for each basic block. */
135 static int *rpo_numbers
;
137 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
139 /* This represents the top of the VN lattice, which is the universal
144 /* Unique counter for our value ids. */
146 static unsigned int next_value_id
;
148 /* Next DFS number and the stack for strongly connected component
151 static unsigned int next_dfs_num
;
152 static VEC (tree
, heap
) *sccstack
;
155 DEF_VEC_P(vn_ssa_aux_t
);
156 DEF_VEC_ALLOC_P(vn_ssa_aux_t
, heap
);
158 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
159 are allocated on an obstack for locality reasons, and to free them
160 without looping over the VEC. */
162 static VEC (vn_ssa_aux_t
, heap
) *vn_ssa_aux_table
;
163 static struct obstack vn_ssa_aux_obstack
;
165 /* Return the value numbering information for a given SSA name. */
170 vn_ssa_aux_t res
= VEC_index (vn_ssa_aux_t
, vn_ssa_aux_table
,
171 SSA_NAME_VERSION (name
));
172 gcc_checking_assert (res
);
176 /* Set the value numbering info for a given SSA name to a given
180 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
182 VEC_replace (vn_ssa_aux_t
, vn_ssa_aux_table
,
183 SSA_NAME_VERSION (name
), value
);
186 /* Initialize the value numbering info for a given SSA name.
187 This should be called just once for every SSA name. */
190 VN_INFO_GET (tree name
)
192 vn_ssa_aux_t newinfo
;
194 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
195 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
196 if (SSA_NAME_VERSION (name
) >= VEC_length (vn_ssa_aux_t
, vn_ssa_aux_table
))
197 VEC_safe_grow (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
,
198 SSA_NAME_VERSION (name
) + 1);
199 VEC_replace (vn_ssa_aux_t
, vn_ssa_aux_table
,
200 SSA_NAME_VERSION (name
), newinfo
);
205 /* Get the representative expression for the SSA_NAME NAME. Returns
206 the representative SSA_NAME if there is no expression associated with it. */
209 vn_get_expr_for (tree name
)
211 vn_ssa_aux_t vn
= VN_INFO (name
);
213 tree expr
= NULL_TREE
;
216 if (vn
->valnum
== VN_TOP
)
219 /* If the value-number is a constant it is the representative
221 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
224 /* Get to the information of the value of this SSA_NAME. */
225 vn
= VN_INFO (vn
->valnum
);
227 /* If the value-number is a constant it is the representative
229 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
232 /* Else if we have an expression, return it. */
233 if (vn
->expr
!= NULL_TREE
)
236 /* Otherwise use the defining statement to build the expression. */
237 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
239 /* If the value number is not an assignment use it directly. */
240 if (!is_gimple_assign (def_stmt
))
243 /* FIXME tuples. This is incomplete and likely will miss some
245 code
= gimple_assign_rhs_code (def_stmt
);
246 switch (TREE_CODE_CLASS (code
))
249 if ((code
== REALPART_EXPR
250 || code
== IMAGPART_EXPR
251 || code
== VIEW_CONVERT_EXPR
)
252 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
254 expr
= fold_build1 (code
,
255 gimple_expr_type (def_stmt
),
256 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
260 expr
= fold_build1 (code
,
261 gimple_expr_type (def_stmt
),
262 gimple_assign_rhs1 (def_stmt
));
266 expr
= fold_build2 (code
,
267 gimple_expr_type (def_stmt
),
268 gimple_assign_rhs1 (def_stmt
),
269 gimple_assign_rhs2 (def_stmt
));
272 case tcc_exceptional
:
273 if (code
== CONSTRUCTOR
275 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
276 expr
= gimple_assign_rhs1 (def_stmt
);
281 if (expr
== NULL_TREE
)
284 /* Cache the expression. */
290 /* Return the vn_kind the expression computed by the stmt should be
294 vn_get_stmt_kind (gimple stmt
)
296 switch (gimple_code (stmt
))
304 enum tree_code code
= gimple_assign_rhs_code (stmt
);
305 tree rhs1
= gimple_assign_rhs1 (stmt
);
306 switch (get_gimple_rhs_class (code
))
308 case GIMPLE_UNARY_RHS
:
309 case GIMPLE_BINARY_RHS
:
310 case GIMPLE_TERNARY_RHS
:
312 case GIMPLE_SINGLE_RHS
:
313 switch (TREE_CODE_CLASS (code
))
316 /* VOP-less references can go through unary case. */
317 if ((code
== REALPART_EXPR
318 || code
== IMAGPART_EXPR
319 || code
== VIEW_CONVERT_EXPR
320 || code
== BIT_FIELD_REF
)
321 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
325 case tcc_declaration
:
332 if (code
== ADDR_EXPR
)
333 return (is_gimple_min_invariant (rhs1
)
334 ? VN_CONSTANT
: VN_REFERENCE
);
335 else if (code
== CONSTRUCTOR
)
348 /* Free a phi operation structure VP. */
353 vn_phi_t phi
= (vn_phi_t
) vp
;
354 VEC_free (tree
, heap
, phi
->phiargs
);
357 /* Free a reference operation structure VP. */
360 free_reference (void *vp
)
362 vn_reference_t vr
= (vn_reference_t
) vp
;
363 VEC_free (vn_reference_op_s
, heap
, vr
->operands
);
366 /* Hash table equality function for vn_constant_t. */
369 vn_constant_eq (const void *p1
, const void *p2
)
371 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
372 const struct vn_constant_s
*vc2
= (const struct vn_constant_s
*) p2
;
374 if (vc1
->hashcode
!= vc2
->hashcode
)
377 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
380 /* Hash table hash function for vn_constant_t. */
383 vn_constant_hash (const void *p1
)
385 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
386 return vc1
->hashcode
;
389 /* Lookup a value id for CONSTANT and return it. If it does not
393 get_constant_value_id (tree constant
)
396 struct vn_constant_s vc
;
398 vc
.hashcode
= vn_hash_constant_with_type (constant
);
399 vc
.constant
= constant
;
400 slot
= htab_find_slot_with_hash (constant_to_value_id
, &vc
,
401 vc
.hashcode
, NO_INSERT
);
403 return ((vn_constant_t
)*slot
)->value_id
;
407 /* Lookup a value id for CONSTANT, and if it does not exist, create a
408 new one and return it. If it does exist, return it. */
411 get_or_alloc_constant_value_id (tree constant
)
414 struct vn_constant_s vc
;
417 vc
.hashcode
= vn_hash_constant_with_type (constant
);
418 vc
.constant
= constant
;
419 slot
= htab_find_slot_with_hash (constant_to_value_id
, &vc
,
420 vc
.hashcode
, INSERT
);
422 return ((vn_constant_t
)*slot
)->value_id
;
424 vcp
= XNEW (struct vn_constant_s
);
425 vcp
->hashcode
= vc
.hashcode
;
426 vcp
->constant
= constant
;
427 vcp
->value_id
= get_next_value_id ();
428 *slot
= (void *) vcp
;
429 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
430 return vcp
->value_id
;
433 /* Return true if V is a value id for a constant. */
436 value_id_constant_p (unsigned int v
)
438 return bitmap_bit_p (constant_value_ids
, v
);
441 /* Compare two reference operands P1 and P2 for equality. Return true if
442 they are equal, and false otherwise. */
445 vn_reference_op_eq (const void *p1
, const void *p2
)
447 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
448 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
450 return (vro1
->opcode
== vro2
->opcode
451 /* We do not care for differences in type qualification. */
452 && (vro1
->type
== vro2
->type
453 || (vro1
->type
&& vro2
->type
454 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
455 TYPE_MAIN_VARIANT (vro2
->type
))))
456 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
457 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
458 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
461 /* Compute the hash for a reference operand VRO1. */
464 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
466 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
468 result
= iterative_hash_expr (vro1
->op0
, result
);
470 result
= iterative_hash_expr (vro1
->op1
, result
);
472 result
= iterative_hash_expr (vro1
->op2
, result
);
476 /* Return the hashcode for a given reference operation P1. */
479 vn_reference_hash (const void *p1
)
481 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
482 return vr1
->hashcode
;
485 /* Compute a hash for the reference operation VR1 and return it. */
488 vn_reference_compute_hash (const vn_reference_t vr1
)
490 hashval_t result
= 0;
492 vn_reference_op_t vro
;
493 HOST_WIDE_INT off
= -1;
496 FOR_EACH_VEC_ELT (vn_reference_op_s
, vr1
->operands
, i
, vro
)
498 if (vro
->opcode
== MEM_REF
)
500 else if (vro
->opcode
!= ADDR_EXPR
)
512 result
= iterative_hash_hashval_t (off
, result
);
515 && vro
->opcode
== ADDR_EXPR
)
519 tree op
= TREE_OPERAND (vro
->op0
, 0);
520 result
= iterative_hash_hashval_t (TREE_CODE (op
), result
);
521 result
= iterative_hash_expr (op
, result
);
525 result
= vn_reference_op_compute_hash (vro
, result
);
529 result
+= SSA_NAME_VERSION (vr1
->vuse
);
534 /* Return true if reference operations P1 and P2 are equivalent. This
535 means they have the same set of operands and vuses. */
538 vn_reference_eq (const void *p1
, const void *p2
)
542 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
543 const_vn_reference_t
const vr2
= (const_vn_reference_t
) p2
;
544 if (vr1
->hashcode
!= vr2
->hashcode
)
547 /* Early out if this is not a hash collision. */
548 if (vr1
->hashcode
!= vr2
->hashcode
)
551 /* The VOP needs to be the same. */
552 if (vr1
->vuse
!= vr2
->vuse
)
555 /* If the operands are the same we are done. */
556 if (vr1
->operands
== vr2
->operands
)
559 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
562 if (INTEGRAL_TYPE_P (vr1
->type
)
563 && INTEGRAL_TYPE_P (vr2
->type
))
565 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
568 else if (INTEGRAL_TYPE_P (vr1
->type
)
569 && (TYPE_PRECISION (vr1
->type
)
570 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
572 else if (INTEGRAL_TYPE_P (vr2
->type
)
573 && (TYPE_PRECISION (vr2
->type
)
574 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
581 HOST_WIDE_INT off1
= 0, off2
= 0;
582 vn_reference_op_t vro1
, vro2
;
583 vn_reference_op_s tem1
, tem2
;
584 bool deref1
= false, deref2
= false;
585 for (; VEC_iterate (vn_reference_op_s
, vr1
->operands
, i
, vro1
); i
++)
587 if (vro1
->opcode
== MEM_REF
)
593 for (; VEC_iterate (vn_reference_op_s
, vr2
->operands
, j
, vro2
); j
++)
595 if (vro2
->opcode
== MEM_REF
)
603 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
605 memset (&tem1
, 0, sizeof (tem1
));
606 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
607 tem1
.type
= TREE_TYPE (tem1
.op0
);
608 tem1
.opcode
= TREE_CODE (tem1
.op0
);
612 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
614 memset (&tem2
, 0, sizeof (tem2
));
615 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
616 tem2
.type
= TREE_TYPE (tem2
.op0
);
617 tem2
.opcode
= TREE_CODE (tem2
.op0
);
621 if (deref1
!= deref2
)
623 if (!vn_reference_op_eq (vro1
, vro2
))
628 while (VEC_length (vn_reference_op_s
, vr1
->operands
) != i
629 || VEC_length (vn_reference_op_s
, vr2
->operands
) != j
);
634 /* Copy the operations present in load/store REF into RESULT, a vector of
635 vn_reference_op_s's. */
638 copy_reference_ops_from_ref (tree ref
, VEC(vn_reference_op_s
, heap
) **result
)
640 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
642 vn_reference_op_s temp
;
644 memset (&temp
, 0, sizeof (temp
));
645 temp
.type
= TREE_TYPE (ref
);
646 temp
.opcode
= TREE_CODE (ref
);
647 temp
.op0
= TMR_INDEX (ref
);
648 temp
.op1
= TMR_STEP (ref
);
649 temp
.op2
= TMR_OFFSET (ref
);
651 VEC_safe_push (vn_reference_op_s
, heap
, *result
, temp
);
653 memset (&temp
, 0, sizeof (temp
));
654 temp
.type
= NULL_TREE
;
655 temp
.opcode
= ERROR_MARK
;
656 temp
.op0
= TMR_INDEX2 (ref
);
658 VEC_safe_push (vn_reference_op_s
, heap
, *result
, temp
);
660 memset (&temp
, 0, sizeof (temp
));
661 temp
.type
= NULL_TREE
;
662 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
663 temp
.op0
= TMR_BASE (ref
);
665 VEC_safe_push (vn_reference_op_s
, heap
, *result
, temp
);
669 /* For non-calls, store the information that makes up the address. */
673 vn_reference_op_s temp
;
675 memset (&temp
, 0, sizeof (temp
));
676 temp
.type
= TREE_TYPE (ref
);
677 temp
.opcode
= TREE_CODE (ref
);
683 temp
.op0
= TREE_OPERAND (ref
, 1);
686 temp
.op0
= TREE_OPERAND (ref
, 1);
690 /* The base address gets its own vn_reference_op_s structure. */
691 temp
.op0
= TREE_OPERAND (ref
, 1);
692 if (host_integerp (TREE_OPERAND (ref
, 1), 0))
693 temp
.off
= TREE_INT_CST_LOW (TREE_OPERAND (ref
, 1));
696 /* Record bits and position. */
697 temp
.op0
= TREE_OPERAND (ref
, 1);
698 temp
.op1
= TREE_OPERAND (ref
, 2);
701 /* The field decl is enough to unambiguously specify the field,
702 a matching type is not necessary and a mismatching type
703 is always a spurious difference. */
704 temp
.type
= NULL_TREE
;
705 temp
.op0
= TREE_OPERAND (ref
, 1);
706 temp
.op1
= TREE_OPERAND (ref
, 2);
708 tree this_offset
= component_ref_field_offset (ref
);
710 && TREE_CODE (this_offset
) == INTEGER_CST
)
712 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
713 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
716 = tree_to_double_int (this_offset
)
717 + tree_to_double_int (bit_offset
)
718 .arshift (BITS_PER_UNIT
== 8
719 ? 3 : exact_log2 (BITS_PER_UNIT
),
720 HOST_BITS_PER_DOUBLE_INT
);
721 if (off
.fits_shwi ())
727 case ARRAY_RANGE_REF
:
729 /* Record index as operand. */
730 temp
.op0
= TREE_OPERAND (ref
, 1);
731 /* Always record lower bounds and element size. */
732 temp
.op1
= array_ref_low_bound (ref
);
733 temp
.op2
= array_ref_element_size (ref
);
734 if (TREE_CODE (temp
.op0
) == INTEGER_CST
735 && TREE_CODE (temp
.op1
) == INTEGER_CST
736 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
738 double_int off
= tree_to_double_int (temp
.op0
);
739 off
+= -tree_to_double_int (temp
.op1
);
740 off
*= tree_to_double_int (temp
.op2
);
741 if (off
.fits_shwi ())
746 if (DECL_HARD_REGISTER (ref
))
755 /* Canonicalize decls to MEM[&decl] which is what we end up with
756 when valueizing MEM[ptr] with ptr = &decl. */
757 temp
.opcode
= MEM_REF
;
758 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
760 VEC_safe_push (vn_reference_op_s
, heap
, *result
, temp
);
761 temp
.opcode
= ADDR_EXPR
;
762 temp
.op0
= build_fold_addr_expr (ref
);
763 temp
.type
= TREE_TYPE (temp
.op0
);
777 if (is_gimple_min_invariant (ref
))
783 /* These are only interesting for their operands, their
784 existence, and their type. They will never be the last
785 ref in the chain of references (IE they require an
786 operand), so we don't have to put anything
787 for op* as it will be handled by the iteration */
789 case VIEW_CONVERT_EXPR
:
793 /* This is only interesting for its constant offset. */
794 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
799 VEC_safe_push (vn_reference_op_s
, heap
, *result
, temp
);
801 if (REFERENCE_CLASS_P (ref
)
802 || TREE_CODE (ref
) == MODIFY_EXPR
803 || TREE_CODE (ref
) == WITH_SIZE_EXPR
804 || (TREE_CODE (ref
) == ADDR_EXPR
805 && !is_gimple_min_invariant (ref
)))
806 ref
= TREE_OPERAND (ref
, 0);
812 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
813 operands in *OPS, the reference alias set SET and the reference type TYPE.
814 Return true if something useful was produced. */
817 ao_ref_init_from_vn_reference (ao_ref
*ref
,
818 alias_set_type set
, tree type
,
819 VEC (vn_reference_op_s
, heap
) *ops
)
821 vn_reference_op_t op
;
823 tree base
= NULL_TREE
;
825 HOST_WIDE_INT offset
= 0;
826 HOST_WIDE_INT max_size
;
827 HOST_WIDE_INT size
= -1;
828 tree size_tree
= NULL_TREE
;
829 alias_set_type base_alias_set
= -1;
831 /* First get the final access size from just the outermost expression. */
832 op
= &VEC_index (vn_reference_op_s
, ops
, 0);
833 if (op
->opcode
== COMPONENT_REF
)
834 size_tree
= DECL_SIZE (op
->op0
);
835 else if (op
->opcode
== BIT_FIELD_REF
)
839 enum machine_mode mode
= TYPE_MODE (type
);
841 size_tree
= TYPE_SIZE (type
);
843 size
= GET_MODE_BITSIZE (mode
);
845 if (size_tree
!= NULL_TREE
)
847 if (!host_integerp (size_tree
, 1))
850 size
= TREE_INT_CST_LOW (size_tree
);
853 /* Initially, maxsize is the same as the accessed element size.
854 In the following it will only grow (or become -1). */
857 /* Compute cumulative bit-offset for nested component-refs and array-refs,
858 and find the ultimate containing object. */
859 FOR_EACH_VEC_ELT (vn_reference_op_s
, ops
, i
, op
)
863 /* These may be in the reference ops, but we cannot do anything
864 sensible with them here. */
866 /* Apart from ADDR_EXPR arguments to MEM_REF. */
867 if (base
!= NULL_TREE
868 && TREE_CODE (base
) == MEM_REF
870 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
872 vn_reference_op_t pop
= &VEC_index (vn_reference_op_s
, ops
, i
-1);
873 base
= TREE_OPERAND (op
->op0
, 0);
880 offset
+= pop
->off
* BITS_PER_UNIT
;
888 /* Record the base objects. */
890 base_alias_set
= get_deref_alias_set (op
->op0
);
891 *op0_p
= build2 (MEM_REF
, op
->type
,
893 op0_p
= &TREE_OPERAND (*op0_p
, 0);
904 /* And now the usual component-reference style ops. */
906 offset
+= tree_low_cst (op
->op1
, 0);
911 tree field
= op
->op0
;
912 /* We do not have a complete COMPONENT_REF tree here so we
913 cannot use component_ref_field_offset. Do the interesting
917 || !host_integerp (DECL_FIELD_OFFSET (field
), 1))
921 offset
+= (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field
))
923 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
928 case ARRAY_RANGE_REF
:
930 /* We recorded the lower bound and the element size. */
931 if (!host_integerp (op
->op0
, 0)
932 || !host_integerp (op
->op1
, 0)
933 || !host_integerp (op
->op2
, 0))
937 HOST_WIDE_INT hindex
= TREE_INT_CST_LOW (op
->op0
);
938 hindex
-= TREE_INT_CST_LOW (op
->op1
);
939 hindex
*= TREE_INT_CST_LOW (op
->op2
);
940 hindex
*= BITS_PER_UNIT
;
952 case VIEW_CONVERT_EXPR
:
969 if (base
== NULL_TREE
)
972 ref
->ref
= NULL_TREE
;
974 ref
->offset
= offset
;
976 ref
->max_size
= max_size
;
977 ref
->ref_alias_set
= set
;
978 if (base_alias_set
!= -1)
979 ref
->base_alias_set
= base_alias_set
;
981 ref
->base_alias_set
= get_alias_set (base
);
982 /* We discount volatiles from value-numbering elsewhere. */
983 ref
->volatile_p
= false;
988 /* Copy the operations present in load/store/call REF into RESULT, a vector of
989 vn_reference_op_s's. */
992 copy_reference_ops_from_call (gimple call
,
993 VEC(vn_reference_op_s
, heap
) **result
)
995 vn_reference_op_s temp
;
997 tree lhs
= gimple_call_lhs (call
);
999 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1000 different. By adding the lhs here in the vector, we ensure that the
1001 hashcode is different, guaranteeing a different value number. */
1002 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1004 memset (&temp
, 0, sizeof (temp
));
1005 temp
.opcode
= MODIFY_EXPR
;
1006 temp
.type
= TREE_TYPE (lhs
);
1009 VEC_safe_push (vn_reference_op_s
, heap
, *result
, temp
);
1012 /* Copy the type, opcode, function being called and static chain. */
1013 memset (&temp
, 0, sizeof (temp
));
1014 temp
.type
= gimple_call_return_type (call
);
1015 temp
.opcode
= CALL_EXPR
;
1016 temp
.op0
= gimple_call_fn (call
);
1017 temp
.op1
= gimple_call_chain (call
);
1019 VEC_safe_push (vn_reference_op_s
, heap
, *result
, temp
);
1021 /* Copy the call arguments. As they can be references as well,
1022 just chain them together. */
1023 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1025 tree callarg
= gimple_call_arg (call
, i
);
1026 copy_reference_ops_from_ref (callarg
, result
);
1030 /* Create a vector of vn_reference_op_s structures from REF, a
1031 REFERENCE_CLASS_P tree. The vector is not shared. */
1033 static VEC(vn_reference_op_s
, heap
) *
1034 create_reference_ops_from_ref (tree ref
)
1036 VEC (vn_reference_op_s
, heap
) *result
= NULL
;
1038 copy_reference_ops_from_ref (ref
, &result
);
1042 /* Create a vector of vn_reference_op_s structures from CALL, a
1043 call statement. The vector is not shared. */
1045 static VEC(vn_reference_op_s
, heap
) *
1046 create_reference_ops_from_call (gimple call
)
1048 VEC (vn_reference_op_s
, heap
) *result
= NULL
;
1050 copy_reference_ops_from_call (call
, &result
);
1054 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1055 *I_P to point to the last element of the replacement. */
1057 vn_reference_fold_indirect (VEC (vn_reference_op_s
, heap
) **ops
,
1060 unsigned int i
= *i_p
;
1061 vn_reference_op_t op
= &VEC_index (vn_reference_op_s
, *ops
, i
);
1062 vn_reference_op_t mem_op
= &VEC_index (vn_reference_op_s
, *ops
, i
- 1);
1064 HOST_WIDE_INT addr_offset
= 0;
1066 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1067 from .foo.bar to the preceding MEM_REF offset and replace the
1068 address with &OBJ. */
1069 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1071 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1072 if (addr_base
!= op
->op0
)
1074 double_int off
= tree_to_double_int (mem_op
->op0
);
1075 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1076 off
+= double_int::from_shwi (addr_offset
);
1077 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1078 op
->op0
= build_fold_addr_expr (addr_base
);
1079 if (host_integerp (mem_op
->op0
, 0))
1080 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1086 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1087 *I_P to point to the last element of the replacement. */
1089 vn_reference_maybe_forwprop_address (VEC (vn_reference_op_s
, heap
) **ops
,
1092 unsigned int i
= *i_p
;
1093 vn_reference_op_t op
= &VEC_index (vn_reference_op_s
, *ops
, i
);
1094 vn_reference_op_t mem_op
= &VEC_index (vn_reference_op_s
, *ops
, i
- 1);
1096 enum tree_code code
;
1099 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1100 if (!is_gimple_assign (def_stmt
))
1103 code
= gimple_assign_rhs_code (def_stmt
);
1104 if (code
!= ADDR_EXPR
1105 && code
!= POINTER_PLUS_EXPR
)
1108 off
= tree_to_double_int (mem_op
->op0
);
1109 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1111 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1112 from .foo.bar to the preceding MEM_REF offset and replace the
1113 address with &OBJ. */
1114 if (code
== ADDR_EXPR
)
1116 tree addr
, addr_base
;
1117 HOST_WIDE_INT addr_offset
;
1119 addr
= gimple_assign_rhs1 (def_stmt
);
1120 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1123 || TREE_CODE (addr_base
) != MEM_REF
)
1126 off
+= double_int::from_shwi (addr_offset
);
1127 off
+= mem_ref_offset (addr_base
);
1128 op
->op0
= TREE_OPERAND (addr_base
, 0);
1133 ptr
= gimple_assign_rhs1 (def_stmt
);
1134 ptroff
= gimple_assign_rhs2 (def_stmt
);
1135 if (TREE_CODE (ptr
) != SSA_NAME
1136 || TREE_CODE (ptroff
) != INTEGER_CST
)
1139 off
+= tree_to_double_int (ptroff
);
1143 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1144 if (host_integerp (mem_op
->op0
, 0))
1145 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1148 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1149 op
->op0
= SSA_VAL (op
->op0
);
1150 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1151 op
->opcode
= TREE_CODE (op
->op0
);
1154 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1155 vn_reference_maybe_forwprop_address (ops
, i_p
);
1156 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1157 vn_reference_fold_indirect (ops
, i_p
);
1160 /* Optimize the reference REF to a constant if possible or return
1161 NULL_TREE if not. */
1164 fully_constant_vn_reference_p (vn_reference_t ref
)
1166 VEC (vn_reference_op_s
, heap
) *operands
= ref
->operands
;
1167 vn_reference_op_t op
;
1169 /* Try to simplify the translated expression if it is
1170 a call to a builtin function with at most two arguments. */
1171 op
= &VEC_index (vn_reference_op_s
, operands
, 0);
1172 if (op
->opcode
== CALL_EXPR
1173 && TREE_CODE (op
->op0
) == ADDR_EXPR
1174 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1175 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1176 && VEC_length (vn_reference_op_s
, operands
) >= 2
1177 && VEC_length (vn_reference_op_s
, operands
) <= 3)
1179 vn_reference_op_t arg0
, arg1
= NULL
;
1180 bool anyconst
= false;
1181 arg0
= &VEC_index (vn_reference_op_s
, operands
, 1);
1182 if (VEC_length (vn_reference_op_s
, operands
) > 2)
1183 arg1
= &VEC_index (vn_reference_op_s
, operands
, 2);
1184 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1185 || (arg0
->opcode
== ADDR_EXPR
1186 && is_gimple_min_invariant (arg0
->op0
)))
1189 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1190 || (arg1
->opcode
== ADDR_EXPR
1191 && is_gimple_min_invariant (arg1
->op0
))))
1195 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1198 arg1
? arg1
->op0
: NULL
);
1200 && TREE_CODE (folded
) == NOP_EXPR
)
1201 folded
= TREE_OPERAND (folded
, 0);
1203 && is_gimple_min_invariant (folded
))
1208 /* Simplify reads from constant strings. */
1209 else if (op
->opcode
== ARRAY_REF
1210 && TREE_CODE (op
->op0
) == INTEGER_CST
1211 && integer_zerop (op
->op1
)
1212 && VEC_length (vn_reference_op_s
, operands
) == 2)
1214 vn_reference_op_t arg0
;
1215 arg0
= &VEC_index (vn_reference_op_s
, operands
, 1);
1216 if (arg0
->opcode
== STRING_CST
1217 && (TYPE_MODE (op
->type
)
1218 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1219 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1220 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1221 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1222 return build_int_cst_type (op
->type
,
1223 (TREE_STRING_POINTER (arg0
->op0
)
1224 [TREE_INT_CST_LOW (op
->op0
)]));
1230 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1231 structures into their value numbers. This is done in-place, and
1232 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1233 whether any operands were valueized. */
1235 static VEC (vn_reference_op_s
, heap
) *
1236 valueize_refs_1 (VEC (vn_reference_op_s
, heap
) *orig
, bool *valueized_anything
)
1238 vn_reference_op_t vro
;
1241 *valueized_anything
= false;
1243 FOR_EACH_VEC_ELT (vn_reference_op_s
, orig
, i
, vro
)
1245 if (vro
->opcode
== SSA_NAME
1246 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1248 tree tem
= SSA_VAL (vro
->op0
);
1249 if (tem
!= vro
->op0
)
1251 *valueized_anything
= true;
1254 /* If it transforms from an SSA_NAME to a constant, update
1256 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1257 vro
->opcode
= TREE_CODE (vro
->op0
);
1259 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1261 tree tem
= SSA_VAL (vro
->op1
);
1262 if (tem
!= vro
->op1
)
1264 *valueized_anything
= true;
1268 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1270 tree tem
= SSA_VAL (vro
->op2
);
1271 if (tem
!= vro
->op2
)
1273 *valueized_anything
= true;
1277 /* If it transforms from an SSA_NAME to an address, fold with
1278 a preceding indirect reference. */
1281 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1282 && VEC_index (vn_reference_op_s
,
1283 orig
, i
- 1).opcode
== MEM_REF
)
1284 vn_reference_fold_indirect (&orig
, &i
);
1286 && vro
->opcode
== SSA_NAME
1287 && VEC_index (vn_reference_op_s
,
1288 orig
, i
- 1).opcode
== MEM_REF
)
1289 vn_reference_maybe_forwprop_address (&orig
, &i
);
1290 /* If it transforms a non-constant ARRAY_REF into a constant
1291 one, adjust the constant offset. */
1292 else if (vro
->opcode
== ARRAY_REF
1294 && TREE_CODE (vro
->op0
) == INTEGER_CST
1295 && TREE_CODE (vro
->op1
) == INTEGER_CST
1296 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1298 double_int off
= tree_to_double_int (vro
->op0
);
1299 off
+= -tree_to_double_int (vro
->op1
);
1300 off
*= tree_to_double_int (vro
->op2
);
1301 if (off
.fits_shwi ())
1309 static VEC (vn_reference_op_s
, heap
) *
1310 valueize_refs (VEC (vn_reference_op_s
, heap
) *orig
)
1313 return valueize_refs_1 (orig
, &tem
);
1316 static VEC(vn_reference_op_s
, heap
) *shared_lookup_references
;
1318 /* Create a vector of vn_reference_op_s structures from REF, a
1319 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1320 this function. *VALUEIZED_ANYTHING will specify whether any
1321 operands were valueized. */
1323 static VEC(vn_reference_op_s
, heap
) *
1324 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1328 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
1329 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1330 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1331 valueized_anything
);
1332 return shared_lookup_references
;
1335 /* Create a vector of vn_reference_op_s structures from CALL, a
1336 call statement. The vector is shared among all callers of
1339 static VEC(vn_reference_op_s
, heap
) *
1340 valueize_shared_reference_ops_from_call (gimple call
)
1344 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
1345 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1346 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1347 return shared_lookup_references
;
1350 /* Lookup a SCCVN reference operation VR in the current hash table.
1351 Returns the resulting value number if it exists in the hash table,
1352 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1353 vn_reference_t stored in the hashtable if something is found. */
1356 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1361 hash
= vr
->hashcode
;
1362 slot
= htab_find_slot_with_hash (current_info
->references
, vr
,
1364 if (!slot
&& current_info
== optimistic_info
)
1365 slot
= htab_find_slot_with_hash (valid_info
->references
, vr
,
1370 *vnresult
= (vn_reference_t
)*slot
;
1371 return ((vn_reference_t
)*slot
)->result
;
1377 static tree
*last_vuse_ptr
;
1378 static vn_lookup_kind vn_walk_kind
;
1379 static vn_lookup_kind default_vn_walk_kind
;
1381 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1382 with the current VUSE and performs the expression lookup. */
1385 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1386 unsigned int cnt
, void *vr_
)
1388 vn_reference_t vr
= (vn_reference_t
)vr_
;
1392 /* This bounds the stmt walks we perform on reference lookups
1393 to O(1) instead of O(N) where N is the number of dominating
1395 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1399 *last_vuse_ptr
= vuse
;
1401 /* Fixup vuse and hash. */
1403 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1404 vr
->vuse
= SSA_VAL (vuse
);
1406 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1408 hash
= vr
->hashcode
;
1409 slot
= htab_find_slot_with_hash (current_info
->references
, vr
,
1411 if (!slot
&& current_info
== optimistic_info
)
1412 slot
= htab_find_slot_with_hash (valid_info
->references
, vr
,
1420 /* Lookup an existing or insert a new vn_reference entry into the
1421 value table for the VUSE, SET, TYPE, OPERANDS reference which
1422 has the value VALUE which is either a constant or an SSA name. */
1424 static vn_reference_t
1425 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1428 VEC (vn_reference_op_s
,
1432 struct vn_reference_s vr1
;
1433 vn_reference_t result
;
1436 vr1
.operands
= operands
;
1439 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1440 if (vn_reference_lookup_1 (&vr1
, &result
))
1442 if (TREE_CODE (value
) == SSA_NAME
)
1443 value_id
= VN_INFO (value
)->value_id
;
1445 value_id
= get_or_alloc_constant_value_id (value
);
1446 return vn_reference_insert_pieces (vuse
, set
, type
,
1447 VEC_copy (vn_reference_op_s
, heap
,
1448 operands
), value
, value_id
);
1451 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1452 from the statement defining VUSE and if not successful tries to
1453 translate *REFP and VR_ through an aggregate copy at the definition
1457 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
)
1459 vn_reference_t vr
= (vn_reference_t
)vr_
;
1460 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1462 HOST_WIDE_INT offset
, maxsize
;
1463 static VEC (vn_reference_op_s
, heap
) *lhs_ops
= NULL
;
1465 bool lhs_ref_ok
= false;
1467 /* First try to disambiguate after value-replacing in the definitions LHS. */
1468 if (is_gimple_assign (def_stmt
))
1470 VEC (vn_reference_op_s
, heap
) *tem
;
1471 tree lhs
= gimple_assign_lhs (def_stmt
);
1472 bool valueized_anything
= false;
1473 /* Avoid re-allocation overhead. */
1474 VEC_truncate (vn_reference_op_s
, lhs_ops
, 0);
1475 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1477 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1478 gcc_assert (lhs_ops
== tem
);
1479 if (valueized_anything
)
1481 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1482 get_alias_set (lhs
),
1483 TREE_TYPE (lhs
), lhs_ops
);
1485 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1490 ao_ref_init (&lhs_ref
, lhs
);
1495 base
= ao_ref_base (ref
);
1496 offset
= ref
->offset
;
1497 maxsize
= ref
->max_size
;
1499 /* If we cannot constrain the size of the reference we cannot
1500 test if anything kills it. */
1504 /* We can't deduce anything useful from clobbers. */
1505 if (gimple_clobber_p (def_stmt
))
1508 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1509 from that definition.
1511 if (is_gimple_reg_type (vr
->type
)
1512 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1513 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1514 && host_integerp (gimple_call_arg (def_stmt
, 2), 1)
1515 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1517 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1519 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1520 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1521 size2
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2)) * 8;
1522 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1523 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2))
1525 && operand_equal_p (base
, base2
, 0)
1526 && offset2
<= offset
1527 && offset2
+ size2
>= offset
+ maxsize
)
1529 tree val
= build_zero_cst (vr
->type
);
1530 return vn_reference_lookup_or_insert_for_pieces
1531 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1535 /* 2) Assignment from an empty CONSTRUCTOR. */
1536 else if (is_gimple_reg_type (vr
->type
)
1537 && gimple_assign_single_p (def_stmt
)
1538 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1539 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1542 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1543 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1544 &offset2
, &size2
, &maxsize2
);
1546 && operand_equal_p (base
, base2
, 0)
1547 && offset2
<= offset
1548 && offset2
+ size2
>= offset
+ maxsize
)
1550 tree val
= build_zero_cst (vr
->type
);
1551 return vn_reference_lookup_or_insert_for_pieces
1552 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1556 /* 3) Assignment from a constant. We can use folds native encode/interpret
1557 routines to extract the assigned bits. */
1558 else if (CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1559 && ref
->size
== maxsize
1560 && maxsize
% BITS_PER_UNIT
== 0
1561 && offset
% BITS_PER_UNIT
== 0
1562 && is_gimple_reg_type (vr
->type
)
1563 && gimple_assign_single_p (def_stmt
)
1564 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1567 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1568 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1569 &offset2
, &size2
, &maxsize2
);
1571 && maxsize2
== size2
1572 && size2
% BITS_PER_UNIT
== 0
1573 && offset2
% BITS_PER_UNIT
== 0
1574 && operand_equal_p (base
, base2
, 0)
1575 && offset2
<= offset
1576 && offset2
+ size2
>= offset
+ maxsize
)
1578 /* We support up to 512-bit values (for V8DFmode). */
1579 unsigned char buffer
[64];
1582 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1583 buffer
, sizeof (buffer
));
1586 tree val
= native_interpret_expr (vr
->type
,
1588 + ((offset
- offset2
)
1590 ref
->size
/ BITS_PER_UNIT
);
1592 return vn_reference_lookup_or_insert_for_pieces
1593 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1598 /* 4) Assignment from an SSA name which definition we may be able
1599 to access pieces from. */
1600 else if (ref
->size
== maxsize
1601 && is_gimple_reg_type (vr
->type
)
1602 && gimple_assign_single_p (def_stmt
)
1603 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1605 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1606 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1607 if (is_gimple_assign (def_stmt2
)
1608 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1609 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1610 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1613 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1614 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1615 &offset2
, &size2
, &maxsize2
);
1616 off
= offset
- offset2
;
1618 && maxsize2
== size2
1619 && operand_equal_p (base
, base2
, 0)
1620 && offset2
<= offset
1621 && offset2
+ size2
>= offset
+ maxsize
)
1623 tree val
= NULL_TREE
;
1625 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1626 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1629 val
= gimple_assign_rhs1 (def_stmt2
);
1630 else if (off
== elsz
)
1631 val
= gimple_assign_rhs2 (def_stmt2
);
1633 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1636 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1637 unsigned i
= off
/ elsz
;
1638 if (i
< CONSTRUCTOR_NELTS (ctor
))
1640 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1641 if (compare_tree_int (elt
->index
, i
) == 0)
1646 return vn_reference_lookup_or_insert_for_pieces
1647 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1652 /* 5) For aggregate copies translate the reference through them if
1653 the copy kills ref. */
1654 else if (vn_walk_kind
== VN_WALKREWRITE
1655 && gimple_assign_single_p (def_stmt
)
1656 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1657 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1658 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1661 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1663 VEC (vn_reference_op_s
, heap
) *rhs
= NULL
;
1664 vn_reference_op_t vro
;
1670 /* See if the assignment kills REF. */
1671 base2
= ao_ref_base (&lhs_ref
);
1672 offset2
= lhs_ref
.offset
;
1673 size2
= lhs_ref
.size
;
1674 maxsize2
= lhs_ref
.max_size
;
1676 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1678 || offset2
+ size2
< offset
+ maxsize
)
1681 /* Find the common base of ref and the lhs. lhs_ops already
1682 contains valueized operands for the lhs. */
1683 i
= VEC_length (vn_reference_op_s
, vr
->operands
) - 1;
1684 j
= VEC_length (vn_reference_op_s
, lhs_ops
) - 1;
1685 while (j
>= 0 && i
>= 0
1686 && vn_reference_op_eq (&VEC_index (vn_reference_op_s
,
1688 &VEC_index (vn_reference_op_s
, lhs_ops
, j
)))
1694 /* ??? The innermost op should always be a MEM_REF and we already
1695 checked that the assignment to the lhs kills vr. Thus for
1696 aggregate copies using char[] types the vn_reference_op_eq
1697 may fail when comparing types for compatibility. But we really
1698 don't care here - further lookups with the rewritten operands
1699 will simply fail if we messed up types too badly. */
1700 if (j
== 0 && i
>= 0
1701 && VEC_index (vn_reference_op_s
, lhs_ops
, 0).opcode
== MEM_REF
1702 && VEC_index (vn_reference_op_s
, lhs_ops
, 0).off
!= -1
1703 && (VEC_index (vn_reference_op_s
, lhs_ops
, 0).off
1704 == VEC_index (vn_reference_op_s
, vr
->operands
, i
).off
))
1707 /* i now points to the first additional op.
1708 ??? LHS may not be completely contained in VR, one or more
1709 VIEW_CONVERT_EXPRs could be in its way. We could at least
1710 try handling outermost VIEW_CONVERT_EXPRs. */
1714 /* Now re-write REF to be based on the rhs of the assignment. */
1715 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1716 /* We need to pre-pend vr->operands[0..i] to rhs. */
1717 if (i
+ 1 + VEC_length (vn_reference_op_s
, rhs
)
1718 > VEC_length (vn_reference_op_s
, vr
->operands
))
1720 VEC (vn_reference_op_s
, heap
) *old
= vr
->operands
;
1721 VEC_safe_grow (vn_reference_op_s
, heap
, vr
->operands
,
1722 i
+ 1 + VEC_length (vn_reference_op_s
, rhs
));
1723 if (old
== shared_lookup_references
1724 && vr
->operands
!= old
)
1725 shared_lookup_references
= NULL
;
1728 VEC_truncate (vn_reference_op_s
, vr
->operands
,
1729 i
+ 1 + VEC_length (vn_reference_op_s
, rhs
));
1730 FOR_EACH_VEC_ELT (vn_reference_op_s
, rhs
, j
, vro
)
1731 VEC_replace (vn_reference_op_s
, vr
->operands
, i
+ 1 + j
, *vro
);
1732 VEC_free (vn_reference_op_s
, heap
, rhs
);
1733 vr
->operands
= valueize_refs (vr
->operands
);
1734 vr
->hashcode
= vn_reference_compute_hash (vr
);
1736 /* Adjust *ref from the new operands. */
1737 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1739 /* This can happen with bitfields. */
1740 if (ref
->size
!= r
.size
)
1744 /* Do not update last seen VUSE after translating. */
1745 last_vuse_ptr
= NULL
;
1747 /* Keep looking for the adjusted *REF / VR pair. */
1751 /* 6) For memcpy copies translate the reference through them if
1752 the copy kills ref. */
1753 else if (vn_walk_kind
== VN_WALKREWRITE
1754 && is_gimple_reg_type (vr
->type
)
1755 /* ??? Handle BCOPY as well. */
1756 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1757 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1758 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1759 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1760 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1761 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1762 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1763 && host_integerp (gimple_call_arg (def_stmt
, 2), 1))
1767 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1768 vn_reference_op_s op
;
1772 /* Only handle non-variable, addressable refs. */
1773 if (ref
->size
!= maxsize
1774 || offset
% BITS_PER_UNIT
!= 0
1775 || ref
->size
% BITS_PER_UNIT
!= 0)
1778 /* Extract a pointer base and an offset for the destination. */
1779 lhs
= gimple_call_arg (def_stmt
, 0);
1781 if (TREE_CODE (lhs
) == SSA_NAME
)
1782 lhs
= SSA_VAL (lhs
);
1783 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1785 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1789 if (TREE_CODE (tem
) == MEM_REF
1790 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1792 lhs
= TREE_OPERAND (tem
, 0);
1793 lhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1795 else if (DECL_P (tem
))
1796 lhs
= build_fold_addr_expr (tem
);
1800 if (TREE_CODE (lhs
) != SSA_NAME
1801 && TREE_CODE (lhs
) != ADDR_EXPR
)
1804 /* Extract a pointer base and an offset for the source. */
1805 rhs
= gimple_call_arg (def_stmt
, 1);
1807 if (TREE_CODE (rhs
) == SSA_NAME
)
1808 rhs
= SSA_VAL (rhs
);
1809 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1811 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1815 if (TREE_CODE (tem
) == MEM_REF
1816 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1818 rhs
= TREE_OPERAND (tem
, 0);
1819 rhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1821 else if (DECL_P (tem
))
1822 rhs
= build_fold_addr_expr (tem
);
1826 if (TREE_CODE (rhs
) != SSA_NAME
1827 && TREE_CODE (rhs
) != ADDR_EXPR
)
1830 copy_size
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2));
1832 /* The bases of the destination and the references have to agree. */
1833 if ((TREE_CODE (base
) != MEM_REF
1835 || (TREE_CODE (base
) == MEM_REF
1836 && (TREE_OPERAND (base
, 0) != lhs
1837 || !host_integerp (TREE_OPERAND (base
, 1), 1)))
1839 && (TREE_CODE (lhs
) != ADDR_EXPR
1840 || TREE_OPERAND (lhs
, 0) != base
)))
1843 /* And the access has to be contained within the memcpy destination. */
1844 at
= offset
/ BITS_PER_UNIT
;
1845 if (TREE_CODE (base
) == MEM_REF
)
1846 at
+= TREE_INT_CST_LOW (TREE_OPERAND (base
, 1));
1848 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1851 /* Make room for 2 operands in the new reference. */
1852 if (VEC_length (vn_reference_op_s
, vr
->operands
) < 2)
1854 VEC (vn_reference_op_s
, heap
) *old
= vr
->operands
;
1855 VEC_safe_grow (vn_reference_op_s
, heap
, vr
->operands
, 2);
1856 if (old
== shared_lookup_references
1857 && vr
->operands
!= old
)
1858 shared_lookup_references
= NULL
;
1861 VEC_truncate (vn_reference_op_s
, vr
->operands
, 2);
1863 /* The looked-through reference is a simple MEM_REF. */
1864 memset (&op
, 0, sizeof (op
));
1866 op
.opcode
= MEM_REF
;
1867 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
1868 op
.off
= at
- lhs_offset
+ rhs_offset
;
1869 VEC_replace (vn_reference_op_s
, vr
->operands
, 0, op
);
1870 op
.type
= TREE_TYPE (rhs
);
1871 op
.opcode
= TREE_CODE (rhs
);
1874 VEC_replace (vn_reference_op_s
, vr
->operands
, 1, op
);
1875 vr
->hashcode
= vn_reference_compute_hash (vr
);
1877 /* Adjust *ref from the new operands. */
1878 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1880 /* This can happen with bitfields. */
1881 if (ref
->size
!= r
.size
)
1885 /* Do not update last seen VUSE after translating. */
1886 last_vuse_ptr
= NULL
;
1888 /* Keep looking for the adjusted *REF / VR pair. */
1892 /* Bail out and stop walking. */
1896 /* Lookup a reference operation by it's parts, in the current hash table.
1897 Returns the resulting value number if it exists in the hash table,
1898 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1899 vn_reference_t stored in the hashtable if something is found. */
1902 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
1903 VEC (vn_reference_op_s
, heap
) *operands
,
1904 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
1906 struct vn_reference_s vr1
;
1914 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1915 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
1916 VEC_safe_grow (vn_reference_op_s
, heap
, shared_lookup_references
,
1917 VEC_length (vn_reference_op_s
, operands
));
1918 memcpy (VEC_address (vn_reference_op_s
, shared_lookup_references
),
1919 VEC_address (vn_reference_op_s
, operands
),
1920 sizeof (vn_reference_op_s
)
1921 * VEC_length (vn_reference_op_s
, operands
));
1922 vr1
.operands
= operands
= shared_lookup_references
1923 = valueize_refs (shared_lookup_references
);
1926 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1927 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
1930 vn_reference_lookup_1 (&vr1
, vnresult
);
1932 && kind
!= VN_NOWALK
1936 vn_walk_kind
= kind
;
1937 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
1939 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1940 vn_reference_lookup_2
,
1941 vn_reference_lookup_3
, &vr1
);
1942 if (vr1
.operands
!= operands
)
1943 VEC_free (vn_reference_op_s
, heap
, vr1
.operands
);
1947 return (*vnresult
)->result
;
1952 /* Lookup OP in the current hash table, and return the resulting value
1953 number if it exists in the hash table. Return NULL_TREE if it does
1954 not exist in the hash table or if the result field of the structure
1955 was NULL.. VNRESULT will be filled in with the vn_reference_t
1956 stored in the hashtable if one exists. */
1959 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
1960 vn_reference_t
*vnresult
)
1962 VEC (vn_reference_op_s
, heap
) *operands
;
1963 struct vn_reference_s vr1
;
1965 bool valuezied_anything
;
1970 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1971 vr1
.operands
= operands
1972 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
1973 vr1
.type
= TREE_TYPE (op
);
1974 vr1
.set
= get_alias_set (op
);
1975 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1976 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
1979 if (kind
!= VN_NOWALK
1982 vn_reference_t wvnresult
;
1984 /* Make sure to use a valueized reference if we valueized anything.
1985 Otherwise preserve the full reference for advanced TBAA. */
1986 if (!valuezied_anything
1987 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
1989 ao_ref_init (&r
, op
);
1990 vn_walk_kind
= kind
;
1992 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1993 vn_reference_lookup_2
,
1994 vn_reference_lookup_3
, &vr1
);
1995 if (vr1
.operands
!= operands
)
1996 VEC_free (vn_reference_op_s
, heap
, vr1
.operands
);
2000 *vnresult
= wvnresult
;
2001 return wvnresult
->result
;
2007 return vn_reference_lookup_1 (&vr1
, vnresult
);
2011 /* Insert OP into the current hash table with a value number of
2012 RESULT, and return the resulting reference structure we created. */
2015 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2020 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2021 if (TREE_CODE (result
) == SSA_NAME
)
2022 vr1
->value_id
= VN_INFO (result
)->value_id
;
2024 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2025 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2026 vr1
->operands
= valueize_refs (create_reference_ops_from_ref (op
));
2027 vr1
->type
= TREE_TYPE (op
);
2028 vr1
->set
= get_alias_set (op
);
2029 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2030 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2031 vr1
->result_vdef
= vdef
;
2033 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
2036 /* Because we lookup stores using vuses, and value number failures
2037 using the vdefs (see visit_reference_op_store for how and why),
2038 it's possible that on failure we may try to insert an already
2039 inserted store. This is not wrong, there is no ssa name for a
2040 store that we could use as a differentiator anyway. Thus, unlike
2041 the other lookup functions, you cannot gcc_assert (!*slot)
2044 /* But free the old slot in case of a collision. */
2046 free_reference (*slot
);
2052 /* Insert a reference by it's pieces into the current hash table with
2053 a value number of RESULT. Return the resulting reference
2054 structure we created. */
2057 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2058 VEC (vn_reference_op_s
, heap
) *operands
,
2059 tree result
, unsigned int value_id
)
2065 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2066 vr1
->value_id
= value_id
;
2067 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2068 vr1
->operands
= valueize_refs (operands
);
2071 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2072 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2073 result
= SSA_VAL (result
);
2074 vr1
->result
= result
;
2076 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
2079 /* At this point we should have all the things inserted that we have
2080 seen before, and we should never try inserting something that
2082 gcc_assert (!*slot
);
2084 free_reference (*slot
);
2090 /* Compute and return the hash value for nary operation VBO1. */
2093 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2098 for (i
= 0; i
< vno1
->length
; ++i
)
2099 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2100 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2102 if (vno1
->length
== 2
2103 && commutative_tree_code (vno1
->opcode
)
2104 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2106 tree temp
= vno1
->op
[0];
2107 vno1
->op
[0] = vno1
->op
[1];
2111 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2112 for (i
= 0; i
< vno1
->length
; ++i
)
2113 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2118 /* Return the computed hashcode for nary operation P1. */
2121 vn_nary_op_hash (const void *p1
)
2123 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
2124 return vno1
->hashcode
;
2127 /* Compare nary operations P1 and P2 and return true if they are
2131 vn_nary_op_eq (const void *p1
, const void *p2
)
2133 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
2134 const_vn_nary_op_t
const vno2
= (const_vn_nary_op_t
) p2
;
2137 if (vno1
->hashcode
!= vno2
->hashcode
)
2140 if (vno1
->length
!= vno2
->length
)
2143 if (vno1
->opcode
!= vno2
->opcode
2144 || !types_compatible_p (vno1
->type
, vno2
->type
))
2147 for (i
= 0; i
< vno1
->length
; ++i
)
2148 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2154 /* Initialize VNO from the pieces provided. */
2157 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2158 enum tree_code code
, tree type
, tree
*ops
)
2161 vno
->length
= length
;
2163 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2166 /* Initialize VNO from OP. */
2169 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2173 vno
->opcode
= TREE_CODE (op
);
2174 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2175 vno
->type
= TREE_TYPE (op
);
2176 for (i
= 0; i
< vno
->length
; ++i
)
2177 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2180 /* Return the number of operands for a vn_nary ops structure from STMT. */
2183 vn_nary_length_from_stmt (gimple stmt
)
2185 switch (gimple_assign_rhs_code (stmt
))
2189 case VIEW_CONVERT_EXPR
:
2193 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2196 return gimple_num_ops (stmt
) - 1;
2200 /* Initialize VNO from STMT. */
2203 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2207 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2208 vno
->type
= gimple_expr_type (stmt
);
2209 switch (vno
->opcode
)
2213 case VIEW_CONVERT_EXPR
:
2215 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2219 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2220 for (i
= 0; i
< vno
->length
; ++i
)
2221 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2225 vno
->length
= gimple_num_ops (stmt
) - 1;
2226 for (i
= 0; i
< vno
->length
; ++i
)
2227 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2231 /* Compute the hashcode for VNO and look for it in the hash table;
2232 return the resulting value number if it exists in the hash table.
2233 Return NULL_TREE if it does not exist in the hash table or if the
2234 result field of the operation is NULL. VNRESULT will contain the
2235 vn_nary_op_t from the hashtable if it exists. */
2238 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2245 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2246 slot
= htab_find_slot_with_hash (current_info
->nary
, vno
, vno
->hashcode
,
2248 if (!slot
&& current_info
== optimistic_info
)
2249 slot
= htab_find_slot_with_hash (valid_info
->nary
, vno
, vno
->hashcode
,
2254 *vnresult
= (vn_nary_op_t
)*slot
;
2255 return ((vn_nary_op_t
)*slot
)->result
;
2258 /* Lookup a n-ary operation by its pieces and return the resulting value
2259 number if it exists in the hash table. Return NULL_TREE if it does
2260 not exist in the hash table or if the result field of the operation
2261 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2265 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2266 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2268 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2269 sizeof_vn_nary_op (length
));
2270 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2271 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2274 /* Lookup OP in the current hash table, and return the resulting value
2275 number if it exists in the hash table. Return NULL_TREE if it does
2276 not exist in the hash table or if the result field of the operation
2277 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2281 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2284 = XALLOCAVAR (struct vn_nary_op_s
,
2285 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2286 init_vn_nary_op_from_op (vno1
, op
);
2287 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2290 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2291 value number if it exists in the hash table. Return NULL_TREE if
2292 it does not exist in the hash table. VNRESULT will contain the
2293 vn_nary_op_t from the hashtable if it exists. */
2296 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2299 = XALLOCAVAR (struct vn_nary_op_s
,
2300 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2301 init_vn_nary_op_from_stmt (vno1
, stmt
);
2302 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2305 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2308 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2310 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2313 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2317 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2319 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2320 ¤t_info
->nary_obstack
);
2322 vno1
->value_id
= value_id
;
2323 vno1
->length
= length
;
2324 vno1
->result
= result
;
2329 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2330 VNO->HASHCODE first. */
2333 vn_nary_op_insert_into (vn_nary_op_t vno
, htab_t table
, bool compute_hash
)
2338 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2340 slot
= htab_find_slot_with_hash (table
, vno
, vno
->hashcode
, INSERT
);
2341 gcc_assert (!*slot
);
2347 /* Insert a n-ary operation into the current hash table using it's
2348 pieces. Return the vn_nary_op_t structure we created and put in
2352 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2353 tree type
, tree
*ops
,
2354 tree result
, unsigned int value_id
)
2356 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2357 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2358 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2361 /* Insert OP into the current hash table with a value number of
2362 RESULT. Return the vn_nary_op_t structure we created and put in
2366 vn_nary_op_insert (tree op
, tree result
)
2368 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2371 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2372 init_vn_nary_op_from_op (vno1
, op
);
2373 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2376 /* Insert the rhs of STMT into the current hash table with a value number of
2380 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2383 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2384 result
, VN_INFO (result
)->value_id
);
2385 init_vn_nary_op_from_stmt (vno1
, stmt
);
2386 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2389 /* Compute a hashcode for PHI operation VP1 and return it. */
2391 static inline hashval_t
2392 vn_phi_compute_hash (vn_phi_t vp1
)
2399 result
= vp1
->block
->index
;
2401 /* If all PHI arguments are constants we need to distinguish
2402 the PHI node via its type. */
2403 type
= TREE_TYPE (VEC_index (tree
, vp1
->phiargs
, 0));
2404 result
+= (INTEGRAL_TYPE_P (type
)
2405 + (INTEGRAL_TYPE_P (type
)
2406 ? TYPE_PRECISION (type
) + TYPE_UNSIGNED (type
) : 0));
2408 FOR_EACH_VEC_ELT (tree
, vp1
->phiargs
, i
, phi1op
)
2410 if (phi1op
== VN_TOP
)
2412 result
= iterative_hash_expr (phi1op
, result
);
2418 /* Return the computed hashcode for phi operation P1. */
2421 vn_phi_hash (const void *p1
)
2423 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
2424 return vp1
->hashcode
;
2427 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2430 vn_phi_eq (const void *p1
, const void *p2
)
2432 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
2433 const_vn_phi_t
const vp2
= (const_vn_phi_t
) p2
;
2435 if (vp1
->hashcode
!= vp2
->hashcode
)
2438 if (vp1
->block
== vp2
->block
)
2443 /* If the PHI nodes do not have compatible types
2444 they are not the same. */
2445 if (!types_compatible_p (TREE_TYPE (VEC_index (tree
, vp1
->phiargs
, 0)),
2446 TREE_TYPE (VEC_index (tree
, vp2
->phiargs
, 0))))
2449 /* Any phi in the same block will have it's arguments in the
2450 same edge order, because of how we store phi nodes. */
2451 FOR_EACH_VEC_ELT (tree
, vp1
->phiargs
, i
, phi1op
)
2453 tree phi2op
= VEC_index (tree
, vp2
->phiargs
, i
);
2454 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2456 if (!expressions_equal_p (phi1op
, phi2op
))
2464 static VEC(tree
, heap
) *shared_lookup_phiargs
;
2466 /* Lookup PHI in the current hash table, and return the resulting
2467 value number if it exists in the hash table. Return NULL_TREE if
2468 it does not exist in the hash table. */
2471 vn_phi_lookup (gimple phi
)
2474 struct vn_phi_s vp1
;
2477 VEC_truncate (tree
, shared_lookup_phiargs
, 0);
2479 /* Canonicalize the SSA_NAME's to their value number. */
2480 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2482 tree def
= PHI_ARG_DEF (phi
, i
);
2483 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2484 VEC_safe_push (tree
, heap
, shared_lookup_phiargs
, def
);
2486 vp1
.phiargs
= shared_lookup_phiargs
;
2487 vp1
.block
= gimple_bb (phi
);
2488 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2489 slot
= htab_find_slot_with_hash (current_info
->phis
, &vp1
, vp1
.hashcode
,
2491 if (!slot
&& current_info
== optimistic_info
)
2492 slot
= htab_find_slot_with_hash (valid_info
->phis
, &vp1
, vp1
.hashcode
,
2496 return ((vn_phi_t
)*slot
)->result
;
2499 /* Insert PHI into the current hash table with a value number of
2503 vn_phi_insert (gimple phi
, tree result
)
2506 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2508 VEC (tree
, heap
) *args
= NULL
;
2510 /* Canonicalize the SSA_NAME's to their value number. */
2511 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2513 tree def
= PHI_ARG_DEF (phi
, i
);
2514 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2515 VEC_safe_push (tree
, heap
, args
, def
);
2517 vp1
->value_id
= VN_INFO (result
)->value_id
;
2518 vp1
->phiargs
= args
;
2519 vp1
->block
= gimple_bb (phi
);
2520 vp1
->result
= result
;
2521 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2523 slot
= htab_find_slot_with_hash (current_info
->phis
, vp1
, vp1
->hashcode
,
2526 /* Because we iterate over phi operations more than once, it's
2527 possible the slot might already exist here, hence no assert.*/
2533 /* Print set of components in strongly connected component SCC to OUT. */
2536 print_scc (FILE *out
, VEC (tree
, heap
) *scc
)
2541 fprintf (out
, "SCC consists of:");
2542 FOR_EACH_VEC_ELT (tree
, scc
, i
, var
)
2545 print_generic_expr (out
, var
, 0);
2547 fprintf (out
, "\n");
2550 /* Set the value number of FROM to TO, return true if it has changed
2554 set_ssa_val_to (tree from
, tree to
)
2556 tree currval
= SSA_VAL (from
);
2560 if (currval
== from
)
2562 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2564 fprintf (dump_file
, "Not changing value number of ");
2565 print_generic_expr (dump_file
, from
, 0);
2566 fprintf (dump_file
, " from VARYING to ");
2567 print_generic_expr (dump_file
, to
, 0);
2568 fprintf (dump_file
, "\n");
2572 else if (TREE_CODE (to
) == SSA_NAME
2573 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2577 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2578 and invariants. So assert that here. */
2579 gcc_assert (to
!= NULL_TREE
2581 || TREE_CODE (to
) == SSA_NAME
2582 || is_gimple_min_invariant (to
)));
2584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2586 fprintf (dump_file
, "Setting value number of ");
2587 print_generic_expr (dump_file
, from
, 0);
2588 fprintf (dump_file
, " to ");
2589 print_generic_expr (dump_file
, to
, 0);
2592 if (currval
!= to
&& !operand_equal_p (currval
, to
, OEP_PURE_SAME
))
2594 VN_INFO (from
)->valnum
= to
;
2595 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2596 fprintf (dump_file
, " (changed)\n");
2599 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2600 fprintf (dump_file
, "\n");
2604 /* Mark as processed all the definitions in the defining stmt of USE, or
2608 mark_use_processed (tree use
)
2612 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2614 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2616 VN_INFO (use
)->use_processed
= true;
2620 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2622 tree def
= DEF_FROM_PTR (defp
);
2624 VN_INFO (def
)->use_processed
= true;
2628 /* Set all definitions in STMT to value number to themselves.
2629 Return true if a value number changed. */
2632 defs_to_varying (gimple stmt
)
2634 bool changed
= false;
2638 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2640 tree def
= DEF_FROM_PTR (defp
);
2641 changed
|= set_ssa_val_to (def
, def
);
2646 static bool expr_has_constants (tree expr
);
2647 static tree
valueize_expr (tree expr
);
2649 /* Visit a copy between LHS and RHS, return true if the value number
2653 visit_copy (tree lhs
, tree rhs
)
2655 /* Follow chains of copies to their destination. */
2656 while (TREE_CODE (rhs
) == SSA_NAME
2657 && SSA_VAL (rhs
) != rhs
)
2658 rhs
= SSA_VAL (rhs
);
2660 /* The copy may have a more interesting constant filled expression
2661 (we don't, since we know our RHS is just an SSA name). */
2662 if (TREE_CODE (rhs
) == SSA_NAME
)
2664 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2665 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2668 return set_ssa_val_to (lhs
, rhs
);
2671 /* Visit a nary operator RHS, value number it, and return true if the
2672 value number of LHS has changed as a result. */
2675 visit_nary_op (tree lhs
, gimple stmt
)
2677 bool changed
= false;
2678 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2681 changed
= set_ssa_val_to (lhs
, result
);
2684 changed
= set_ssa_val_to (lhs
, lhs
);
2685 vn_nary_op_insert_stmt (stmt
, lhs
);
2691 /* Visit a call STMT storing into LHS. Return true if the value number
2692 of the LHS has changed as a result. */
2695 visit_reference_op_call (tree lhs
, gimple stmt
)
2697 bool changed
= false;
2698 struct vn_reference_s vr1
;
2699 vn_reference_t vnresult
= NULL
;
2700 tree vuse
= gimple_vuse (stmt
);
2701 tree vdef
= gimple_vdef (stmt
);
2703 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2704 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2707 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2708 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2709 vr1
.type
= gimple_expr_type (stmt
);
2711 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2712 vn_reference_lookup_1 (&vr1
, &vnresult
);
2716 if (vnresult
->result_vdef
)
2717 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2719 if (!vnresult
->result
&& lhs
)
2720 vnresult
->result
= lhs
;
2722 if (vnresult
->result
&& lhs
)
2724 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2726 if (VN_INFO (vnresult
->result
)->has_constants
)
2727 VN_INFO (lhs
)->has_constants
= true;
2735 changed
|= set_ssa_val_to (vdef
, vdef
);
2737 changed
|= set_ssa_val_to (lhs
, lhs
);
2738 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2739 vr2
->vuse
= vr1
.vuse
;
2740 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2741 vr2
->type
= vr1
.type
;
2743 vr2
->hashcode
= vr1
.hashcode
;
2745 vr2
->result_vdef
= vdef
;
2746 slot
= htab_find_slot_with_hash (current_info
->references
,
2747 vr2
, vr2
->hashcode
, INSERT
);
2749 free_reference (*slot
);
2756 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2757 and return true if the value number of the LHS has changed as a result. */
2760 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2762 bool changed
= false;
2766 last_vuse
= gimple_vuse (stmt
);
2767 last_vuse_ptr
= &last_vuse
;
2768 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2769 default_vn_walk_kind
, NULL
);
2770 last_vuse_ptr
= NULL
;
2772 /* If we have a VCE, try looking up its operand as it might be stored in
2773 a different type. */
2774 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2775 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2776 default_vn_walk_kind
, NULL
);
2778 /* We handle type-punning through unions by value-numbering based
2779 on offset and size of the access. Be prepared to handle a
2780 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2782 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2784 /* We will be setting the value number of lhs to the value number
2785 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2786 So first simplify and lookup this expression to see if it
2787 is already available. */
2788 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2789 if ((CONVERT_EXPR_P (val
)
2790 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2791 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2793 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2794 if ((CONVERT_EXPR_P (tem
)
2795 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2796 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2797 TREE_TYPE (val
), tem
)))
2801 if (!is_gimple_min_invariant (val
)
2802 && TREE_CODE (val
) != SSA_NAME
)
2803 result
= vn_nary_op_lookup (val
, NULL
);
2804 /* If the expression is not yet available, value-number lhs to
2805 a new SSA_NAME we create. */
2808 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2810 /* Initialize value-number information properly. */
2811 VN_INFO_GET (result
)->valnum
= result
;
2812 VN_INFO (result
)->value_id
= get_next_value_id ();
2813 VN_INFO (result
)->expr
= val
;
2814 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2815 VN_INFO (result
)->needs_insertion
= true;
2816 /* As all "inserted" statements are singleton SCCs, insert
2817 to the valid table. This is strictly needed to
2818 avoid re-generating new value SSA_NAMEs for the same
2819 expression during SCC iteration over and over (the
2820 optimistic table gets cleared after each iteration).
2821 We do not need to insert into the optimistic table, as
2822 lookups there will fall back to the valid table. */
2823 if (current_info
== optimistic_info
)
2825 current_info
= valid_info
;
2826 vn_nary_op_insert (val
, result
);
2827 current_info
= optimistic_info
;
2830 vn_nary_op_insert (val
, result
);
2831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2833 fprintf (dump_file
, "Inserting name ");
2834 print_generic_expr (dump_file
, result
, 0);
2835 fprintf (dump_file
, " for expression ");
2836 print_generic_expr (dump_file
, val
, 0);
2837 fprintf (dump_file
, "\n");
2844 changed
= set_ssa_val_to (lhs
, result
);
2845 if (TREE_CODE (result
) == SSA_NAME
2846 && VN_INFO (result
)->has_constants
)
2848 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2849 VN_INFO (lhs
)->has_constants
= true;
2854 changed
= set_ssa_val_to (lhs
, lhs
);
2855 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
2862 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2863 and return true if the value number of the LHS has changed as a result. */
2866 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2868 bool changed
= false;
2869 vn_reference_t vnresult
= NULL
;
2870 tree result
, assign
;
2871 bool resultsame
= false;
2872 tree vuse
= gimple_vuse (stmt
);
2873 tree vdef
= gimple_vdef (stmt
);
2875 /* First we want to lookup using the *vuses* from the store and see
2876 if there the last store to this location with the same address
2879 The vuses represent the memory state before the store. If the
2880 memory state, address, and value of the store is the same as the
2881 last store to this location, then this store will produce the
2882 same memory state as that store.
2884 In this case the vdef versions for this store are value numbered to those
2885 vuse versions, since they represent the same memory state after
2888 Otherwise, the vdefs for the store are used when inserting into
2889 the table, since the store generates a new memory state. */
2891 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
2895 if (TREE_CODE (result
) == SSA_NAME
)
2896 result
= SSA_VAL (result
);
2897 if (TREE_CODE (op
) == SSA_NAME
)
2899 resultsame
= expressions_equal_p (result
, op
);
2902 if (!result
|| !resultsame
)
2904 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2905 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
2908 VN_INFO (vdef
)->use_processed
= true;
2909 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2913 if (!result
|| !resultsame
)
2915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2917 fprintf (dump_file
, "No store match\n");
2918 fprintf (dump_file
, "Value numbering store ");
2919 print_generic_expr (dump_file
, lhs
, 0);
2920 fprintf (dump_file
, " to ");
2921 print_generic_expr (dump_file
, op
, 0);
2922 fprintf (dump_file
, "\n");
2924 /* Have to set value numbers before insert, since insert is
2925 going to valueize the references in-place. */
2928 changed
|= set_ssa_val_to (vdef
, vdef
);
2931 /* Do not insert structure copies into the tables. */
2932 if (is_gimple_min_invariant (op
)
2933 || is_gimple_reg (op
))
2934 vn_reference_insert (lhs
, op
, vdef
, NULL
);
2936 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2937 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
2941 /* We had a match, so value number the vdef to have the value
2942 number of the vuse it came from. */
2944 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2945 fprintf (dump_file
, "Store matched earlier value,"
2946 "value numbering store vdefs to matching vuses.\n");
2948 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
2954 /* Visit and value number PHI, return true if the value number
2958 visit_phi (gimple phi
)
2960 bool changed
= false;
2962 tree sameval
= VN_TOP
;
2963 bool allsame
= true;
2966 /* TODO: We could check for this in init_sccvn, and replace this
2967 with a gcc_assert. */
2968 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
2969 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
2971 /* See if all non-TOP arguments have the same value. TOP is
2972 equivalent to everything, so we can ignore it. */
2973 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2975 tree def
= PHI_ARG_DEF (phi
, i
);
2977 if (TREE_CODE (def
) == SSA_NAME
)
2978 def
= SSA_VAL (def
);
2981 if (sameval
== VN_TOP
)
2987 if (!expressions_equal_p (def
, sameval
))
2995 /* If all value numbered to the same value, the phi node has that
2999 if (is_gimple_min_invariant (sameval
))
3001 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
3002 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3006 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3007 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3010 if (TREE_CODE (sameval
) == SSA_NAME
)
3011 return visit_copy (PHI_RESULT (phi
), sameval
);
3013 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3016 /* Otherwise, see if it is equivalent to a phi node in this block. */
3017 result
= vn_phi_lookup (phi
);
3020 if (TREE_CODE (result
) == SSA_NAME
)
3021 changed
= visit_copy (PHI_RESULT (phi
), result
);
3023 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3027 vn_phi_insert (phi
, PHI_RESULT (phi
));
3028 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3029 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3030 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3036 /* Return true if EXPR contains constants. */
3039 expr_has_constants (tree expr
)
3041 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3044 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3047 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3048 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3049 /* Constants inside reference ops are rarely interesting, but
3050 it can take a lot of looking to find them. */
3052 case tcc_declaration
:
3055 return is_gimple_min_invariant (expr
);
3060 /* Return true if STMT contains constants. */
3063 stmt_has_constants (gimple stmt
)
3065 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3068 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3070 case GIMPLE_UNARY_RHS
:
3071 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
3073 case GIMPLE_BINARY_RHS
:
3074 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
3075 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
)));
3076 case GIMPLE_TERNARY_RHS
:
3077 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
3078 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
))
3079 || is_gimple_min_invariant (gimple_assign_rhs3 (stmt
)));
3080 case GIMPLE_SINGLE_RHS
:
3081 /* Constants inside reference ops are rarely interesting, but
3082 it can take a lot of looking to find them. */
3083 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
3090 /* Replace SSA_NAMES in expr with their value numbers, and return the
3092 This is performed in place. */
3095 valueize_expr (tree expr
)
3097 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3100 TREE_OPERAND (expr
, 1) = vn_valueize (TREE_OPERAND (expr
, 1));
3103 TREE_OPERAND (expr
, 0) = vn_valueize (TREE_OPERAND (expr
, 0));
3110 /* Simplify the binary expression RHS, and return the result if
3114 simplify_binary_expression (gimple stmt
)
3116 tree result
= NULL_TREE
;
3117 tree op0
= gimple_assign_rhs1 (stmt
);
3118 tree op1
= gimple_assign_rhs2 (stmt
);
3119 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3121 /* This will not catch every single case we could combine, but will
3122 catch those with constants. The goal here is to simultaneously
3123 combine constants between expressions, but avoid infinite
3124 expansion of expressions during simplification. */
3125 if (TREE_CODE (op0
) == SSA_NAME
)
3127 if (VN_INFO (op0
)->has_constants
3128 || TREE_CODE_CLASS (code
) == tcc_comparison
3129 || code
== COMPLEX_EXPR
)
3130 op0
= valueize_expr (vn_get_expr_for (op0
));
3132 op0
= vn_valueize (op0
);
3135 if (TREE_CODE (op1
) == SSA_NAME
)
3137 if (VN_INFO (op1
)->has_constants
3138 || code
== COMPLEX_EXPR
)
3139 op1
= valueize_expr (vn_get_expr_for (op1
));
3141 op1
= vn_valueize (op1
);
3144 /* Pointer plus constant can be represented as invariant address.
3145 Do so to allow further propatation, see also tree forwprop. */
3146 if (code
== POINTER_PLUS_EXPR
3147 && host_integerp (op1
, 1)
3148 && TREE_CODE (op0
) == ADDR_EXPR
3149 && is_gimple_min_invariant (op0
))
3150 return build_invariant_address (TREE_TYPE (op0
),
3151 TREE_OPERAND (op0
, 0),
3152 TREE_INT_CST_LOW (op1
));
3154 /* Avoid folding if nothing changed. */
3155 if (op0
== gimple_assign_rhs1 (stmt
)
3156 && op1
== gimple_assign_rhs2 (stmt
))
3159 fold_defer_overflow_warnings ();
3161 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3163 STRIP_USELESS_TYPE_CONVERSION (result
);
3165 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3168 /* Make sure result is not a complex expression consisting
3169 of operators of operators (IE (a + b) + (a + c))
3170 Otherwise, we will end up with unbounded expressions if
3171 fold does anything at all. */
3172 if (result
&& valid_gimple_rhs_p (result
))
3178 /* Simplify the unary expression RHS, and return the result if
3182 simplify_unary_expression (gimple stmt
)
3184 tree result
= NULL_TREE
;
3185 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3186 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3188 /* We handle some tcc_reference codes here that are all
3189 GIMPLE_ASSIGN_SINGLE codes. */
3190 if (code
== REALPART_EXPR
3191 || code
== IMAGPART_EXPR
3192 || code
== VIEW_CONVERT_EXPR
3193 || code
== BIT_FIELD_REF
)
3194 op0
= TREE_OPERAND (op0
, 0);
3196 if (TREE_CODE (op0
) != SSA_NAME
)
3200 if (VN_INFO (op0
)->has_constants
)
3201 op0
= valueize_expr (vn_get_expr_for (op0
));
3202 else if (CONVERT_EXPR_CODE_P (code
)
3203 || code
== REALPART_EXPR
3204 || code
== IMAGPART_EXPR
3205 || code
== VIEW_CONVERT_EXPR
3206 || code
== BIT_FIELD_REF
)
3208 /* We want to do tree-combining on conversion-like expressions.
3209 Make sure we feed only SSA_NAMEs or constants to fold though. */
3210 tree tem
= valueize_expr (vn_get_expr_for (op0
));
3211 if (UNARY_CLASS_P (tem
)
3212 || BINARY_CLASS_P (tem
)
3213 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3214 || TREE_CODE (tem
) == SSA_NAME
3215 || TREE_CODE (tem
) == CONSTRUCTOR
3216 || is_gimple_min_invariant (tem
))
3220 /* Avoid folding if nothing changed, but remember the expression. */
3221 if (op0
== orig_op0
)
3224 if (code
== BIT_FIELD_REF
)
3226 tree rhs
= gimple_assign_rhs1 (stmt
);
3227 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3228 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3231 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3234 STRIP_USELESS_TYPE_CONVERSION (result
);
3235 if (valid_gimple_rhs_p (result
))
3242 /* Try to simplify RHS using equivalences and constant folding. */
3245 try_to_simplify (gimple stmt
)
3247 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3250 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3251 in this case, there is no point in doing extra work. */
3252 if (code
== SSA_NAME
)
3255 /* First try constant folding based on our current lattice. */
3256 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3258 && (TREE_CODE (tem
) == SSA_NAME
3259 || is_gimple_min_invariant (tem
)))
3262 /* If that didn't work try combining multiple statements. */
3263 switch (TREE_CODE_CLASS (code
))
3266 /* Fallthrough for some unary codes that can operate on registers. */
3267 if (!(code
== REALPART_EXPR
3268 || code
== IMAGPART_EXPR
3269 || code
== VIEW_CONVERT_EXPR
3270 || code
== BIT_FIELD_REF
))
3272 /* We could do a little more with unary ops, if they expand
3273 into binary ops, but it's debatable whether it is worth it. */
3275 return simplify_unary_expression (stmt
);
3277 case tcc_comparison
:
3279 return simplify_binary_expression (stmt
);
3288 /* Visit and value number USE, return true if the value number
3292 visit_use (tree use
)
3294 bool changed
= false;
3295 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3297 mark_use_processed (use
);
3299 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3300 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3301 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3303 fprintf (dump_file
, "Value numbering ");
3304 print_generic_expr (dump_file
, use
, 0);
3305 fprintf (dump_file
, " stmt = ");
3306 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3309 /* Handle uninitialized uses. */
3310 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3311 changed
= set_ssa_val_to (use
, use
);
3314 if (gimple_code (stmt
) == GIMPLE_PHI
)
3315 changed
= visit_phi (stmt
);
3316 else if (gimple_has_volatile_ops (stmt
))
3317 changed
= defs_to_varying (stmt
);
3318 else if (is_gimple_assign (stmt
))
3320 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3321 tree lhs
= gimple_assign_lhs (stmt
);
3322 tree rhs1
= gimple_assign_rhs1 (stmt
);
3325 /* Shortcut for copies. Simplifying copies is pointless,
3326 since we copy the expression and value they represent. */
3327 if (code
== SSA_NAME
3328 && TREE_CODE (lhs
) == SSA_NAME
)
3330 changed
= visit_copy (lhs
, rhs1
);
3333 simplified
= try_to_simplify (stmt
);
3336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3338 fprintf (dump_file
, "RHS ");
3339 print_gimple_expr (dump_file
, stmt
, 0, 0);
3340 fprintf (dump_file
, " simplified to ");
3341 print_generic_expr (dump_file
, simplified
, 0);
3342 if (TREE_CODE (lhs
) == SSA_NAME
)
3343 fprintf (dump_file
, " has constants %d\n",
3344 expr_has_constants (simplified
));
3346 fprintf (dump_file
, "\n");
3349 /* Setting value numbers to constants will occasionally
3350 screw up phi congruence because constants are not
3351 uniquely associated with a single ssa name that can be
3354 && is_gimple_min_invariant (simplified
)
3355 && TREE_CODE (lhs
) == SSA_NAME
)
3357 VN_INFO (lhs
)->expr
= simplified
;
3358 VN_INFO (lhs
)->has_constants
= true;
3359 changed
= set_ssa_val_to (lhs
, simplified
);
3363 && TREE_CODE (simplified
) == SSA_NAME
3364 && TREE_CODE (lhs
) == SSA_NAME
)
3366 changed
= visit_copy (lhs
, simplified
);
3369 else if (simplified
)
3371 if (TREE_CODE (lhs
) == SSA_NAME
)
3373 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3374 /* We have to unshare the expression or else
3375 valuizing may change the IL stream. */
3376 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3379 else if (stmt_has_constants (stmt
)
3380 && TREE_CODE (lhs
) == SSA_NAME
)
3381 VN_INFO (lhs
)->has_constants
= true;
3382 else if (TREE_CODE (lhs
) == SSA_NAME
)
3384 /* We reset expr and constantness here because we may
3385 have been value numbering optimistically, and
3386 iterating. They may become non-constant in this case,
3387 even if they were optimistically constant. */
3389 VN_INFO (lhs
)->has_constants
= false;
3390 VN_INFO (lhs
)->expr
= NULL_TREE
;
3393 if ((TREE_CODE (lhs
) == SSA_NAME
3394 /* We can substitute SSA_NAMEs that are live over
3395 abnormal edges with their constant value. */
3396 && !(gimple_assign_copy_p (stmt
)
3397 && is_gimple_min_invariant (rhs1
))
3399 && is_gimple_min_invariant (simplified
))
3400 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3401 /* Stores or copies from SSA_NAMEs that are live over
3402 abnormal edges are a problem. */
3403 || (code
== SSA_NAME
3404 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3405 changed
= defs_to_varying (stmt
);
3406 else if (REFERENCE_CLASS_P (lhs
)
3408 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3409 else if (TREE_CODE (lhs
) == SSA_NAME
)
3411 if ((gimple_assign_copy_p (stmt
)
3412 && is_gimple_min_invariant (rhs1
))
3414 && is_gimple_min_invariant (simplified
)))
3416 VN_INFO (lhs
)->has_constants
= true;
3418 changed
= set_ssa_val_to (lhs
, simplified
);
3420 changed
= set_ssa_val_to (lhs
, rhs1
);
3424 switch (vn_get_stmt_kind (stmt
))
3427 changed
= visit_nary_op (lhs
, stmt
);
3430 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3433 changed
= defs_to_varying (stmt
);
3439 changed
= defs_to_varying (stmt
);
3441 else if (is_gimple_call (stmt
))
3443 tree lhs
= gimple_call_lhs (stmt
);
3445 /* ??? We could try to simplify calls. */
3447 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3449 if (stmt_has_constants (stmt
))
3450 VN_INFO (lhs
)->has_constants
= true;
3453 /* We reset expr and constantness here because we may
3454 have been value numbering optimistically, and
3455 iterating. They may become non-constant in this case,
3456 even if they were optimistically constant. */
3457 VN_INFO (lhs
)->has_constants
= false;
3458 VN_INFO (lhs
)->expr
= NULL_TREE
;
3461 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3463 changed
= defs_to_varying (stmt
);
3468 if (!gimple_call_internal_p (stmt
)
3469 && (/* Calls to the same function with the same vuse
3470 and the same operands do not necessarily return the same
3471 value, unless they're pure or const. */
3472 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3473 /* If calls have a vdef, subsequent calls won't have
3474 the same incoming vuse. So, if 2 calls with vdef have the
3475 same vuse, we know they're not subsequent.
3476 We can value number 2 calls to the same function with the
3477 same vuse and the same operands which are not subsequent
3478 the same, because there is no code in the program that can
3479 compare the 2 values. */
3480 || gimple_vdef (stmt
)))
3481 changed
= visit_reference_op_call (lhs
, stmt
);
3483 changed
= defs_to_varying (stmt
);
3486 changed
= defs_to_varying (stmt
);
3492 /* Compare two operands by reverse postorder index */
3495 compare_ops (const void *pa
, const void *pb
)
3497 const tree opa
= *((const tree
*)pa
);
3498 const tree opb
= *((const tree
*)pb
);
3499 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3500 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3504 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3505 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3506 else if (gimple_nop_p (opstmta
))
3508 else if (gimple_nop_p (opstmtb
))
3511 bba
= gimple_bb (opstmta
);
3512 bbb
= gimple_bb (opstmtb
);
3515 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3523 if (gimple_code (opstmta
) == GIMPLE_PHI
3524 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3525 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3526 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3528 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3530 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3531 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3533 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3535 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3538 /* Sort an array containing members of a strongly connected component
3539 SCC so that the members are ordered by RPO number.
3540 This means that when the sort is complete, iterating through the
3541 array will give you the members in RPO order. */
3544 sort_scc (VEC (tree
, heap
) *scc
)
3546 VEC_qsort (tree
, scc
, compare_ops
);
3549 /* Insert the no longer used nary ONARY to the hash INFO. */
3552 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3554 size_t size
= sizeof_vn_nary_op (onary
->length
);
3555 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3556 &info
->nary_obstack
);
3557 memcpy (nary
, onary
, size
);
3558 vn_nary_op_insert_into (nary
, info
->nary
, false);
3561 /* Insert the no longer used phi OPHI to the hash INFO. */
3564 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3566 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3568 memcpy (phi
, ophi
, sizeof (*phi
));
3569 ophi
->phiargs
= NULL
;
3570 slot
= htab_find_slot_with_hash (info
->phis
, phi
, phi
->hashcode
, INSERT
);
3571 gcc_assert (!*slot
);
3575 /* Insert the no longer used reference OREF to the hash INFO. */
3578 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3582 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3583 memcpy (ref
, oref
, sizeof (*ref
));
3584 oref
->operands
= NULL
;
3585 slot
= htab_find_slot_with_hash (info
->references
, ref
, ref
->hashcode
,
3588 free_reference (*slot
);
3592 /* Process a strongly connected component in the SSA graph. */
3595 process_scc (VEC (tree
, heap
) *scc
)
3599 unsigned int iterations
= 0;
3600 bool changed
= true;
3606 /* If the SCC has a single member, just visit it. */
3607 if (VEC_length (tree
, scc
) == 1)
3609 tree use
= VEC_index (tree
, scc
, 0);
3610 if (VN_INFO (use
)->use_processed
)
3612 /* We need to make sure it doesn't form a cycle itself, which can
3613 happen for self-referential PHI nodes. In that case we would
3614 end up inserting an expression with VN_TOP operands into the
3615 valid table which makes us derive bogus equivalences later.
3616 The cheapest way to check this is to assume it for all PHI nodes. */
3617 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3618 /* Fallthru to iteration. */ ;
3626 /* Iterate over the SCC with the optimistic table until it stops
3628 current_info
= optimistic_info
;
3633 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3634 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3635 /* As we are value-numbering optimistically we have to
3636 clear the expression tables and the simplified expressions
3637 in each iteration until we converge. */
3638 htab_empty (optimistic_info
->nary
);
3639 htab_empty (optimistic_info
->phis
);
3640 htab_empty (optimistic_info
->references
);
3641 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3642 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3643 empty_alloc_pool (optimistic_info
->phis_pool
);
3644 empty_alloc_pool (optimistic_info
->references_pool
);
3645 FOR_EACH_VEC_ELT (tree
, scc
, i
, var
)
3646 VN_INFO (var
)->expr
= NULL_TREE
;
3647 FOR_EACH_VEC_ELT (tree
, scc
, i
, var
)
3648 changed
|= visit_use (var
);
3651 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3653 /* Finally, copy the contents of the no longer used optimistic
3654 table to the valid table. */
3655 FOR_EACH_HTAB_ELEMENT (optimistic_info
->nary
, nary
, vn_nary_op_t
, hi
)
3656 copy_nary (nary
, valid_info
);
3657 FOR_EACH_HTAB_ELEMENT (optimistic_info
->phis
, phi
, vn_phi_t
, hi
)
3658 copy_phi (phi
, valid_info
);
3659 FOR_EACH_HTAB_ELEMENT (optimistic_info
->references
, ref
, vn_reference_t
, hi
)
3660 copy_reference (ref
, valid_info
);
3662 current_info
= valid_info
;
3665 DEF_VEC_O(ssa_op_iter
);
3666 DEF_VEC_ALLOC_O(ssa_op_iter
,heap
);
3668 /* Pop the components of the found SCC for NAME off the SCC stack
3669 and process them. Returns true if all went well, false if
3670 we run into resource limits. */
3673 extract_and_process_scc_for_name (tree name
)
3675 VEC (tree
, heap
) *scc
= NULL
;
3678 /* Found an SCC, pop the components off the SCC stack and
3682 x
= VEC_pop (tree
, sccstack
);
3684 VN_INFO (x
)->on_sccstack
= false;
3685 VEC_safe_push (tree
, heap
, scc
, x
);
3686 } while (x
!= name
);
3688 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3689 if (VEC_length (tree
, scc
)
3690 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3693 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3694 "SCC size %u exceeding %u\n", VEC_length (tree
, scc
),
3695 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3697 VEC_free (tree
, heap
, scc
);
3701 if (VEC_length (tree
, scc
) > 1)
3704 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3705 print_scc (dump_file
, scc
);
3709 VEC_free (tree
, heap
, scc
);
3714 /* Depth first search on NAME to discover and process SCC's in the SSA
3716 Execution of this algorithm relies on the fact that the SCC's are
3717 popped off the stack in topological order.
3718 Returns true if successful, false if we stopped processing SCC's due
3719 to resource constraints. */
3724 VEC(ssa_op_iter
, heap
) *itervec
= NULL
;
3725 VEC(tree
, heap
) *namevec
= NULL
;
3726 use_operand_p usep
= NULL
;
3733 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3734 VN_INFO (name
)->visited
= true;
3735 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3737 VEC_safe_push (tree
, heap
, sccstack
, name
);
3738 VN_INFO (name
)->on_sccstack
= true;
3739 defstmt
= SSA_NAME_DEF_STMT (name
);
3741 /* Recursively DFS on our operands, looking for SCC's. */
3742 if (!gimple_nop_p (defstmt
))
3744 /* Push a new iterator. */
3745 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3746 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3748 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3751 clear_and_done_ssa_iter (&iter
);
3755 /* If we are done processing uses of a name, go up the stack
3756 of iterators and process SCCs as we found them. */
3757 if (op_iter_done (&iter
))
3759 /* See if we found an SCC. */
3760 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3761 if (!extract_and_process_scc_for_name (name
))
3763 VEC_free (tree
, heap
, namevec
);
3764 VEC_free (ssa_op_iter
, heap
, itervec
);
3768 /* Check if we are done. */
3769 if (VEC_empty (tree
, namevec
))
3771 VEC_free (tree
, heap
, namevec
);
3772 VEC_free (ssa_op_iter
, heap
, itervec
);
3776 /* Restore the last use walker and continue walking there. */
3778 name
= VEC_pop (tree
, namevec
);
3779 memcpy (&iter
, &VEC_last (ssa_op_iter
, itervec
),
3780 sizeof (ssa_op_iter
));
3781 VEC_pop (ssa_op_iter
, itervec
);
3782 goto continue_walking
;
3785 use
= USE_FROM_PTR (usep
);
3787 /* Since we handle phi nodes, we will sometimes get
3788 invariants in the use expression. */
3789 if (TREE_CODE (use
) == SSA_NAME
)
3791 if (! (VN_INFO (use
)->visited
))
3793 /* Recurse by pushing the current use walking state on
3794 the stack and starting over. */
3795 VEC_safe_push(ssa_op_iter
, heap
, itervec
, iter
);
3796 VEC_safe_push(tree
, heap
, namevec
, name
);
3801 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3802 VN_INFO (use
)->low
);
3804 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3805 && VN_INFO (use
)->on_sccstack
)
3807 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3808 VN_INFO (name
)->low
);
3812 usep
= op_iter_next_use (&iter
);
3816 /* Allocate a value number table. */
3819 allocate_vn_table (vn_tables_t table
)
3821 table
->phis
= htab_create (23, vn_phi_hash
, vn_phi_eq
, free_phi
);
3822 table
->nary
= htab_create (23, vn_nary_op_hash
, vn_nary_op_eq
, NULL
);
3823 table
->references
= htab_create (23, vn_reference_hash
, vn_reference_eq
,
3826 gcc_obstack_init (&table
->nary_obstack
);
3827 table
->phis_pool
= create_alloc_pool ("VN phis",
3828 sizeof (struct vn_phi_s
),
3830 table
->references_pool
= create_alloc_pool ("VN references",
3831 sizeof (struct vn_reference_s
),
3835 /* Free a value number table. */
3838 free_vn_table (vn_tables_t table
)
3840 htab_delete (table
->phis
);
3841 htab_delete (table
->nary
);
3842 htab_delete (table
->references
);
3843 obstack_free (&table
->nary_obstack
, NULL
);
3844 free_alloc_pool (table
->phis_pool
);
3845 free_alloc_pool (table
->references_pool
);
3853 int *rpo_numbers_temp
;
3855 calculate_dominance_info (CDI_DOMINATORS
);
3857 constant_to_value_id
= htab_create (23, vn_constant_hash
, vn_constant_eq
,
3860 constant_value_ids
= BITMAP_ALLOC (NULL
);
3865 vn_ssa_aux_table
= VEC_alloc (vn_ssa_aux_t
, heap
, num_ssa_names
+ 1);
3866 /* VEC_alloc doesn't actually grow it to the right size, it just
3867 preallocates the space to do so. */
3868 VEC_safe_grow_cleared (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
,
3870 gcc_obstack_init (&vn_ssa_aux_obstack
);
3872 shared_lookup_phiargs
= NULL
;
3873 shared_lookup_references
= NULL
;
3874 rpo_numbers
= XNEWVEC (int, last_basic_block
);
3875 rpo_numbers_temp
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3876 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
3878 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3879 the i'th block in RPO order is bb. We want to map bb's to RPO
3880 numbers, so we need to rearrange this array. */
3881 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
3882 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
3884 XDELETE (rpo_numbers_temp
);
3886 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
3888 /* Create the VN_INFO structures, and initialize value numbers to
3890 for (i
= 0; i
< num_ssa_names
; i
++)
3892 tree name
= ssa_name (i
);
3895 VN_INFO_GET (name
)->valnum
= VN_TOP
;
3896 VN_INFO (name
)->expr
= NULL_TREE
;
3897 VN_INFO (name
)->value_id
= 0;
3901 renumber_gimple_stmt_uids ();
3903 /* Create the valid and optimistic value numbering tables. */
3904 valid_info
= XCNEW (struct vn_tables_s
);
3905 allocate_vn_table (valid_info
);
3906 optimistic_info
= XCNEW (struct vn_tables_s
);
3907 allocate_vn_table (optimistic_info
);
3915 htab_delete (constant_to_value_id
);
3916 BITMAP_FREE (constant_value_ids
);
3917 VEC_free (tree
, heap
, shared_lookup_phiargs
);
3918 VEC_free (vn_reference_op_s
, heap
, shared_lookup_references
);
3919 XDELETEVEC (rpo_numbers
);
3921 for (i
= 0; i
< num_ssa_names
; i
++)
3923 tree name
= ssa_name (i
);
3925 && VN_INFO (name
)->needs_insertion
)
3926 release_ssa_name (name
);
3928 obstack_free (&vn_ssa_aux_obstack
, NULL
);
3929 VEC_free (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
);
3931 VEC_free (tree
, heap
, sccstack
);
3932 free_vn_table (valid_info
);
3933 XDELETE (valid_info
);
3934 free_vn_table (optimistic_info
);
3935 XDELETE (optimistic_info
);
3938 /* Set *ID if we computed something useful in RESULT. */
3941 set_value_id_for_result (tree result
, unsigned int *id
)
3945 if (TREE_CODE (result
) == SSA_NAME
)
3946 *id
= VN_INFO (result
)->value_id
;
3947 else if (is_gimple_min_invariant (result
))
3948 *id
= get_or_alloc_constant_value_id (result
);
3952 /* Set the value ids in the valid hash tables. */
3955 set_hashtable_value_ids (void)
3962 /* Now set the value ids of the things we had put in the hash
3965 FOR_EACH_HTAB_ELEMENT (valid_info
->nary
,
3966 vno
, vn_nary_op_t
, hi
)
3967 set_value_id_for_result (vno
->result
, &vno
->value_id
);
3969 FOR_EACH_HTAB_ELEMENT (valid_info
->phis
,
3971 set_value_id_for_result (vp
->result
, &vp
->value_id
);
3973 FOR_EACH_HTAB_ELEMENT (valid_info
->references
,
3974 vr
, vn_reference_t
, hi
)
3975 set_value_id_for_result (vr
->result
, &vr
->value_id
);
3978 /* Do SCCVN. Returns true if it finished, false if we bailed out
3979 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
3980 how we use the alias oracle walking during the VN process. */
3983 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
3987 bool changed
= true;
3989 default_vn_walk_kind
= default_vn_walk_kind_
;
3992 current_info
= valid_info
;
3994 for (param
= DECL_ARGUMENTS (current_function_decl
);
3996 param
= DECL_CHAIN (param
))
3998 tree def
= ssa_default_def (cfun
, param
);
4000 VN_INFO (def
)->valnum
= def
;
4003 for (i
= 1; i
< num_ssa_names
; ++i
)
4005 tree name
= ssa_name (i
);
4007 && VN_INFO (name
)->visited
== false
4008 && !has_zero_uses (name
))
4016 /* Initialize the value ids. */
4018 for (i
= 1; i
< num_ssa_names
; ++i
)
4020 tree name
= ssa_name (i
);
4024 info
= VN_INFO (name
);
4025 if (info
->valnum
== name
4026 || info
->valnum
== VN_TOP
)
4027 info
->value_id
= get_next_value_id ();
4028 else if (is_gimple_min_invariant (info
->valnum
))
4029 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4032 /* Propagate until they stop changing. */
4036 for (i
= 1; i
< num_ssa_names
; ++i
)
4038 tree name
= ssa_name (i
);
4042 info
= VN_INFO (name
);
4043 if (TREE_CODE (info
->valnum
) == SSA_NAME
4044 && info
->valnum
!= name
4045 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4048 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4053 set_hashtable_value_ids ();
4055 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4057 fprintf (dump_file
, "Value numbers:\n");
4058 for (i
= 0; i
< num_ssa_names
; i
++)
4060 tree name
= ssa_name (i
);
4062 && VN_INFO (name
)->visited
4063 && SSA_VAL (name
) != name
)
4065 print_generic_expr (dump_file
, name
, 0);
4066 fprintf (dump_file
, " = ");
4067 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4068 fprintf (dump_file
, "\n");
4076 /* Return the maximum value id we have ever seen. */
4079 get_max_value_id (void)
4081 return next_value_id
;
4084 /* Return the next unique value id. */
4087 get_next_value_id (void)
4089 return next_value_id
++;
4093 /* Compare two expressions E1 and E2 and return true if they are equal. */
4096 expressions_equal_p (tree e1
, tree e2
)
4098 /* The obvious case. */
4102 /* If only one of them is null, they cannot be equal. */
4106 /* Now perform the actual comparison. */
4107 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4108 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4115 /* Return true if the nary operation NARY may trap. This is a copy
4116 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4119 vn_nary_may_trap (vn_nary_op_t nary
)
4122 tree rhs2
= NULL_TREE
;
4123 bool honor_nans
= false;
4124 bool honor_snans
= false;
4125 bool fp_operation
= false;
4126 bool honor_trapv
= false;
4130 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4131 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4132 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4135 fp_operation
= FLOAT_TYPE_P (type
);
4138 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4139 honor_snans
= flag_signaling_nans
!= 0;
4141 else if (INTEGRAL_TYPE_P (type
)
4142 && TYPE_OVERFLOW_TRAPS (type
))
4145 if (nary
->length
>= 2)
4147 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4149 honor_nans
, honor_snans
, rhs2
,
4155 for (i
= 0; i
< nary
->length
; ++i
)
4156 if (tree_could_trap_p (nary
->op
[i
]))