1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012
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 (vn_walk_kind
== VN_WALKREWRITE
1559 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1560 && ref
->size
== maxsize
1561 && maxsize
% BITS_PER_UNIT
== 0
1562 && offset
% BITS_PER_UNIT
== 0
1563 && is_gimple_reg_type (vr
->type
)
1564 && gimple_assign_single_p (def_stmt
)
1565 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1568 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1569 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1570 &offset2
, &size2
, &maxsize2
);
1572 && maxsize2
== size2
1573 && size2
% BITS_PER_UNIT
== 0
1574 && offset2
% BITS_PER_UNIT
== 0
1575 && operand_equal_p (base
, base2
, 0)
1576 && offset2
<= offset
1577 && offset2
+ size2
>= offset
+ maxsize
)
1579 /* We support up to 512-bit values (for V8DFmode). */
1580 unsigned char buffer
[64];
1583 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1584 buffer
, sizeof (buffer
));
1587 tree val
= native_interpret_expr (vr
->type
,
1589 + ((offset
- offset2
)
1591 ref
->size
/ BITS_PER_UNIT
);
1593 return vn_reference_lookup_or_insert_for_pieces
1594 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1599 /* 4) Assignment from an SSA name which definition we may be able
1600 to access pieces from. */
1601 else if (ref
->size
== maxsize
1602 && is_gimple_reg_type (vr
->type
)
1603 && gimple_assign_single_p (def_stmt
)
1604 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1606 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1607 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1608 if (is_gimple_assign (def_stmt2
)
1609 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1610 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1611 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1614 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1615 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1616 &offset2
, &size2
, &maxsize2
);
1617 off
= offset
- offset2
;
1619 && maxsize2
== size2
1620 && operand_equal_p (base
, base2
, 0)
1621 && offset2
<= offset
1622 && offset2
+ size2
>= offset
+ maxsize
)
1624 tree val
= NULL_TREE
;
1626 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1627 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1630 val
= gimple_assign_rhs1 (def_stmt2
);
1631 else if (off
== elsz
)
1632 val
= gimple_assign_rhs2 (def_stmt2
);
1634 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1637 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1638 unsigned i
= off
/ elsz
;
1639 if (i
< CONSTRUCTOR_NELTS (ctor
))
1641 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1642 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1644 if (TREE_CODE (TREE_TYPE (elt
->value
))
1651 return vn_reference_lookup_or_insert_for_pieces
1652 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1657 /* 5) For aggregate copies translate the reference through them if
1658 the copy kills ref. */
1659 else if (vn_walk_kind
== VN_WALKREWRITE
1660 && gimple_assign_single_p (def_stmt
)
1661 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1662 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1663 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1666 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1668 VEC (vn_reference_op_s
, heap
) *rhs
= NULL
;
1669 vn_reference_op_t vro
;
1675 /* See if the assignment kills REF. */
1676 base2
= ao_ref_base (&lhs_ref
);
1677 offset2
= lhs_ref
.offset
;
1678 size2
= lhs_ref
.size
;
1679 maxsize2
= lhs_ref
.max_size
;
1681 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1683 || offset2
+ size2
< offset
+ maxsize
)
1686 /* Find the common base of ref and the lhs. lhs_ops already
1687 contains valueized operands for the lhs. */
1688 i
= VEC_length (vn_reference_op_s
, vr
->operands
) - 1;
1689 j
= VEC_length (vn_reference_op_s
, lhs_ops
) - 1;
1690 while (j
>= 0 && i
>= 0
1691 && vn_reference_op_eq (&VEC_index (vn_reference_op_s
,
1693 &VEC_index (vn_reference_op_s
, lhs_ops
, j
)))
1699 /* ??? The innermost op should always be a MEM_REF and we already
1700 checked that the assignment to the lhs kills vr. Thus for
1701 aggregate copies using char[] types the vn_reference_op_eq
1702 may fail when comparing types for compatibility. But we really
1703 don't care here - further lookups with the rewritten operands
1704 will simply fail if we messed up types too badly. */
1705 if (j
== 0 && i
>= 0
1706 && VEC_index (vn_reference_op_s
, lhs_ops
, 0).opcode
== MEM_REF
1707 && VEC_index (vn_reference_op_s
, lhs_ops
, 0).off
!= -1
1708 && (VEC_index (vn_reference_op_s
, lhs_ops
, 0).off
1709 == VEC_index (vn_reference_op_s
, vr
->operands
, i
).off
))
1712 /* i now points to the first additional op.
1713 ??? LHS may not be completely contained in VR, one or more
1714 VIEW_CONVERT_EXPRs could be in its way. We could at least
1715 try handling outermost VIEW_CONVERT_EXPRs. */
1719 /* Now re-write REF to be based on the rhs of the assignment. */
1720 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1721 /* We need to pre-pend vr->operands[0..i] to rhs. */
1722 if (i
+ 1 + VEC_length (vn_reference_op_s
, rhs
)
1723 > VEC_length (vn_reference_op_s
, vr
->operands
))
1725 VEC (vn_reference_op_s
, heap
) *old
= vr
->operands
;
1726 VEC_safe_grow (vn_reference_op_s
, heap
, vr
->operands
,
1727 i
+ 1 + VEC_length (vn_reference_op_s
, rhs
));
1728 if (old
== shared_lookup_references
1729 && vr
->operands
!= old
)
1730 shared_lookup_references
= NULL
;
1733 VEC_truncate (vn_reference_op_s
, vr
->operands
,
1734 i
+ 1 + VEC_length (vn_reference_op_s
, rhs
));
1735 FOR_EACH_VEC_ELT (vn_reference_op_s
, rhs
, j
, vro
)
1736 VEC_replace (vn_reference_op_s
, vr
->operands
, i
+ 1 + j
, *vro
);
1737 VEC_free (vn_reference_op_s
, heap
, rhs
);
1738 vr
->operands
= valueize_refs (vr
->operands
);
1739 vr
->hashcode
= vn_reference_compute_hash (vr
);
1741 /* Adjust *ref from the new operands. */
1742 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1744 /* This can happen with bitfields. */
1745 if (ref
->size
!= r
.size
)
1749 /* Do not update last seen VUSE after translating. */
1750 last_vuse_ptr
= NULL
;
1752 /* Keep looking for the adjusted *REF / VR pair. */
1756 /* 6) For memcpy copies translate the reference through them if
1757 the copy kills ref. */
1758 else if (vn_walk_kind
== VN_WALKREWRITE
1759 && is_gimple_reg_type (vr
->type
)
1760 /* ??? Handle BCOPY as well. */
1761 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1762 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1763 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1764 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1765 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1766 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1767 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1768 && host_integerp (gimple_call_arg (def_stmt
, 2), 1))
1772 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1773 vn_reference_op_s op
;
1777 /* Only handle non-variable, addressable refs. */
1778 if (ref
->size
!= maxsize
1779 || offset
% BITS_PER_UNIT
!= 0
1780 || ref
->size
% BITS_PER_UNIT
!= 0)
1783 /* Extract a pointer base and an offset for the destination. */
1784 lhs
= gimple_call_arg (def_stmt
, 0);
1786 if (TREE_CODE (lhs
) == SSA_NAME
)
1787 lhs
= SSA_VAL (lhs
);
1788 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1790 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1794 if (TREE_CODE (tem
) == MEM_REF
1795 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1797 lhs
= TREE_OPERAND (tem
, 0);
1798 lhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1800 else if (DECL_P (tem
))
1801 lhs
= build_fold_addr_expr (tem
);
1805 if (TREE_CODE (lhs
) != SSA_NAME
1806 && TREE_CODE (lhs
) != ADDR_EXPR
)
1809 /* Extract a pointer base and an offset for the source. */
1810 rhs
= gimple_call_arg (def_stmt
, 1);
1812 if (TREE_CODE (rhs
) == SSA_NAME
)
1813 rhs
= SSA_VAL (rhs
);
1814 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1816 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1820 if (TREE_CODE (tem
) == MEM_REF
1821 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1823 rhs
= TREE_OPERAND (tem
, 0);
1824 rhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1826 else if (DECL_P (tem
))
1827 rhs
= build_fold_addr_expr (tem
);
1831 if (TREE_CODE (rhs
) != SSA_NAME
1832 && TREE_CODE (rhs
) != ADDR_EXPR
)
1835 copy_size
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2));
1837 /* The bases of the destination and the references have to agree. */
1838 if ((TREE_CODE (base
) != MEM_REF
1840 || (TREE_CODE (base
) == MEM_REF
1841 && (TREE_OPERAND (base
, 0) != lhs
1842 || !host_integerp (TREE_OPERAND (base
, 1), 1)))
1844 && (TREE_CODE (lhs
) != ADDR_EXPR
1845 || TREE_OPERAND (lhs
, 0) != base
)))
1848 /* And the access has to be contained within the memcpy destination. */
1849 at
= offset
/ BITS_PER_UNIT
;
1850 if (TREE_CODE (base
) == MEM_REF
)
1851 at
+= TREE_INT_CST_LOW (TREE_OPERAND (base
, 1));
1853 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1856 /* Make room for 2 operands in the new reference. */
1857 if (VEC_length (vn_reference_op_s
, vr
->operands
) < 2)
1859 VEC (vn_reference_op_s
, heap
) *old
= vr
->operands
;
1860 VEC_safe_grow (vn_reference_op_s
, heap
, vr
->operands
, 2);
1861 if (old
== shared_lookup_references
1862 && vr
->operands
!= old
)
1863 shared_lookup_references
= NULL
;
1866 VEC_truncate (vn_reference_op_s
, vr
->operands
, 2);
1868 /* The looked-through reference is a simple MEM_REF. */
1869 memset (&op
, 0, sizeof (op
));
1871 op
.opcode
= MEM_REF
;
1872 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
1873 op
.off
= at
- lhs_offset
+ rhs_offset
;
1874 VEC_replace (vn_reference_op_s
, vr
->operands
, 0, op
);
1875 op
.type
= TREE_TYPE (rhs
);
1876 op
.opcode
= TREE_CODE (rhs
);
1879 VEC_replace (vn_reference_op_s
, vr
->operands
, 1, op
);
1880 vr
->hashcode
= vn_reference_compute_hash (vr
);
1882 /* Adjust *ref from the new operands. */
1883 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1885 /* This can happen with bitfields. */
1886 if (ref
->size
!= r
.size
)
1890 /* Do not update last seen VUSE after translating. */
1891 last_vuse_ptr
= NULL
;
1893 /* Keep looking for the adjusted *REF / VR pair. */
1897 /* Bail out and stop walking. */
1901 /* Lookup a reference operation by it's parts, in the current hash table.
1902 Returns the resulting value number if it exists in the hash table,
1903 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1904 vn_reference_t stored in the hashtable if something is found. */
1907 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
1908 VEC (vn_reference_op_s
, heap
) *operands
,
1909 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
1911 struct vn_reference_s vr1
;
1919 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1920 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
1921 VEC_safe_grow (vn_reference_op_s
, heap
, shared_lookup_references
,
1922 VEC_length (vn_reference_op_s
, operands
));
1923 memcpy (VEC_address (vn_reference_op_s
, shared_lookup_references
),
1924 VEC_address (vn_reference_op_s
, operands
),
1925 sizeof (vn_reference_op_s
)
1926 * VEC_length (vn_reference_op_s
, operands
));
1927 vr1
.operands
= operands
= shared_lookup_references
1928 = valueize_refs (shared_lookup_references
);
1931 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1932 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
1935 vn_reference_lookup_1 (&vr1
, vnresult
);
1937 && kind
!= VN_NOWALK
1941 vn_walk_kind
= kind
;
1942 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
1944 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1945 vn_reference_lookup_2
,
1946 vn_reference_lookup_3
, &vr1
);
1947 if (vr1
.operands
!= operands
)
1948 VEC_free (vn_reference_op_s
, heap
, vr1
.operands
);
1952 return (*vnresult
)->result
;
1957 /* Lookup OP in the current hash table, and return the resulting value
1958 number if it exists in the hash table. Return NULL_TREE if it does
1959 not exist in the hash table or if the result field of the structure
1960 was NULL.. VNRESULT will be filled in with the vn_reference_t
1961 stored in the hashtable if one exists. */
1964 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
1965 vn_reference_t
*vnresult
)
1967 VEC (vn_reference_op_s
, heap
) *operands
;
1968 struct vn_reference_s vr1
;
1970 bool valuezied_anything
;
1975 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1976 vr1
.operands
= operands
1977 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
1978 vr1
.type
= TREE_TYPE (op
);
1979 vr1
.set
= get_alias_set (op
);
1980 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1981 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
1984 if (kind
!= VN_NOWALK
1987 vn_reference_t wvnresult
;
1989 /* Make sure to use a valueized reference if we valueized anything.
1990 Otherwise preserve the full reference for advanced TBAA. */
1991 if (!valuezied_anything
1992 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
1994 ao_ref_init (&r
, op
);
1995 vn_walk_kind
= kind
;
1997 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1998 vn_reference_lookup_2
,
1999 vn_reference_lookup_3
, &vr1
);
2000 if (vr1
.operands
!= operands
)
2001 VEC_free (vn_reference_op_s
, heap
, vr1
.operands
);
2005 *vnresult
= wvnresult
;
2006 return wvnresult
->result
;
2012 return vn_reference_lookup_1 (&vr1
, vnresult
);
2016 /* Insert OP into the current hash table with a value number of
2017 RESULT, and return the resulting reference structure we created. */
2020 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2025 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2026 if (TREE_CODE (result
) == SSA_NAME
)
2027 vr1
->value_id
= VN_INFO (result
)->value_id
;
2029 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2030 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2031 vr1
->operands
= valueize_refs (create_reference_ops_from_ref (op
));
2032 vr1
->type
= TREE_TYPE (op
);
2033 vr1
->set
= get_alias_set (op
);
2034 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2035 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2036 vr1
->result_vdef
= vdef
;
2038 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
2041 /* Because we lookup stores using vuses, and value number failures
2042 using the vdefs (see visit_reference_op_store for how and why),
2043 it's possible that on failure we may try to insert an already
2044 inserted store. This is not wrong, there is no ssa name for a
2045 store that we could use as a differentiator anyway. Thus, unlike
2046 the other lookup functions, you cannot gcc_assert (!*slot)
2049 /* But free the old slot in case of a collision. */
2051 free_reference (*slot
);
2057 /* Insert a reference by it's pieces into the current hash table with
2058 a value number of RESULT. Return the resulting reference
2059 structure we created. */
2062 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2063 VEC (vn_reference_op_s
, heap
) *operands
,
2064 tree result
, unsigned int value_id
)
2070 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2071 vr1
->value_id
= value_id
;
2072 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2073 vr1
->operands
= valueize_refs (operands
);
2076 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2077 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2078 result
= SSA_VAL (result
);
2079 vr1
->result
= result
;
2081 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
2084 /* At this point we should have all the things inserted that we have
2085 seen before, and we should never try inserting something that
2087 gcc_assert (!*slot
);
2089 free_reference (*slot
);
2095 /* Compute and return the hash value for nary operation VBO1. */
2098 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2103 for (i
= 0; i
< vno1
->length
; ++i
)
2104 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2105 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2107 if (vno1
->length
== 2
2108 && commutative_tree_code (vno1
->opcode
)
2109 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2111 tree temp
= vno1
->op
[0];
2112 vno1
->op
[0] = vno1
->op
[1];
2116 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2117 for (i
= 0; i
< vno1
->length
; ++i
)
2118 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2123 /* Return the computed hashcode for nary operation P1. */
2126 vn_nary_op_hash (const void *p1
)
2128 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
2129 return vno1
->hashcode
;
2132 /* Compare nary operations P1 and P2 and return true if they are
2136 vn_nary_op_eq (const void *p1
, const void *p2
)
2138 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
2139 const_vn_nary_op_t
const vno2
= (const_vn_nary_op_t
) p2
;
2142 if (vno1
->hashcode
!= vno2
->hashcode
)
2145 if (vno1
->length
!= vno2
->length
)
2148 if (vno1
->opcode
!= vno2
->opcode
2149 || !types_compatible_p (vno1
->type
, vno2
->type
))
2152 for (i
= 0; i
< vno1
->length
; ++i
)
2153 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2159 /* Initialize VNO from the pieces provided. */
2162 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2163 enum tree_code code
, tree type
, tree
*ops
)
2166 vno
->length
= length
;
2168 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2171 /* Initialize VNO from OP. */
2174 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2178 vno
->opcode
= TREE_CODE (op
);
2179 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2180 vno
->type
= TREE_TYPE (op
);
2181 for (i
= 0; i
< vno
->length
; ++i
)
2182 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2185 /* Return the number of operands for a vn_nary ops structure from STMT. */
2188 vn_nary_length_from_stmt (gimple stmt
)
2190 switch (gimple_assign_rhs_code (stmt
))
2194 case VIEW_CONVERT_EXPR
:
2198 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2201 return gimple_num_ops (stmt
) - 1;
2205 /* Initialize VNO from STMT. */
2208 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2212 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2213 vno
->type
= gimple_expr_type (stmt
);
2214 switch (vno
->opcode
)
2218 case VIEW_CONVERT_EXPR
:
2220 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2224 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2225 for (i
= 0; i
< vno
->length
; ++i
)
2226 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2230 vno
->length
= gimple_num_ops (stmt
) - 1;
2231 for (i
= 0; i
< vno
->length
; ++i
)
2232 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2236 /* Compute the hashcode for VNO and look for it in the hash table;
2237 return the resulting value number if it exists in the hash table.
2238 Return NULL_TREE if it does not exist in the hash table or if the
2239 result field of the operation is NULL. VNRESULT will contain the
2240 vn_nary_op_t from the hashtable if it exists. */
2243 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2250 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2251 slot
= htab_find_slot_with_hash (current_info
->nary
, vno
, vno
->hashcode
,
2253 if (!slot
&& current_info
== optimistic_info
)
2254 slot
= htab_find_slot_with_hash (valid_info
->nary
, vno
, vno
->hashcode
,
2259 *vnresult
= (vn_nary_op_t
)*slot
;
2260 return ((vn_nary_op_t
)*slot
)->result
;
2263 /* Lookup a n-ary operation by its pieces and return the resulting value
2264 number if it exists in the hash table. Return NULL_TREE if it does
2265 not exist in the hash table or if the result field of the operation
2266 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2270 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2271 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2273 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2274 sizeof_vn_nary_op (length
));
2275 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2276 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2279 /* Lookup OP in the current hash table, and return the resulting value
2280 number if it exists in the hash table. Return NULL_TREE if it does
2281 not exist in the hash table or if the result field of the operation
2282 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2286 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2289 = XALLOCAVAR (struct vn_nary_op_s
,
2290 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2291 init_vn_nary_op_from_op (vno1
, op
);
2292 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2295 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2296 value number if it exists in the hash table. Return NULL_TREE if
2297 it does not exist in the hash table. VNRESULT will contain the
2298 vn_nary_op_t from the hashtable if it exists. */
2301 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2304 = XALLOCAVAR (struct vn_nary_op_s
,
2305 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2306 init_vn_nary_op_from_stmt (vno1
, stmt
);
2307 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2310 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2313 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2315 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2318 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2322 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2324 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2325 ¤t_info
->nary_obstack
);
2327 vno1
->value_id
= value_id
;
2328 vno1
->length
= length
;
2329 vno1
->result
= result
;
2334 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2335 VNO->HASHCODE first. */
2338 vn_nary_op_insert_into (vn_nary_op_t vno
, htab_t table
, bool compute_hash
)
2343 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2345 slot
= htab_find_slot_with_hash (table
, vno
, vno
->hashcode
, INSERT
);
2346 gcc_assert (!*slot
);
2352 /* Insert a n-ary operation into the current hash table using it's
2353 pieces. Return the vn_nary_op_t structure we created and put in
2357 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2358 tree type
, tree
*ops
,
2359 tree result
, unsigned int value_id
)
2361 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2362 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2363 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2366 /* Insert OP into the current hash table with a value number of
2367 RESULT. Return the vn_nary_op_t structure we created and put in
2371 vn_nary_op_insert (tree op
, tree result
)
2373 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2376 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2377 init_vn_nary_op_from_op (vno1
, op
);
2378 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2381 /* Insert the rhs of STMT into the current hash table with a value number of
2385 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2388 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2389 result
, VN_INFO (result
)->value_id
);
2390 init_vn_nary_op_from_stmt (vno1
, stmt
);
2391 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2394 /* Compute a hashcode for PHI operation VP1 and return it. */
2396 static inline hashval_t
2397 vn_phi_compute_hash (vn_phi_t vp1
)
2404 result
= vp1
->block
->index
;
2406 /* If all PHI arguments are constants we need to distinguish
2407 the PHI node via its type. */
2408 type
= TREE_TYPE (VEC_index (tree
, vp1
->phiargs
, 0));
2409 result
+= (INTEGRAL_TYPE_P (type
)
2410 + (INTEGRAL_TYPE_P (type
)
2411 ? TYPE_PRECISION (type
) + TYPE_UNSIGNED (type
) : 0));
2413 FOR_EACH_VEC_ELT (tree
, vp1
->phiargs
, i
, phi1op
)
2415 if (phi1op
== VN_TOP
)
2417 result
= iterative_hash_expr (phi1op
, result
);
2423 /* Return the computed hashcode for phi operation P1. */
2426 vn_phi_hash (const void *p1
)
2428 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
2429 return vp1
->hashcode
;
2432 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2435 vn_phi_eq (const void *p1
, const void *p2
)
2437 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
2438 const_vn_phi_t
const vp2
= (const_vn_phi_t
) p2
;
2440 if (vp1
->hashcode
!= vp2
->hashcode
)
2443 if (vp1
->block
== vp2
->block
)
2448 /* If the PHI nodes do not have compatible types
2449 they are not the same. */
2450 if (!types_compatible_p (TREE_TYPE (VEC_index (tree
, vp1
->phiargs
, 0)),
2451 TREE_TYPE (VEC_index (tree
, vp2
->phiargs
, 0))))
2454 /* Any phi in the same block will have it's arguments in the
2455 same edge order, because of how we store phi nodes. */
2456 FOR_EACH_VEC_ELT (tree
, vp1
->phiargs
, i
, phi1op
)
2458 tree phi2op
= VEC_index (tree
, vp2
->phiargs
, i
);
2459 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2461 if (!expressions_equal_p (phi1op
, phi2op
))
2469 static VEC(tree
, heap
) *shared_lookup_phiargs
;
2471 /* Lookup PHI in the current hash table, and return the resulting
2472 value number if it exists in the hash table. Return NULL_TREE if
2473 it does not exist in the hash table. */
2476 vn_phi_lookup (gimple phi
)
2479 struct vn_phi_s vp1
;
2482 VEC_truncate (tree
, shared_lookup_phiargs
, 0);
2484 /* Canonicalize the SSA_NAME's to their value number. */
2485 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2487 tree def
= PHI_ARG_DEF (phi
, i
);
2488 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2489 VEC_safe_push (tree
, heap
, shared_lookup_phiargs
, def
);
2491 vp1
.phiargs
= shared_lookup_phiargs
;
2492 vp1
.block
= gimple_bb (phi
);
2493 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2494 slot
= htab_find_slot_with_hash (current_info
->phis
, &vp1
, vp1
.hashcode
,
2496 if (!slot
&& current_info
== optimistic_info
)
2497 slot
= htab_find_slot_with_hash (valid_info
->phis
, &vp1
, vp1
.hashcode
,
2501 return ((vn_phi_t
)*slot
)->result
;
2504 /* Insert PHI into the current hash table with a value number of
2508 vn_phi_insert (gimple phi
, tree result
)
2511 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2513 VEC (tree
, heap
) *args
= NULL
;
2515 /* Canonicalize the SSA_NAME's to their value number. */
2516 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2518 tree def
= PHI_ARG_DEF (phi
, i
);
2519 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2520 VEC_safe_push (tree
, heap
, args
, def
);
2522 vp1
->value_id
= VN_INFO (result
)->value_id
;
2523 vp1
->phiargs
= args
;
2524 vp1
->block
= gimple_bb (phi
);
2525 vp1
->result
= result
;
2526 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2528 slot
= htab_find_slot_with_hash (current_info
->phis
, vp1
, vp1
->hashcode
,
2531 /* Because we iterate over phi operations more than once, it's
2532 possible the slot might already exist here, hence no assert.*/
2538 /* Print set of components in strongly connected component SCC to OUT. */
2541 print_scc (FILE *out
, VEC (tree
, heap
) *scc
)
2546 fprintf (out
, "SCC consists of:");
2547 FOR_EACH_VEC_ELT (tree
, scc
, i
, var
)
2550 print_generic_expr (out
, var
, 0);
2552 fprintf (out
, "\n");
2555 /* Set the value number of FROM to TO, return true if it has changed
2559 set_ssa_val_to (tree from
, tree to
)
2561 tree currval
= SSA_VAL (from
);
2565 if (currval
== from
)
2567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2569 fprintf (dump_file
, "Not changing value number of ");
2570 print_generic_expr (dump_file
, from
, 0);
2571 fprintf (dump_file
, " from VARYING to ");
2572 print_generic_expr (dump_file
, to
, 0);
2573 fprintf (dump_file
, "\n");
2577 else if (TREE_CODE (to
) == SSA_NAME
2578 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2582 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2583 and invariants. So assert that here. */
2584 gcc_assert (to
!= NULL_TREE
2586 || TREE_CODE (to
) == SSA_NAME
2587 || is_gimple_min_invariant (to
)));
2589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2591 fprintf (dump_file
, "Setting value number of ");
2592 print_generic_expr (dump_file
, from
, 0);
2593 fprintf (dump_file
, " to ");
2594 print_generic_expr (dump_file
, to
, 0);
2597 if (currval
!= to
&& !operand_equal_p (currval
, to
, OEP_PURE_SAME
))
2599 VN_INFO (from
)->valnum
= to
;
2600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2601 fprintf (dump_file
, " (changed)\n");
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2605 fprintf (dump_file
, "\n");
2609 /* Mark as processed all the definitions in the defining stmt of USE, or
2613 mark_use_processed (tree use
)
2617 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2619 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2621 VN_INFO (use
)->use_processed
= true;
2625 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2627 tree def
= DEF_FROM_PTR (defp
);
2629 VN_INFO (def
)->use_processed
= true;
2633 /* Set all definitions in STMT to value number to themselves.
2634 Return true if a value number changed. */
2637 defs_to_varying (gimple stmt
)
2639 bool changed
= false;
2643 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2645 tree def
= DEF_FROM_PTR (defp
);
2646 changed
|= set_ssa_val_to (def
, def
);
2651 static bool expr_has_constants (tree expr
);
2652 static tree
valueize_expr (tree expr
);
2654 /* Visit a copy between LHS and RHS, return true if the value number
2658 visit_copy (tree lhs
, tree rhs
)
2660 /* Follow chains of copies to their destination. */
2661 while (TREE_CODE (rhs
) == SSA_NAME
2662 && SSA_VAL (rhs
) != rhs
)
2663 rhs
= SSA_VAL (rhs
);
2665 /* The copy may have a more interesting constant filled expression
2666 (we don't, since we know our RHS is just an SSA name). */
2667 if (TREE_CODE (rhs
) == SSA_NAME
)
2669 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2670 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2673 return set_ssa_val_to (lhs
, rhs
);
2676 /* Visit a nary operator RHS, value number it, and return true if the
2677 value number of LHS has changed as a result. */
2680 visit_nary_op (tree lhs
, gimple stmt
)
2682 bool changed
= false;
2683 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2686 changed
= set_ssa_val_to (lhs
, result
);
2689 changed
= set_ssa_val_to (lhs
, lhs
);
2690 vn_nary_op_insert_stmt (stmt
, lhs
);
2696 /* Visit a call STMT storing into LHS. Return true if the value number
2697 of the LHS has changed as a result. */
2700 visit_reference_op_call (tree lhs
, gimple stmt
)
2702 bool changed
= false;
2703 struct vn_reference_s vr1
;
2704 vn_reference_t vnresult
= NULL
;
2705 tree vuse
= gimple_vuse (stmt
);
2706 tree vdef
= gimple_vdef (stmt
);
2708 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2709 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2712 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2713 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2714 vr1
.type
= gimple_expr_type (stmt
);
2716 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2717 vn_reference_lookup_1 (&vr1
, &vnresult
);
2721 if (vnresult
->result_vdef
)
2722 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2724 if (!vnresult
->result
&& lhs
)
2725 vnresult
->result
= lhs
;
2727 if (vnresult
->result
&& lhs
)
2729 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2731 if (VN_INFO (vnresult
->result
)->has_constants
)
2732 VN_INFO (lhs
)->has_constants
= true;
2740 changed
|= set_ssa_val_to (vdef
, vdef
);
2742 changed
|= set_ssa_val_to (lhs
, lhs
);
2743 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2744 vr2
->vuse
= vr1
.vuse
;
2745 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2746 vr2
->type
= vr1
.type
;
2748 vr2
->hashcode
= vr1
.hashcode
;
2750 vr2
->result_vdef
= vdef
;
2751 slot
= htab_find_slot_with_hash (current_info
->references
,
2752 vr2
, vr2
->hashcode
, INSERT
);
2754 free_reference (*slot
);
2761 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2762 and return true if the value number of the LHS has changed as a result. */
2765 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2767 bool changed
= false;
2771 last_vuse
= gimple_vuse (stmt
);
2772 last_vuse_ptr
= &last_vuse
;
2773 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2774 default_vn_walk_kind
, NULL
);
2775 last_vuse_ptr
= NULL
;
2777 /* If we have a VCE, try looking up its operand as it might be stored in
2778 a different type. */
2779 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2780 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2781 default_vn_walk_kind
, NULL
);
2783 /* We handle type-punning through unions by value-numbering based
2784 on offset and size of the access. Be prepared to handle a
2785 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2787 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2789 /* We will be setting the value number of lhs to the value number
2790 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2791 So first simplify and lookup this expression to see if it
2792 is already available. */
2793 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2794 if ((CONVERT_EXPR_P (val
)
2795 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2796 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2798 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2799 if ((CONVERT_EXPR_P (tem
)
2800 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2801 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2802 TREE_TYPE (val
), tem
)))
2806 if (!is_gimple_min_invariant (val
)
2807 && TREE_CODE (val
) != SSA_NAME
)
2808 result
= vn_nary_op_lookup (val
, NULL
);
2809 /* If the expression is not yet available, value-number lhs to
2810 a new SSA_NAME we create. */
2813 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2815 /* Initialize value-number information properly. */
2816 VN_INFO_GET (result
)->valnum
= result
;
2817 VN_INFO (result
)->value_id
= get_next_value_id ();
2818 VN_INFO (result
)->expr
= val
;
2819 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2820 VN_INFO (result
)->needs_insertion
= true;
2821 /* As all "inserted" statements are singleton SCCs, insert
2822 to the valid table. This is strictly needed to
2823 avoid re-generating new value SSA_NAMEs for the same
2824 expression during SCC iteration over and over (the
2825 optimistic table gets cleared after each iteration).
2826 We do not need to insert into the optimistic table, as
2827 lookups there will fall back to the valid table. */
2828 if (current_info
== optimistic_info
)
2830 current_info
= valid_info
;
2831 vn_nary_op_insert (val
, result
);
2832 current_info
= optimistic_info
;
2835 vn_nary_op_insert (val
, result
);
2836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2838 fprintf (dump_file
, "Inserting name ");
2839 print_generic_expr (dump_file
, result
, 0);
2840 fprintf (dump_file
, " for expression ");
2841 print_generic_expr (dump_file
, val
, 0);
2842 fprintf (dump_file
, "\n");
2849 changed
= set_ssa_val_to (lhs
, result
);
2850 if (TREE_CODE (result
) == SSA_NAME
2851 && VN_INFO (result
)->has_constants
)
2853 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2854 VN_INFO (lhs
)->has_constants
= true;
2859 changed
= set_ssa_val_to (lhs
, lhs
);
2860 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
2867 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2868 and return true if the value number of the LHS has changed as a result. */
2871 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2873 bool changed
= false;
2874 vn_reference_t vnresult
= NULL
;
2875 tree result
, assign
;
2876 bool resultsame
= false;
2877 tree vuse
= gimple_vuse (stmt
);
2878 tree vdef
= gimple_vdef (stmt
);
2880 /* First we want to lookup using the *vuses* from the store and see
2881 if there the last store to this location with the same address
2884 The vuses represent the memory state before the store. If the
2885 memory state, address, and value of the store is the same as the
2886 last store to this location, then this store will produce the
2887 same memory state as that store.
2889 In this case the vdef versions for this store are value numbered to those
2890 vuse versions, since they represent the same memory state after
2893 Otherwise, the vdefs for the store are used when inserting into
2894 the table, since the store generates a new memory state. */
2896 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
2900 if (TREE_CODE (result
) == SSA_NAME
)
2901 result
= SSA_VAL (result
);
2902 if (TREE_CODE (op
) == SSA_NAME
)
2904 resultsame
= expressions_equal_p (result
, op
);
2907 if (!result
|| !resultsame
)
2909 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2910 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
2913 VN_INFO (vdef
)->use_processed
= true;
2914 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2918 if (!result
|| !resultsame
)
2920 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2922 fprintf (dump_file
, "No store match\n");
2923 fprintf (dump_file
, "Value numbering store ");
2924 print_generic_expr (dump_file
, lhs
, 0);
2925 fprintf (dump_file
, " to ");
2926 print_generic_expr (dump_file
, op
, 0);
2927 fprintf (dump_file
, "\n");
2929 /* Have to set value numbers before insert, since insert is
2930 going to valueize the references in-place. */
2933 changed
|= set_ssa_val_to (vdef
, vdef
);
2936 /* Do not insert structure copies into the tables. */
2937 if (is_gimple_min_invariant (op
)
2938 || is_gimple_reg (op
))
2939 vn_reference_insert (lhs
, op
, vdef
, NULL
);
2941 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2942 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
2946 /* We had a match, so value number the vdef to have the value
2947 number of the vuse it came from. */
2949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2950 fprintf (dump_file
, "Store matched earlier value,"
2951 "value numbering store vdefs to matching vuses.\n");
2953 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
2959 /* Visit and value number PHI, return true if the value number
2963 visit_phi (gimple phi
)
2965 bool changed
= false;
2967 tree sameval
= VN_TOP
;
2968 bool allsame
= true;
2971 /* TODO: We could check for this in init_sccvn, and replace this
2972 with a gcc_assert. */
2973 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
2974 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
2976 /* See if all non-TOP arguments have the same value. TOP is
2977 equivalent to everything, so we can ignore it. */
2978 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2980 tree def
= PHI_ARG_DEF (phi
, i
);
2982 if (TREE_CODE (def
) == SSA_NAME
)
2983 def
= SSA_VAL (def
);
2986 if (sameval
== VN_TOP
)
2992 if (!expressions_equal_p (def
, sameval
))
3000 /* If all value numbered to the same value, the phi node has that
3004 if (is_gimple_min_invariant (sameval
))
3006 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
3007 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3011 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3012 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3015 if (TREE_CODE (sameval
) == SSA_NAME
)
3016 return visit_copy (PHI_RESULT (phi
), sameval
);
3018 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3021 /* Otherwise, see if it is equivalent to a phi node in this block. */
3022 result
= vn_phi_lookup (phi
);
3025 if (TREE_CODE (result
) == SSA_NAME
)
3026 changed
= visit_copy (PHI_RESULT (phi
), result
);
3028 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3032 vn_phi_insert (phi
, PHI_RESULT (phi
));
3033 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3034 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3035 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3041 /* Return true if EXPR contains constants. */
3044 expr_has_constants (tree expr
)
3046 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3049 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3052 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3053 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3054 /* Constants inside reference ops are rarely interesting, but
3055 it can take a lot of looking to find them. */
3057 case tcc_declaration
:
3060 return is_gimple_min_invariant (expr
);
3065 /* Return true if STMT contains constants. */
3068 stmt_has_constants (gimple stmt
)
3070 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3073 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3075 case GIMPLE_UNARY_RHS
:
3076 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
3078 case GIMPLE_BINARY_RHS
:
3079 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
3080 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
)));
3081 case GIMPLE_TERNARY_RHS
:
3082 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
3083 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
))
3084 || is_gimple_min_invariant (gimple_assign_rhs3 (stmt
)));
3085 case GIMPLE_SINGLE_RHS
:
3086 /* Constants inside reference ops are rarely interesting, but
3087 it can take a lot of looking to find them. */
3088 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
3095 /* Replace SSA_NAMES in expr with their value numbers, and return the
3097 This is performed in place. */
3100 valueize_expr (tree expr
)
3102 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3105 TREE_OPERAND (expr
, 1) = vn_valueize (TREE_OPERAND (expr
, 1));
3108 TREE_OPERAND (expr
, 0) = vn_valueize (TREE_OPERAND (expr
, 0));
3115 /* Simplify the binary expression RHS, and return the result if
3119 simplify_binary_expression (gimple stmt
)
3121 tree result
= NULL_TREE
;
3122 tree op0
= gimple_assign_rhs1 (stmt
);
3123 tree op1
= gimple_assign_rhs2 (stmt
);
3124 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3126 /* This will not catch every single case we could combine, but will
3127 catch those with constants. The goal here is to simultaneously
3128 combine constants between expressions, but avoid infinite
3129 expansion of expressions during simplification. */
3130 if (TREE_CODE (op0
) == SSA_NAME
)
3132 if (VN_INFO (op0
)->has_constants
3133 || TREE_CODE_CLASS (code
) == tcc_comparison
3134 || code
== COMPLEX_EXPR
)
3135 op0
= valueize_expr (vn_get_expr_for (op0
));
3137 op0
= vn_valueize (op0
);
3140 if (TREE_CODE (op1
) == SSA_NAME
)
3142 if (VN_INFO (op1
)->has_constants
3143 || code
== COMPLEX_EXPR
)
3144 op1
= valueize_expr (vn_get_expr_for (op1
));
3146 op1
= vn_valueize (op1
);
3149 /* Pointer plus constant can be represented as invariant address.
3150 Do so to allow further propatation, see also tree forwprop. */
3151 if (code
== POINTER_PLUS_EXPR
3152 && host_integerp (op1
, 1)
3153 && TREE_CODE (op0
) == ADDR_EXPR
3154 && is_gimple_min_invariant (op0
))
3155 return build_invariant_address (TREE_TYPE (op0
),
3156 TREE_OPERAND (op0
, 0),
3157 TREE_INT_CST_LOW (op1
));
3159 /* Avoid folding if nothing changed. */
3160 if (op0
== gimple_assign_rhs1 (stmt
)
3161 && op1
== gimple_assign_rhs2 (stmt
))
3164 fold_defer_overflow_warnings ();
3166 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3168 STRIP_USELESS_TYPE_CONVERSION (result
);
3170 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3173 /* Make sure result is not a complex expression consisting
3174 of operators of operators (IE (a + b) + (a + c))
3175 Otherwise, we will end up with unbounded expressions if
3176 fold does anything at all. */
3177 if (result
&& valid_gimple_rhs_p (result
))
3183 /* Simplify the unary expression RHS, and return the result if
3187 simplify_unary_expression (gimple stmt
)
3189 tree result
= NULL_TREE
;
3190 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3191 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3193 /* We handle some tcc_reference codes here that are all
3194 GIMPLE_ASSIGN_SINGLE codes. */
3195 if (code
== REALPART_EXPR
3196 || code
== IMAGPART_EXPR
3197 || code
== VIEW_CONVERT_EXPR
3198 || code
== BIT_FIELD_REF
)
3199 op0
= TREE_OPERAND (op0
, 0);
3201 if (TREE_CODE (op0
) != SSA_NAME
)
3205 if (VN_INFO (op0
)->has_constants
)
3206 op0
= valueize_expr (vn_get_expr_for (op0
));
3207 else if (CONVERT_EXPR_CODE_P (code
)
3208 || code
== REALPART_EXPR
3209 || code
== IMAGPART_EXPR
3210 || code
== VIEW_CONVERT_EXPR
3211 || code
== BIT_FIELD_REF
)
3213 /* We want to do tree-combining on conversion-like expressions.
3214 Make sure we feed only SSA_NAMEs or constants to fold though. */
3215 tree tem
= valueize_expr (vn_get_expr_for (op0
));
3216 if (UNARY_CLASS_P (tem
)
3217 || BINARY_CLASS_P (tem
)
3218 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3219 || TREE_CODE (tem
) == SSA_NAME
3220 || TREE_CODE (tem
) == CONSTRUCTOR
3221 || is_gimple_min_invariant (tem
))
3225 /* Avoid folding if nothing changed, but remember the expression. */
3226 if (op0
== orig_op0
)
3229 if (code
== BIT_FIELD_REF
)
3231 tree rhs
= gimple_assign_rhs1 (stmt
);
3232 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3233 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3236 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3239 STRIP_USELESS_TYPE_CONVERSION (result
);
3240 if (valid_gimple_rhs_p (result
))
3247 /* Try to simplify RHS using equivalences and constant folding. */
3250 try_to_simplify (gimple stmt
)
3252 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3255 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3256 in this case, there is no point in doing extra work. */
3257 if (code
== SSA_NAME
)
3260 /* First try constant folding based on our current lattice. */
3261 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3263 && (TREE_CODE (tem
) == SSA_NAME
3264 || is_gimple_min_invariant (tem
)))
3267 /* If that didn't work try combining multiple statements. */
3268 switch (TREE_CODE_CLASS (code
))
3271 /* Fallthrough for some unary codes that can operate on registers. */
3272 if (!(code
== REALPART_EXPR
3273 || code
== IMAGPART_EXPR
3274 || code
== VIEW_CONVERT_EXPR
3275 || code
== BIT_FIELD_REF
))
3277 /* We could do a little more with unary ops, if they expand
3278 into binary ops, but it's debatable whether it is worth it. */
3280 return simplify_unary_expression (stmt
);
3282 case tcc_comparison
:
3284 return simplify_binary_expression (stmt
);
3293 /* Visit and value number USE, return true if the value number
3297 visit_use (tree use
)
3299 bool changed
= false;
3300 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3302 mark_use_processed (use
);
3304 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3305 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3306 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3308 fprintf (dump_file
, "Value numbering ");
3309 print_generic_expr (dump_file
, use
, 0);
3310 fprintf (dump_file
, " stmt = ");
3311 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3314 /* Handle uninitialized uses. */
3315 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3316 changed
= set_ssa_val_to (use
, use
);
3319 if (gimple_code (stmt
) == GIMPLE_PHI
)
3320 changed
= visit_phi (stmt
);
3321 else if (gimple_has_volatile_ops (stmt
))
3322 changed
= defs_to_varying (stmt
);
3323 else if (is_gimple_assign (stmt
))
3325 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3326 tree lhs
= gimple_assign_lhs (stmt
);
3327 tree rhs1
= gimple_assign_rhs1 (stmt
);
3330 /* Shortcut for copies. Simplifying copies is pointless,
3331 since we copy the expression and value they represent. */
3332 if (code
== SSA_NAME
3333 && TREE_CODE (lhs
) == SSA_NAME
)
3335 changed
= visit_copy (lhs
, rhs1
);
3338 simplified
= try_to_simplify (stmt
);
3341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3343 fprintf (dump_file
, "RHS ");
3344 print_gimple_expr (dump_file
, stmt
, 0, 0);
3345 fprintf (dump_file
, " simplified to ");
3346 print_generic_expr (dump_file
, simplified
, 0);
3347 if (TREE_CODE (lhs
) == SSA_NAME
)
3348 fprintf (dump_file
, " has constants %d\n",
3349 expr_has_constants (simplified
));
3351 fprintf (dump_file
, "\n");
3354 /* Setting value numbers to constants will occasionally
3355 screw up phi congruence because constants are not
3356 uniquely associated with a single ssa name that can be
3359 && is_gimple_min_invariant (simplified
)
3360 && TREE_CODE (lhs
) == SSA_NAME
)
3362 VN_INFO (lhs
)->expr
= simplified
;
3363 VN_INFO (lhs
)->has_constants
= true;
3364 changed
= set_ssa_val_to (lhs
, simplified
);
3368 && TREE_CODE (simplified
) == SSA_NAME
3369 && TREE_CODE (lhs
) == SSA_NAME
)
3371 changed
= visit_copy (lhs
, simplified
);
3374 else if (simplified
)
3376 if (TREE_CODE (lhs
) == SSA_NAME
)
3378 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3379 /* We have to unshare the expression or else
3380 valuizing may change the IL stream. */
3381 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3384 else if (stmt_has_constants (stmt
)
3385 && TREE_CODE (lhs
) == SSA_NAME
)
3386 VN_INFO (lhs
)->has_constants
= true;
3387 else if (TREE_CODE (lhs
) == SSA_NAME
)
3389 /* We reset expr and constantness here because we may
3390 have been value numbering optimistically, and
3391 iterating. They may become non-constant in this case,
3392 even if they were optimistically constant. */
3394 VN_INFO (lhs
)->has_constants
= false;
3395 VN_INFO (lhs
)->expr
= NULL_TREE
;
3398 if ((TREE_CODE (lhs
) == SSA_NAME
3399 /* We can substitute SSA_NAMEs that are live over
3400 abnormal edges with their constant value. */
3401 && !(gimple_assign_copy_p (stmt
)
3402 && is_gimple_min_invariant (rhs1
))
3404 && is_gimple_min_invariant (simplified
))
3405 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3406 /* Stores or copies from SSA_NAMEs that are live over
3407 abnormal edges are a problem. */
3408 || (code
== SSA_NAME
3409 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3410 changed
= defs_to_varying (stmt
);
3411 else if (REFERENCE_CLASS_P (lhs
)
3413 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3414 else if (TREE_CODE (lhs
) == SSA_NAME
)
3416 if ((gimple_assign_copy_p (stmt
)
3417 && is_gimple_min_invariant (rhs1
))
3419 && is_gimple_min_invariant (simplified
)))
3421 VN_INFO (lhs
)->has_constants
= true;
3423 changed
= set_ssa_val_to (lhs
, simplified
);
3425 changed
= set_ssa_val_to (lhs
, rhs1
);
3429 switch (vn_get_stmt_kind (stmt
))
3432 changed
= visit_nary_op (lhs
, stmt
);
3435 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3438 changed
= defs_to_varying (stmt
);
3444 changed
= defs_to_varying (stmt
);
3446 else if (is_gimple_call (stmt
))
3448 tree lhs
= gimple_call_lhs (stmt
);
3450 /* ??? We could try to simplify calls. */
3452 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3454 if (stmt_has_constants (stmt
))
3455 VN_INFO (lhs
)->has_constants
= true;
3458 /* We reset expr and constantness here because we may
3459 have been value numbering optimistically, and
3460 iterating. They may become non-constant in this case,
3461 even if they were optimistically constant. */
3462 VN_INFO (lhs
)->has_constants
= false;
3463 VN_INFO (lhs
)->expr
= NULL_TREE
;
3466 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3468 changed
= defs_to_varying (stmt
);
3473 if (!gimple_call_internal_p (stmt
)
3474 && (/* Calls to the same function with the same vuse
3475 and the same operands do not necessarily return the same
3476 value, unless they're pure or const. */
3477 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3478 /* If calls have a vdef, subsequent calls won't have
3479 the same incoming vuse. So, if 2 calls with vdef have the
3480 same vuse, we know they're not subsequent.
3481 We can value number 2 calls to the same function with the
3482 same vuse and the same operands which are not subsequent
3483 the same, because there is no code in the program that can
3484 compare the 2 values. */
3485 || gimple_vdef (stmt
)))
3486 changed
= visit_reference_op_call (lhs
, stmt
);
3488 changed
= defs_to_varying (stmt
);
3491 changed
= defs_to_varying (stmt
);
3497 /* Compare two operands by reverse postorder index */
3500 compare_ops (const void *pa
, const void *pb
)
3502 const tree opa
= *((const tree
*)pa
);
3503 const tree opb
= *((const tree
*)pb
);
3504 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3505 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3509 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3510 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3511 else if (gimple_nop_p (opstmta
))
3513 else if (gimple_nop_p (opstmtb
))
3516 bba
= gimple_bb (opstmta
);
3517 bbb
= gimple_bb (opstmtb
);
3520 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3528 if (gimple_code (opstmta
) == GIMPLE_PHI
3529 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3530 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3531 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3533 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3535 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3536 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3538 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3540 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3543 /* Sort an array containing members of a strongly connected component
3544 SCC so that the members are ordered by RPO number.
3545 This means that when the sort is complete, iterating through the
3546 array will give you the members in RPO order. */
3549 sort_scc (VEC (tree
, heap
) *scc
)
3551 VEC_qsort (tree
, scc
, compare_ops
);
3554 /* Insert the no longer used nary ONARY to the hash INFO. */
3557 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3559 size_t size
= sizeof_vn_nary_op (onary
->length
);
3560 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3561 &info
->nary_obstack
);
3562 memcpy (nary
, onary
, size
);
3563 vn_nary_op_insert_into (nary
, info
->nary
, false);
3566 /* Insert the no longer used phi OPHI to the hash INFO. */
3569 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3571 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3573 memcpy (phi
, ophi
, sizeof (*phi
));
3574 ophi
->phiargs
= NULL
;
3575 slot
= htab_find_slot_with_hash (info
->phis
, phi
, phi
->hashcode
, INSERT
);
3576 gcc_assert (!*slot
);
3580 /* Insert the no longer used reference OREF to the hash INFO. */
3583 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3587 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3588 memcpy (ref
, oref
, sizeof (*ref
));
3589 oref
->operands
= NULL
;
3590 slot
= htab_find_slot_with_hash (info
->references
, ref
, ref
->hashcode
,
3593 free_reference (*slot
);
3597 /* Process a strongly connected component in the SSA graph. */
3600 process_scc (VEC (tree
, heap
) *scc
)
3604 unsigned int iterations
= 0;
3605 bool changed
= true;
3611 /* If the SCC has a single member, just visit it. */
3612 if (VEC_length (tree
, scc
) == 1)
3614 tree use
= VEC_index (tree
, scc
, 0);
3615 if (VN_INFO (use
)->use_processed
)
3617 /* We need to make sure it doesn't form a cycle itself, which can
3618 happen for self-referential PHI nodes. In that case we would
3619 end up inserting an expression with VN_TOP operands into the
3620 valid table which makes us derive bogus equivalences later.
3621 The cheapest way to check this is to assume it for all PHI nodes. */
3622 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3623 /* Fallthru to iteration. */ ;
3631 /* Iterate over the SCC with the optimistic table until it stops
3633 current_info
= optimistic_info
;
3638 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3639 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3640 /* As we are value-numbering optimistically we have to
3641 clear the expression tables and the simplified expressions
3642 in each iteration until we converge. */
3643 htab_empty (optimistic_info
->nary
);
3644 htab_empty (optimistic_info
->phis
);
3645 htab_empty (optimistic_info
->references
);
3646 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3647 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3648 empty_alloc_pool (optimistic_info
->phis_pool
);
3649 empty_alloc_pool (optimistic_info
->references_pool
);
3650 FOR_EACH_VEC_ELT (tree
, scc
, i
, var
)
3651 VN_INFO (var
)->expr
= NULL_TREE
;
3652 FOR_EACH_VEC_ELT (tree
, scc
, i
, var
)
3653 changed
|= visit_use (var
);
3656 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3658 /* Finally, copy the contents of the no longer used optimistic
3659 table to the valid table. */
3660 FOR_EACH_HTAB_ELEMENT (optimistic_info
->nary
, nary
, vn_nary_op_t
, hi
)
3661 copy_nary (nary
, valid_info
);
3662 FOR_EACH_HTAB_ELEMENT (optimistic_info
->phis
, phi
, vn_phi_t
, hi
)
3663 copy_phi (phi
, valid_info
);
3664 FOR_EACH_HTAB_ELEMENT (optimistic_info
->references
, ref
, vn_reference_t
, hi
)
3665 copy_reference (ref
, valid_info
);
3667 current_info
= valid_info
;
3670 DEF_VEC_O(ssa_op_iter
);
3671 DEF_VEC_ALLOC_O(ssa_op_iter
,heap
);
3673 /* Pop the components of the found SCC for NAME off the SCC stack
3674 and process them. Returns true if all went well, false if
3675 we run into resource limits. */
3678 extract_and_process_scc_for_name (tree name
)
3680 VEC (tree
, heap
) *scc
= NULL
;
3683 /* Found an SCC, pop the components off the SCC stack and
3687 x
= VEC_pop (tree
, sccstack
);
3689 VN_INFO (x
)->on_sccstack
= false;
3690 VEC_safe_push (tree
, heap
, scc
, x
);
3691 } while (x
!= name
);
3693 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3694 if (VEC_length (tree
, scc
)
3695 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3698 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3699 "SCC size %u exceeding %u\n", VEC_length (tree
, scc
),
3700 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3702 VEC_free (tree
, heap
, scc
);
3706 if (VEC_length (tree
, scc
) > 1)
3709 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3710 print_scc (dump_file
, scc
);
3714 VEC_free (tree
, heap
, scc
);
3719 /* Depth first search on NAME to discover and process SCC's in the SSA
3721 Execution of this algorithm relies on the fact that the SCC's are
3722 popped off the stack in topological order.
3723 Returns true if successful, false if we stopped processing SCC's due
3724 to resource constraints. */
3729 VEC(ssa_op_iter
, heap
) *itervec
= NULL
;
3730 VEC(tree
, heap
) *namevec
= NULL
;
3731 use_operand_p usep
= NULL
;
3738 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3739 VN_INFO (name
)->visited
= true;
3740 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3742 VEC_safe_push (tree
, heap
, sccstack
, name
);
3743 VN_INFO (name
)->on_sccstack
= true;
3744 defstmt
= SSA_NAME_DEF_STMT (name
);
3746 /* Recursively DFS on our operands, looking for SCC's. */
3747 if (!gimple_nop_p (defstmt
))
3749 /* Push a new iterator. */
3750 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3751 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3753 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3756 clear_and_done_ssa_iter (&iter
);
3760 /* If we are done processing uses of a name, go up the stack
3761 of iterators and process SCCs as we found them. */
3762 if (op_iter_done (&iter
))
3764 /* See if we found an SCC. */
3765 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3766 if (!extract_and_process_scc_for_name (name
))
3768 VEC_free (tree
, heap
, namevec
);
3769 VEC_free (ssa_op_iter
, heap
, itervec
);
3773 /* Check if we are done. */
3774 if (VEC_empty (tree
, namevec
))
3776 VEC_free (tree
, heap
, namevec
);
3777 VEC_free (ssa_op_iter
, heap
, itervec
);
3781 /* Restore the last use walker and continue walking there. */
3783 name
= VEC_pop (tree
, namevec
);
3784 memcpy (&iter
, &VEC_last (ssa_op_iter
, itervec
),
3785 sizeof (ssa_op_iter
));
3786 VEC_pop (ssa_op_iter
, itervec
);
3787 goto continue_walking
;
3790 use
= USE_FROM_PTR (usep
);
3792 /* Since we handle phi nodes, we will sometimes get
3793 invariants in the use expression. */
3794 if (TREE_CODE (use
) == SSA_NAME
)
3796 if (! (VN_INFO (use
)->visited
))
3798 /* Recurse by pushing the current use walking state on
3799 the stack and starting over. */
3800 VEC_safe_push(ssa_op_iter
, heap
, itervec
, iter
);
3801 VEC_safe_push(tree
, heap
, namevec
, name
);
3806 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3807 VN_INFO (use
)->low
);
3809 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3810 && VN_INFO (use
)->on_sccstack
)
3812 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3813 VN_INFO (name
)->low
);
3817 usep
= op_iter_next_use (&iter
);
3821 /* Allocate a value number table. */
3824 allocate_vn_table (vn_tables_t table
)
3826 table
->phis
= htab_create (23, vn_phi_hash
, vn_phi_eq
, free_phi
);
3827 table
->nary
= htab_create (23, vn_nary_op_hash
, vn_nary_op_eq
, NULL
);
3828 table
->references
= htab_create (23, vn_reference_hash
, vn_reference_eq
,
3831 gcc_obstack_init (&table
->nary_obstack
);
3832 table
->phis_pool
= create_alloc_pool ("VN phis",
3833 sizeof (struct vn_phi_s
),
3835 table
->references_pool
= create_alloc_pool ("VN references",
3836 sizeof (struct vn_reference_s
),
3840 /* Free a value number table. */
3843 free_vn_table (vn_tables_t table
)
3845 htab_delete (table
->phis
);
3846 htab_delete (table
->nary
);
3847 htab_delete (table
->references
);
3848 obstack_free (&table
->nary_obstack
, NULL
);
3849 free_alloc_pool (table
->phis_pool
);
3850 free_alloc_pool (table
->references_pool
);
3858 int *rpo_numbers_temp
;
3860 calculate_dominance_info (CDI_DOMINATORS
);
3862 constant_to_value_id
= htab_create (23, vn_constant_hash
, vn_constant_eq
,
3865 constant_value_ids
= BITMAP_ALLOC (NULL
);
3870 vn_ssa_aux_table
= VEC_alloc (vn_ssa_aux_t
, heap
, num_ssa_names
+ 1);
3871 /* VEC_alloc doesn't actually grow it to the right size, it just
3872 preallocates the space to do so. */
3873 VEC_safe_grow_cleared (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
,
3875 gcc_obstack_init (&vn_ssa_aux_obstack
);
3877 shared_lookup_phiargs
= NULL
;
3878 shared_lookup_references
= NULL
;
3879 rpo_numbers
= XNEWVEC (int, last_basic_block
);
3880 rpo_numbers_temp
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3881 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
3883 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3884 the i'th block in RPO order is bb. We want to map bb's to RPO
3885 numbers, so we need to rearrange this array. */
3886 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
3887 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
3889 XDELETE (rpo_numbers_temp
);
3891 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
3893 /* Create the VN_INFO structures, and initialize value numbers to
3895 for (i
= 0; i
< num_ssa_names
; i
++)
3897 tree name
= ssa_name (i
);
3900 VN_INFO_GET (name
)->valnum
= VN_TOP
;
3901 VN_INFO (name
)->expr
= NULL_TREE
;
3902 VN_INFO (name
)->value_id
= 0;
3906 renumber_gimple_stmt_uids ();
3908 /* Create the valid and optimistic value numbering tables. */
3909 valid_info
= XCNEW (struct vn_tables_s
);
3910 allocate_vn_table (valid_info
);
3911 optimistic_info
= XCNEW (struct vn_tables_s
);
3912 allocate_vn_table (optimistic_info
);
3920 htab_delete (constant_to_value_id
);
3921 BITMAP_FREE (constant_value_ids
);
3922 VEC_free (tree
, heap
, shared_lookup_phiargs
);
3923 VEC_free (vn_reference_op_s
, heap
, shared_lookup_references
);
3924 XDELETEVEC (rpo_numbers
);
3926 for (i
= 0; i
< num_ssa_names
; i
++)
3928 tree name
= ssa_name (i
);
3930 && VN_INFO (name
)->needs_insertion
)
3931 release_ssa_name (name
);
3933 obstack_free (&vn_ssa_aux_obstack
, NULL
);
3934 VEC_free (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
);
3936 VEC_free (tree
, heap
, sccstack
);
3937 free_vn_table (valid_info
);
3938 XDELETE (valid_info
);
3939 free_vn_table (optimistic_info
);
3940 XDELETE (optimistic_info
);
3943 /* Set *ID if we computed something useful in RESULT. */
3946 set_value_id_for_result (tree result
, unsigned int *id
)
3950 if (TREE_CODE (result
) == SSA_NAME
)
3951 *id
= VN_INFO (result
)->value_id
;
3952 else if (is_gimple_min_invariant (result
))
3953 *id
= get_or_alloc_constant_value_id (result
);
3957 /* Set the value ids in the valid hash tables. */
3960 set_hashtable_value_ids (void)
3967 /* Now set the value ids of the things we had put in the hash
3970 FOR_EACH_HTAB_ELEMENT (valid_info
->nary
,
3971 vno
, vn_nary_op_t
, hi
)
3972 set_value_id_for_result (vno
->result
, &vno
->value_id
);
3974 FOR_EACH_HTAB_ELEMENT (valid_info
->phis
,
3976 set_value_id_for_result (vp
->result
, &vp
->value_id
);
3978 FOR_EACH_HTAB_ELEMENT (valid_info
->references
,
3979 vr
, vn_reference_t
, hi
)
3980 set_value_id_for_result (vr
->result
, &vr
->value_id
);
3983 /* Do SCCVN. Returns true if it finished, false if we bailed out
3984 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
3985 how we use the alias oracle walking during the VN process. */
3988 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
3992 bool changed
= true;
3994 default_vn_walk_kind
= default_vn_walk_kind_
;
3997 current_info
= valid_info
;
3999 for (param
= DECL_ARGUMENTS (current_function_decl
);
4001 param
= DECL_CHAIN (param
))
4003 tree def
= ssa_default_def (cfun
, param
);
4005 VN_INFO (def
)->valnum
= def
;
4008 for (i
= 1; i
< num_ssa_names
; ++i
)
4010 tree name
= ssa_name (i
);
4012 && VN_INFO (name
)->visited
== false
4013 && !has_zero_uses (name
))
4021 /* Initialize the value ids. */
4023 for (i
= 1; i
< num_ssa_names
; ++i
)
4025 tree name
= ssa_name (i
);
4029 info
= VN_INFO (name
);
4030 if (info
->valnum
== name
4031 || info
->valnum
== VN_TOP
)
4032 info
->value_id
= get_next_value_id ();
4033 else if (is_gimple_min_invariant (info
->valnum
))
4034 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4037 /* Propagate until they stop changing. */
4041 for (i
= 1; i
< num_ssa_names
; ++i
)
4043 tree name
= ssa_name (i
);
4047 info
= VN_INFO (name
);
4048 if (TREE_CODE (info
->valnum
) == SSA_NAME
4049 && info
->valnum
!= name
4050 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4053 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4058 set_hashtable_value_ids ();
4060 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4062 fprintf (dump_file
, "Value numbers:\n");
4063 for (i
= 0; i
< num_ssa_names
; i
++)
4065 tree name
= ssa_name (i
);
4067 && VN_INFO (name
)->visited
4068 && SSA_VAL (name
) != name
)
4070 print_generic_expr (dump_file
, name
, 0);
4071 fprintf (dump_file
, " = ");
4072 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4073 fprintf (dump_file
, "\n");
4081 /* Return the maximum value id we have ever seen. */
4084 get_max_value_id (void)
4086 return next_value_id
;
4089 /* Return the next unique value id. */
4092 get_next_value_id (void)
4094 return next_value_id
++;
4098 /* Compare two expressions E1 and E2 and return true if they are equal. */
4101 expressions_equal_p (tree e1
, tree e2
)
4103 /* The obvious case. */
4107 /* If only one of them is null, they cannot be equal. */
4111 /* Now perform the actual comparison. */
4112 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4113 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4120 /* Return true if the nary operation NARY may trap. This is a copy
4121 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4124 vn_nary_may_trap (vn_nary_op_t nary
)
4127 tree rhs2
= NULL_TREE
;
4128 bool honor_nans
= false;
4129 bool honor_snans
= false;
4130 bool fp_operation
= false;
4131 bool honor_trapv
= false;
4135 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4136 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4137 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4140 fp_operation
= FLOAT_TYPE_P (type
);
4143 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4144 honor_snans
= flag_signaling_nans
!= 0;
4146 else if (INTEGRAL_TYPE_P (type
)
4147 && TYPE_OVERFLOW_TRAPS (type
))
4150 if (nary
->length
>= 2)
4152 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4154 honor_nans
, honor_snans
, rhs2
,
4160 for (i
= 0; i
< nary
->length
; ++i
)
4161 if (tree_could_trap_p (nary
->op
[i
]))