1 /* SCC value numbering for trees
2 Copyright (C) 2006-2013 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
28 #include "tree-inline.h"
29 #include "tree-flow.h"
33 #include "alloc-pool.h"
38 #include "tree-ssa-propagate.h"
39 #include "tree-ssa-sccvn.h"
40 #include "gimple-fold.h"
42 /* This algorithm is based on the SCC algorithm presented by Keith
43 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
44 (http://citeseer.ist.psu.edu/41805.html). In
45 straight line code, it is equivalent to a regular hash based value
46 numbering that is performed in reverse postorder.
48 For code with cycles, there are two alternatives, both of which
49 require keeping the hashtables separate from the actual list of
50 value numbers for SSA names.
52 1. Iterate value numbering in an RPO walk of the blocks, removing
53 all the entries from the hashtable after each iteration (but
54 keeping the SSA name->value number mapping between iterations).
55 Iterate until it does not change.
57 2. Perform value numbering as part of an SCC walk on the SSA graph,
58 iterating only the cycles in the SSA graph until they do not change
59 (using a separate, optimistic hashtable for value numbering the SCC
62 The second is not just faster in practice (because most SSA graph
63 cycles do not involve all the variables in the graph), it also has
66 One of these nice properties is that when we pop an SCC off the
67 stack, we are guaranteed to have processed all the operands coming from
68 *outside of that SCC*, so we do not need to do anything special to
69 ensure they have value numbers.
71 Another nice property is that the SCC walk is done as part of a DFS
72 of the SSA graph, which makes it easy to perform combining and
73 simplifying operations at the same time.
75 The code below is deliberately written in a way that makes it easy
76 to separate the SCC walk from the other work it does.
78 In order to propagate constants through the code, we track which
79 expressions contain constants, and use those while folding. In
80 theory, we could also track expressions whose value numbers are
81 replaced, in case we end up folding based on expression
84 In order to value number memory, we assign value numbers to vuses.
85 This enables us to note that, for example, stores to the same
86 address of the same value from the same starting memory states are
90 1. We can iterate only the changing portions of the SCC's, but
91 I have not seen an SCC big enough for this to be a win.
92 2. If you differentiate between phi nodes for loops and phi nodes
93 for if-then-else, you can properly consider phi nodes in different
94 blocks for equivalence.
95 3. We could value number vuses in more cases, particularly, whole
99 /* The set of hashtables and alloc_pool's for their items. */
101 typedef struct vn_tables_s
106 struct obstack nary_obstack
;
107 alloc_pool phis_pool
;
108 alloc_pool references_pool
;
111 static htab_t constant_to_value_id
;
112 static bitmap constant_value_ids
;
115 /* Valid hashtables storing information we have proven to be
118 static vn_tables_t valid_info
;
120 /* Optimistic hashtables storing information we are making assumptions about
121 during iterations. */
123 static vn_tables_t optimistic_info
;
125 /* Pointer to the set of hashtables that is currently being used.
126 Should always point to either the optimistic_info, or the
129 static vn_tables_t current_info
;
132 /* Reverse post order index for each basic block. */
134 static int *rpo_numbers
;
136 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
138 /* This represents the top of the VN lattice, which is the universal
143 /* Unique counter for our value ids. */
145 static unsigned int next_value_id
;
147 /* Next DFS number and the stack for strongly connected component
150 static unsigned int next_dfs_num
;
151 static vec
<tree
> sccstack
;
155 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
156 are allocated on an obstack for locality reasons, and to free them
157 without looping over the vec. */
159 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
160 static struct obstack vn_ssa_aux_obstack
;
162 /* Return the value numbering information for a given SSA name. */
167 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
168 gcc_checking_assert (res
);
172 /* Set the value numbering info for a given SSA name to a given
176 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
178 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
181 /* Initialize the value numbering info for a given SSA name.
182 This should be called just once for every SSA name. */
185 VN_INFO_GET (tree name
)
187 vn_ssa_aux_t newinfo
;
189 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
190 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
191 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
192 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
193 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
198 /* Get the representative expression for the SSA_NAME NAME. Returns
199 the representative SSA_NAME if there is no expression associated with it. */
202 vn_get_expr_for (tree name
)
204 vn_ssa_aux_t vn
= VN_INFO (name
);
206 tree expr
= NULL_TREE
;
209 if (vn
->valnum
== VN_TOP
)
212 /* If the value-number is a constant it is the representative
214 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
217 /* Get to the information of the value of this SSA_NAME. */
218 vn
= VN_INFO (vn
->valnum
);
220 /* If the value-number is a constant it is the representative
222 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
225 /* Else if we have an expression, return it. */
226 if (vn
->expr
!= NULL_TREE
)
229 /* Otherwise use the defining statement to build the expression. */
230 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
232 /* If the value number is not an assignment use it directly. */
233 if (!is_gimple_assign (def_stmt
))
236 /* FIXME tuples. This is incomplete and likely will miss some
238 code
= gimple_assign_rhs_code (def_stmt
);
239 switch (TREE_CODE_CLASS (code
))
242 if ((code
== REALPART_EXPR
243 || code
== IMAGPART_EXPR
244 || code
== VIEW_CONVERT_EXPR
)
245 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
247 expr
= fold_build1 (code
,
248 gimple_expr_type (def_stmt
),
249 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
253 expr
= fold_build1 (code
,
254 gimple_expr_type (def_stmt
),
255 gimple_assign_rhs1 (def_stmt
));
259 expr
= fold_build2 (code
,
260 gimple_expr_type (def_stmt
),
261 gimple_assign_rhs1 (def_stmt
),
262 gimple_assign_rhs2 (def_stmt
));
265 case tcc_exceptional
:
266 if (code
== CONSTRUCTOR
268 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
269 expr
= gimple_assign_rhs1 (def_stmt
);
274 if (expr
== NULL_TREE
)
277 /* Cache the expression. */
283 /* Return the vn_kind the expression computed by the stmt should be
287 vn_get_stmt_kind (gimple stmt
)
289 switch (gimple_code (stmt
))
297 enum tree_code code
= gimple_assign_rhs_code (stmt
);
298 tree rhs1
= gimple_assign_rhs1 (stmt
);
299 switch (get_gimple_rhs_class (code
))
301 case GIMPLE_UNARY_RHS
:
302 case GIMPLE_BINARY_RHS
:
303 case GIMPLE_TERNARY_RHS
:
305 case GIMPLE_SINGLE_RHS
:
306 switch (TREE_CODE_CLASS (code
))
309 /* VOP-less references can go through unary case. */
310 if ((code
== REALPART_EXPR
311 || code
== IMAGPART_EXPR
312 || code
== VIEW_CONVERT_EXPR
313 || code
== BIT_FIELD_REF
)
314 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
318 case tcc_declaration
:
325 if (code
== ADDR_EXPR
)
326 return (is_gimple_min_invariant (rhs1
)
327 ? VN_CONSTANT
: VN_REFERENCE
);
328 else if (code
== CONSTRUCTOR
)
341 /* Free a phi operation structure VP. */
346 vn_phi_t phi
= (vn_phi_t
) vp
;
347 phi
->phiargs
.release ();
350 /* Free a reference operation structure VP. */
353 free_reference (void *vp
)
355 vn_reference_t vr
= (vn_reference_t
) vp
;
356 vr
->operands
.release ();
359 /* Hash table equality function for vn_constant_t. */
362 vn_constant_eq (const void *p1
, const void *p2
)
364 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
365 const struct vn_constant_s
*vc2
= (const struct vn_constant_s
*) p2
;
367 if (vc1
->hashcode
!= vc2
->hashcode
)
370 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
373 /* Hash table hash function for vn_constant_t. */
376 vn_constant_hash (const void *p1
)
378 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
379 return vc1
->hashcode
;
382 /* Lookup a value id for CONSTANT and return it. If it does not
386 get_constant_value_id (tree constant
)
389 struct vn_constant_s vc
;
391 vc
.hashcode
= vn_hash_constant_with_type (constant
);
392 vc
.constant
= constant
;
393 slot
= htab_find_slot_with_hash (constant_to_value_id
, &vc
,
394 vc
.hashcode
, NO_INSERT
);
396 return ((vn_constant_t
)*slot
)->value_id
;
400 /* Lookup a value id for CONSTANT, and if it does not exist, create a
401 new one and return it. If it does exist, return it. */
404 get_or_alloc_constant_value_id (tree constant
)
407 struct vn_constant_s vc
;
410 vc
.hashcode
= vn_hash_constant_with_type (constant
);
411 vc
.constant
= constant
;
412 slot
= htab_find_slot_with_hash (constant_to_value_id
, &vc
,
413 vc
.hashcode
, INSERT
);
415 return ((vn_constant_t
)*slot
)->value_id
;
417 vcp
= XNEW (struct vn_constant_s
);
418 vcp
->hashcode
= vc
.hashcode
;
419 vcp
->constant
= constant
;
420 vcp
->value_id
= get_next_value_id ();
421 *slot
= (void *) vcp
;
422 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
423 return vcp
->value_id
;
426 /* Return true if V is a value id for a constant. */
429 value_id_constant_p (unsigned int v
)
431 return bitmap_bit_p (constant_value_ids
, v
);
434 /* Compare two reference operands P1 and P2 for equality. Return true if
435 they are equal, and false otherwise. */
438 vn_reference_op_eq (const void *p1
, const void *p2
)
440 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
441 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
443 return (vro1
->opcode
== vro2
->opcode
444 /* We do not care for differences in type qualification. */
445 && (vro1
->type
== vro2
->type
446 || (vro1
->type
&& vro2
->type
447 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
448 TYPE_MAIN_VARIANT (vro2
->type
))))
449 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
450 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
451 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
454 /* Compute the hash for a reference operand VRO1. */
457 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
459 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
461 result
= iterative_hash_expr (vro1
->op0
, result
);
463 result
= iterative_hash_expr (vro1
->op1
, result
);
465 result
= iterative_hash_expr (vro1
->op2
, result
);
469 /* Return the hashcode for a given reference operation P1. */
472 vn_reference_hash (const void *p1
)
474 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
475 return vr1
->hashcode
;
478 /* Compute a hash for the reference operation VR1 and return it. */
481 vn_reference_compute_hash (const vn_reference_t vr1
)
483 hashval_t result
= 0;
485 vn_reference_op_t vro
;
486 HOST_WIDE_INT off
= -1;
489 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
491 if (vro
->opcode
== MEM_REF
)
493 else if (vro
->opcode
!= ADDR_EXPR
)
505 result
= iterative_hash_hashval_t (off
, result
);
508 && vro
->opcode
== ADDR_EXPR
)
512 tree op
= TREE_OPERAND (vro
->op0
, 0);
513 result
= iterative_hash_hashval_t (TREE_CODE (op
), result
);
514 result
= iterative_hash_expr (op
, result
);
518 result
= vn_reference_op_compute_hash (vro
, result
);
522 result
+= SSA_NAME_VERSION (vr1
->vuse
);
527 /* Return true if reference operations P1 and P2 are equivalent. This
528 means they have the same set of operands and vuses. */
531 vn_reference_eq (const void *p1
, const void *p2
)
535 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
536 const_vn_reference_t
const vr2
= (const_vn_reference_t
) p2
;
537 if (vr1
->hashcode
!= vr2
->hashcode
)
540 /* Early out if this is not a hash collision. */
541 if (vr1
->hashcode
!= vr2
->hashcode
)
544 /* The VOP needs to be the same. */
545 if (vr1
->vuse
!= vr2
->vuse
)
548 /* If the operands are the same we are done. */
549 if (vr1
->operands
== vr2
->operands
)
552 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
555 if (INTEGRAL_TYPE_P (vr1
->type
)
556 && INTEGRAL_TYPE_P (vr2
->type
))
558 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
561 else if (INTEGRAL_TYPE_P (vr1
->type
)
562 && (TYPE_PRECISION (vr1
->type
)
563 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
565 else if (INTEGRAL_TYPE_P (vr2
->type
)
566 && (TYPE_PRECISION (vr2
->type
)
567 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
574 HOST_WIDE_INT off1
= 0, off2
= 0;
575 vn_reference_op_t vro1
, vro2
;
576 vn_reference_op_s tem1
, tem2
;
577 bool deref1
= false, deref2
= false;
578 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
580 if (vro1
->opcode
== MEM_REF
)
586 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
588 if (vro2
->opcode
== MEM_REF
)
596 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
598 memset (&tem1
, 0, sizeof (tem1
));
599 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
600 tem1
.type
= TREE_TYPE (tem1
.op0
);
601 tem1
.opcode
= TREE_CODE (tem1
.op0
);
605 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
607 memset (&tem2
, 0, sizeof (tem2
));
608 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
609 tem2
.type
= TREE_TYPE (tem2
.op0
);
610 tem2
.opcode
= TREE_CODE (tem2
.op0
);
614 if (deref1
!= deref2
)
616 if (!vn_reference_op_eq (vro1
, vro2
))
621 while (vr1
->operands
.length () != i
622 || vr2
->operands
.length () != j
);
627 /* Copy the operations present in load/store REF into RESULT, a vector of
628 vn_reference_op_s's. */
631 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
633 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
635 vn_reference_op_s temp
;
637 memset (&temp
, 0, sizeof (temp
));
638 temp
.type
= TREE_TYPE (ref
);
639 temp
.opcode
= TREE_CODE (ref
);
640 temp
.op0
= TMR_INDEX (ref
);
641 temp
.op1
= TMR_STEP (ref
);
642 temp
.op2
= TMR_OFFSET (ref
);
644 result
->safe_push (temp
);
646 memset (&temp
, 0, sizeof (temp
));
647 temp
.type
= NULL_TREE
;
648 temp
.opcode
= ERROR_MARK
;
649 temp
.op0
= TMR_INDEX2 (ref
);
651 result
->safe_push (temp
);
653 memset (&temp
, 0, sizeof (temp
));
654 temp
.type
= NULL_TREE
;
655 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
656 temp
.op0
= TMR_BASE (ref
);
658 result
->safe_push (temp
);
662 /* For non-calls, store the information that makes up the address. */
666 vn_reference_op_s temp
;
668 memset (&temp
, 0, sizeof (temp
));
669 temp
.type
= TREE_TYPE (ref
);
670 temp
.opcode
= TREE_CODE (ref
);
676 temp
.op0
= TREE_OPERAND (ref
, 1);
679 temp
.op0
= TREE_OPERAND (ref
, 1);
683 /* The base address gets its own vn_reference_op_s structure. */
684 temp
.op0
= TREE_OPERAND (ref
, 1);
685 if (host_integerp (TREE_OPERAND (ref
, 1), 0))
686 temp
.off
= TREE_INT_CST_LOW (TREE_OPERAND (ref
, 1));
689 /* Record bits and position. */
690 temp
.op0
= TREE_OPERAND (ref
, 1);
691 temp
.op1
= TREE_OPERAND (ref
, 2);
694 /* The field decl is enough to unambiguously specify the field,
695 a matching type is not necessary and a mismatching type
696 is always a spurious difference. */
697 temp
.type
= NULL_TREE
;
698 temp
.op0
= TREE_OPERAND (ref
, 1);
699 temp
.op1
= TREE_OPERAND (ref
, 2);
701 tree this_offset
= component_ref_field_offset (ref
);
703 && TREE_CODE (this_offset
) == INTEGER_CST
)
705 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
706 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
709 = tree_to_double_int (this_offset
)
710 + tree_to_double_int (bit_offset
)
711 .arshift (BITS_PER_UNIT
== 8
712 ? 3 : exact_log2 (BITS_PER_UNIT
),
713 HOST_BITS_PER_DOUBLE_INT
);
714 if (off
.fits_shwi ())
720 case ARRAY_RANGE_REF
:
722 /* Record index as operand. */
723 temp
.op0
= TREE_OPERAND (ref
, 1);
724 /* Always record lower bounds and element size. */
725 temp
.op1
= array_ref_low_bound (ref
);
726 temp
.op2
= array_ref_element_size (ref
);
727 if (TREE_CODE (temp
.op0
) == INTEGER_CST
728 && TREE_CODE (temp
.op1
) == INTEGER_CST
729 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
731 double_int off
= tree_to_double_int (temp
.op0
);
732 off
+= -tree_to_double_int (temp
.op1
);
733 off
*= tree_to_double_int (temp
.op2
);
734 if (off
.fits_shwi ())
739 if (DECL_HARD_REGISTER (ref
))
748 /* Canonicalize decls to MEM[&decl] which is what we end up with
749 when valueizing MEM[ptr] with ptr = &decl. */
750 temp
.opcode
= MEM_REF
;
751 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
753 result
->safe_push (temp
);
754 temp
.opcode
= ADDR_EXPR
;
755 temp
.op0
= build_fold_addr_expr (ref
);
756 temp
.type
= TREE_TYPE (temp
.op0
);
770 if (is_gimple_min_invariant (ref
))
776 /* These are only interesting for their operands, their
777 existence, and their type. They will never be the last
778 ref in the chain of references (IE they require an
779 operand), so we don't have to put anything
780 for op* as it will be handled by the iteration */
782 case VIEW_CONVERT_EXPR
:
786 /* This is only interesting for its constant offset. */
787 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
792 result
->safe_push (temp
);
794 if (REFERENCE_CLASS_P (ref
)
795 || TREE_CODE (ref
) == MODIFY_EXPR
796 || TREE_CODE (ref
) == WITH_SIZE_EXPR
797 || (TREE_CODE (ref
) == ADDR_EXPR
798 && !is_gimple_min_invariant (ref
)))
799 ref
= TREE_OPERAND (ref
, 0);
805 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
806 operands in *OPS, the reference alias set SET and the reference type TYPE.
807 Return true if something useful was produced. */
810 ao_ref_init_from_vn_reference (ao_ref
*ref
,
811 alias_set_type set
, tree type
,
812 vec
<vn_reference_op_s
> ops
)
814 vn_reference_op_t op
;
816 tree base
= NULL_TREE
;
818 HOST_WIDE_INT offset
= 0;
819 HOST_WIDE_INT max_size
;
820 HOST_WIDE_INT size
= -1;
821 tree size_tree
= NULL_TREE
;
822 alias_set_type base_alias_set
= -1;
824 /* First get the final access size from just the outermost expression. */
826 if (op
->opcode
== COMPONENT_REF
)
827 size_tree
= DECL_SIZE (op
->op0
);
828 else if (op
->opcode
== BIT_FIELD_REF
)
832 enum machine_mode mode
= TYPE_MODE (type
);
834 size_tree
= TYPE_SIZE (type
);
836 size
= GET_MODE_BITSIZE (mode
);
838 if (size_tree
!= NULL_TREE
)
840 if (!host_integerp (size_tree
, 1))
843 size
= TREE_INT_CST_LOW (size_tree
);
846 /* Initially, maxsize is the same as the accessed element size.
847 In the following it will only grow (or become -1). */
850 /* Compute cumulative bit-offset for nested component-refs and array-refs,
851 and find the ultimate containing object. */
852 FOR_EACH_VEC_ELT (ops
, i
, op
)
856 /* These may be in the reference ops, but we cannot do anything
857 sensible with them here. */
859 /* Apart from ADDR_EXPR arguments to MEM_REF. */
860 if (base
!= NULL_TREE
861 && TREE_CODE (base
) == MEM_REF
863 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
865 vn_reference_op_t pop
= &ops
[i
-1];
866 base
= TREE_OPERAND (op
->op0
, 0);
873 offset
+= pop
->off
* BITS_PER_UNIT
;
881 /* Record the base objects. */
883 base_alias_set
= get_deref_alias_set (op
->op0
);
884 *op0_p
= build2 (MEM_REF
, op
->type
,
886 op0_p
= &TREE_OPERAND (*op0_p
, 0);
897 /* And now the usual component-reference style ops. */
899 offset
+= tree_low_cst (op
->op1
, 0);
904 tree field
= op
->op0
;
905 /* We do not have a complete COMPONENT_REF tree here so we
906 cannot use component_ref_field_offset. Do the interesting
910 || !host_integerp (DECL_FIELD_OFFSET (field
), 1))
914 offset
+= (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field
))
916 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
921 case ARRAY_RANGE_REF
:
923 /* We recorded the lower bound and the element size. */
924 if (!host_integerp (op
->op0
, 0)
925 || !host_integerp (op
->op1
, 0)
926 || !host_integerp (op
->op2
, 0))
930 HOST_WIDE_INT hindex
= TREE_INT_CST_LOW (op
->op0
);
931 hindex
-= TREE_INT_CST_LOW (op
->op1
);
932 hindex
*= TREE_INT_CST_LOW (op
->op2
);
933 hindex
*= BITS_PER_UNIT
;
945 case VIEW_CONVERT_EXPR
:
962 if (base
== NULL_TREE
)
965 ref
->ref
= NULL_TREE
;
967 ref
->offset
= offset
;
969 ref
->max_size
= max_size
;
970 ref
->ref_alias_set
= set
;
971 if (base_alias_set
!= -1)
972 ref
->base_alias_set
= base_alias_set
;
974 ref
->base_alias_set
= get_alias_set (base
);
975 /* We discount volatiles from value-numbering elsewhere. */
976 ref
->volatile_p
= false;
981 /* Copy the operations present in load/store/call REF into RESULT, a vector of
982 vn_reference_op_s's. */
985 copy_reference_ops_from_call (gimple call
,
986 vec
<vn_reference_op_s
> *result
)
988 vn_reference_op_s temp
;
990 tree lhs
= gimple_call_lhs (call
);
992 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
993 different. By adding the lhs here in the vector, we ensure that the
994 hashcode is different, guaranteeing a different value number. */
995 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
997 memset (&temp
, 0, sizeof (temp
));
998 temp
.opcode
= MODIFY_EXPR
;
999 temp
.type
= TREE_TYPE (lhs
);
1002 result
->safe_push (temp
);
1005 /* Copy the type, opcode, function being called and static chain. */
1006 memset (&temp
, 0, sizeof (temp
));
1007 temp
.type
= gimple_call_return_type (call
);
1008 temp
.opcode
= CALL_EXPR
;
1009 temp
.op0
= gimple_call_fn (call
);
1010 temp
.op1
= gimple_call_chain (call
);
1012 result
->safe_push (temp
);
1014 /* Copy the call arguments. As they can be references as well,
1015 just chain them together. */
1016 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1018 tree callarg
= gimple_call_arg (call
, i
);
1019 copy_reference_ops_from_ref (callarg
, result
);
1023 /* Create a vector of vn_reference_op_s structures from REF, a
1024 REFERENCE_CLASS_P tree. The vector is not shared. */
1026 static vec
<vn_reference_op_s
>
1027 create_reference_ops_from_ref (tree ref
)
1029 vec
<vn_reference_op_s
> result
= vNULL
;
1031 copy_reference_ops_from_ref (ref
, &result
);
1035 /* Create a vector of vn_reference_op_s structures from CALL, a
1036 call statement. The vector is not shared. */
1038 static vec
<vn_reference_op_s
>
1039 create_reference_ops_from_call (gimple call
)
1041 vec
<vn_reference_op_s
> result
= vNULL
;
1043 copy_reference_ops_from_call (call
, &result
);
1047 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1048 *I_P to point to the last element of the replacement. */
1050 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1053 unsigned int i
= *i_p
;
1054 vn_reference_op_t op
= &(*ops
)[i
];
1055 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1057 HOST_WIDE_INT addr_offset
= 0;
1059 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1060 from .foo.bar to the preceding MEM_REF offset and replace the
1061 address with &OBJ. */
1062 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1064 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1065 if (addr_base
!= op
->op0
)
1067 double_int off
= tree_to_double_int (mem_op
->op0
);
1068 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1069 off
+= double_int::from_shwi (addr_offset
);
1070 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1071 op
->op0
= build_fold_addr_expr (addr_base
);
1072 if (host_integerp (mem_op
->op0
, 0))
1073 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1079 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1080 *I_P to point to the last element of the replacement. */
1082 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1085 unsigned int i
= *i_p
;
1086 vn_reference_op_t op
= &(*ops
)[i
];
1087 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1089 enum tree_code code
;
1092 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1093 if (!is_gimple_assign (def_stmt
))
1096 code
= gimple_assign_rhs_code (def_stmt
);
1097 if (code
!= ADDR_EXPR
1098 && code
!= POINTER_PLUS_EXPR
)
1101 off
= tree_to_double_int (mem_op
->op0
);
1102 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1104 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1105 from .foo.bar to the preceding MEM_REF offset and replace the
1106 address with &OBJ. */
1107 if (code
== ADDR_EXPR
)
1109 tree addr
, addr_base
;
1110 HOST_WIDE_INT addr_offset
;
1112 addr
= gimple_assign_rhs1 (def_stmt
);
1113 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1116 || TREE_CODE (addr_base
) != MEM_REF
)
1119 off
+= double_int::from_shwi (addr_offset
);
1120 off
+= mem_ref_offset (addr_base
);
1121 op
->op0
= TREE_OPERAND (addr_base
, 0);
1126 ptr
= gimple_assign_rhs1 (def_stmt
);
1127 ptroff
= gimple_assign_rhs2 (def_stmt
);
1128 if (TREE_CODE (ptr
) != SSA_NAME
1129 || TREE_CODE (ptroff
) != INTEGER_CST
)
1132 off
+= tree_to_double_int (ptroff
);
1136 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1137 if (host_integerp (mem_op
->op0
, 0))
1138 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1141 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1142 op
->op0
= SSA_VAL (op
->op0
);
1143 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1144 op
->opcode
= TREE_CODE (op
->op0
);
1147 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1148 vn_reference_maybe_forwprop_address (ops
, i_p
);
1149 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1150 vn_reference_fold_indirect (ops
, i_p
);
1153 /* Optimize the reference REF to a constant if possible or return
1154 NULL_TREE if not. */
1157 fully_constant_vn_reference_p (vn_reference_t ref
)
1159 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1160 vn_reference_op_t op
;
1162 /* Try to simplify the translated expression if it is
1163 a call to a builtin function with at most two arguments. */
1165 if (op
->opcode
== CALL_EXPR
1166 && TREE_CODE (op
->op0
) == ADDR_EXPR
1167 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1168 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1169 && operands
.length () >= 2
1170 && operands
.length () <= 3)
1172 vn_reference_op_t arg0
, arg1
= NULL
;
1173 bool anyconst
= false;
1174 arg0
= &operands
[1];
1175 if (operands
.length () > 2)
1176 arg1
= &operands
[2];
1177 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1178 || (arg0
->opcode
== ADDR_EXPR
1179 && is_gimple_min_invariant (arg0
->op0
)))
1182 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1183 || (arg1
->opcode
== ADDR_EXPR
1184 && is_gimple_min_invariant (arg1
->op0
))))
1188 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1191 arg1
? arg1
->op0
: NULL
);
1193 && TREE_CODE (folded
) == NOP_EXPR
)
1194 folded
= TREE_OPERAND (folded
, 0);
1196 && is_gimple_min_invariant (folded
))
1201 /* Simplify reads from constant strings. */
1202 else if (op
->opcode
== ARRAY_REF
1203 && TREE_CODE (op
->op0
) == INTEGER_CST
1204 && integer_zerop (op
->op1
)
1205 && operands
.length () == 2)
1207 vn_reference_op_t arg0
;
1208 arg0
= &operands
[1];
1209 if (arg0
->opcode
== STRING_CST
1210 && (TYPE_MODE (op
->type
)
1211 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1212 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1213 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1214 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1215 return build_int_cst_type (op
->type
,
1216 (TREE_STRING_POINTER (arg0
->op0
)
1217 [TREE_INT_CST_LOW (op
->op0
)]));
1223 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1224 structures into their value numbers. This is done in-place, and
1225 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1226 whether any operands were valueized. */
1228 static vec
<vn_reference_op_s
>
1229 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1231 vn_reference_op_t vro
;
1234 *valueized_anything
= false;
1236 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1238 if (vro
->opcode
== SSA_NAME
1239 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1241 tree tem
= SSA_VAL (vro
->op0
);
1242 if (tem
!= vro
->op0
)
1244 *valueized_anything
= true;
1247 /* If it transforms from an SSA_NAME to a constant, update
1249 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1250 vro
->opcode
= TREE_CODE (vro
->op0
);
1252 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1254 tree tem
= SSA_VAL (vro
->op1
);
1255 if (tem
!= vro
->op1
)
1257 *valueized_anything
= true;
1261 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1263 tree tem
= SSA_VAL (vro
->op2
);
1264 if (tem
!= vro
->op2
)
1266 *valueized_anything
= true;
1270 /* If it transforms from an SSA_NAME to an address, fold with
1271 a preceding indirect reference. */
1274 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1275 && orig
[i
- 1].opcode
== MEM_REF
)
1276 vn_reference_fold_indirect (&orig
, &i
);
1278 && vro
->opcode
== SSA_NAME
1279 && orig
[i
- 1].opcode
== MEM_REF
)
1280 vn_reference_maybe_forwprop_address (&orig
, &i
);
1281 /* If it transforms a non-constant ARRAY_REF into a constant
1282 one, adjust the constant offset. */
1283 else if (vro
->opcode
== ARRAY_REF
1285 && TREE_CODE (vro
->op0
) == INTEGER_CST
1286 && TREE_CODE (vro
->op1
) == INTEGER_CST
1287 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1289 double_int off
= tree_to_double_int (vro
->op0
);
1290 off
+= -tree_to_double_int (vro
->op1
);
1291 off
*= tree_to_double_int (vro
->op2
);
1292 if (off
.fits_shwi ())
1300 static vec
<vn_reference_op_s
>
1301 valueize_refs (vec
<vn_reference_op_s
> orig
)
1304 return valueize_refs_1 (orig
, &tem
);
1307 static vec
<vn_reference_op_s
> shared_lookup_references
;
1309 /* Create a vector of vn_reference_op_s structures from REF, a
1310 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1311 this function. *VALUEIZED_ANYTHING will specify whether any
1312 operands were valueized. */
1314 static vec
<vn_reference_op_s
>
1315 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1319 shared_lookup_references
.truncate (0);
1320 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1321 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1322 valueized_anything
);
1323 return shared_lookup_references
;
1326 /* Create a vector of vn_reference_op_s structures from CALL, a
1327 call statement. The vector is shared among all callers of
1330 static vec
<vn_reference_op_s
>
1331 valueize_shared_reference_ops_from_call (gimple call
)
1335 shared_lookup_references
.truncate (0);
1336 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1337 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1338 return shared_lookup_references
;
1341 /* Lookup a SCCVN reference operation VR in the current hash table.
1342 Returns the resulting value number if it exists in the hash table,
1343 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1344 vn_reference_t stored in the hashtable if something is found. */
1347 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1352 hash
= vr
->hashcode
;
1353 slot
= htab_find_slot_with_hash (current_info
->references
, vr
,
1355 if (!slot
&& current_info
== optimistic_info
)
1356 slot
= htab_find_slot_with_hash (valid_info
->references
, vr
,
1361 *vnresult
= (vn_reference_t
)*slot
;
1362 return ((vn_reference_t
)*slot
)->result
;
1368 static tree
*last_vuse_ptr
;
1369 static vn_lookup_kind vn_walk_kind
;
1370 static vn_lookup_kind default_vn_walk_kind
;
1372 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1373 with the current VUSE and performs the expression lookup. */
1376 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1377 unsigned int cnt
, void *vr_
)
1379 vn_reference_t vr
= (vn_reference_t
)vr_
;
1383 /* This bounds the stmt walks we perform on reference lookups
1384 to O(1) instead of O(N) where N is the number of dominating
1386 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1390 *last_vuse_ptr
= vuse
;
1392 /* Fixup vuse and hash. */
1394 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1395 vr
->vuse
= SSA_VAL (vuse
);
1397 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1399 hash
= vr
->hashcode
;
1400 slot
= htab_find_slot_with_hash (current_info
->references
, vr
,
1402 if (!slot
&& current_info
== optimistic_info
)
1403 slot
= htab_find_slot_with_hash (valid_info
->references
, vr
,
1411 /* Lookup an existing or insert a new vn_reference entry into the
1412 value table for the VUSE, SET, TYPE, OPERANDS reference which
1413 has the value VALUE which is either a constant or an SSA name. */
1415 static vn_reference_t
1416 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1419 vec
<vn_reference_op_s
,
1423 struct vn_reference_s vr1
;
1424 vn_reference_t result
;
1427 vr1
.operands
= operands
;
1430 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1431 if (vn_reference_lookup_1 (&vr1
, &result
))
1433 if (TREE_CODE (value
) == SSA_NAME
)
1434 value_id
= VN_INFO (value
)->value_id
;
1436 value_id
= get_or_alloc_constant_value_id (value
);
1437 return vn_reference_insert_pieces (vuse
, set
, type
,
1438 operands
.copy (), value
, value_id
);
1441 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1442 from the statement defining VUSE and if not successful tries to
1443 translate *REFP and VR_ through an aggregate copy at the definition
1447 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
)
1449 vn_reference_t vr
= (vn_reference_t
)vr_
;
1450 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1452 HOST_WIDE_INT offset
, maxsize
;
1453 static vec
<vn_reference_op_s
>
1456 bool lhs_ref_ok
= false;
1458 /* First try to disambiguate after value-replacing in the definitions LHS. */
1459 if (is_gimple_assign (def_stmt
))
1461 vec
<vn_reference_op_s
> tem
;
1462 tree lhs
= gimple_assign_lhs (def_stmt
);
1463 bool valueized_anything
= false;
1464 /* Avoid re-allocation overhead. */
1465 lhs_ops
.truncate (0);
1466 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1468 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1469 gcc_assert (lhs_ops
== tem
);
1470 if (valueized_anything
)
1472 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1473 get_alias_set (lhs
),
1474 TREE_TYPE (lhs
), lhs_ops
);
1476 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1481 ao_ref_init (&lhs_ref
, lhs
);
1486 base
= ao_ref_base (ref
);
1487 offset
= ref
->offset
;
1488 maxsize
= ref
->max_size
;
1490 /* If we cannot constrain the size of the reference we cannot
1491 test if anything kills it. */
1495 /* We can't deduce anything useful from clobbers. */
1496 if (gimple_clobber_p (def_stmt
))
1499 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1500 from that definition.
1502 if (is_gimple_reg_type (vr
->type
)
1503 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1504 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1505 && host_integerp (gimple_call_arg (def_stmt
, 2), 1)
1506 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1508 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1510 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1511 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1512 size2
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2)) * 8;
1513 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1514 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2))
1516 && operand_equal_p (base
, base2
, 0)
1517 && offset2
<= offset
1518 && offset2
+ size2
>= offset
+ maxsize
)
1520 tree val
= build_zero_cst (vr
->type
);
1521 return vn_reference_lookup_or_insert_for_pieces
1522 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1526 /* 2) Assignment from an empty CONSTRUCTOR. */
1527 else if (is_gimple_reg_type (vr
->type
)
1528 && gimple_assign_single_p (def_stmt
)
1529 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1530 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1533 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1534 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1535 &offset2
, &size2
, &maxsize2
);
1537 && operand_equal_p (base
, base2
, 0)
1538 && offset2
<= offset
1539 && offset2
+ size2
>= offset
+ maxsize
)
1541 tree val
= build_zero_cst (vr
->type
);
1542 return vn_reference_lookup_or_insert_for_pieces
1543 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1547 /* 3) Assignment from a constant. We can use folds native encode/interpret
1548 routines to extract the assigned bits. */
1549 else if (vn_walk_kind
== VN_WALKREWRITE
1550 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1551 && ref
->size
== maxsize
1552 && maxsize
% BITS_PER_UNIT
== 0
1553 && offset
% BITS_PER_UNIT
== 0
1554 && is_gimple_reg_type (vr
->type
)
1555 && gimple_assign_single_p (def_stmt
)
1556 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1559 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1560 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1561 &offset2
, &size2
, &maxsize2
);
1563 && maxsize2
== size2
1564 && size2
% BITS_PER_UNIT
== 0
1565 && offset2
% BITS_PER_UNIT
== 0
1566 && operand_equal_p (base
, base2
, 0)
1567 && offset2
<= offset
1568 && offset2
+ size2
>= offset
+ maxsize
)
1570 /* We support up to 512-bit values (for V8DFmode). */
1571 unsigned char buffer
[64];
1574 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1575 buffer
, sizeof (buffer
));
1578 tree val
= native_interpret_expr (vr
->type
,
1580 + ((offset
- offset2
)
1582 ref
->size
/ BITS_PER_UNIT
);
1584 return vn_reference_lookup_or_insert_for_pieces
1585 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1590 /* 4) Assignment from an SSA name which definition we may be able
1591 to access pieces from. */
1592 else if (ref
->size
== maxsize
1593 && is_gimple_reg_type (vr
->type
)
1594 && gimple_assign_single_p (def_stmt
)
1595 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1597 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1598 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1599 if (is_gimple_assign (def_stmt2
)
1600 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1601 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1602 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1605 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1606 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1607 &offset2
, &size2
, &maxsize2
);
1608 off
= offset
- offset2
;
1610 && maxsize2
== size2
1611 && operand_equal_p (base
, base2
, 0)
1612 && offset2
<= offset
1613 && offset2
+ size2
>= offset
+ maxsize
)
1615 tree val
= NULL_TREE
;
1617 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1618 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1621 val
= gimple_assign_rhs1 (def_stmt2
);
1622 else if (off
== elsz
)
1623 val
= gimple_assign_rhs2 (def_stmt2
);
1625 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1628 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1629 unsigned i
= off
/ elsz
;
1630 if (i
< CONSTRUCTOR_NELTS (ctor
))
1632 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1633 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1635 if (TREE_CODE (TREE_TYPE (elt
->value
))
1642 return vn_reference_lookup_or_insert_for_pieces
1643 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1648 /* 5) For aggregate copies translate the reference through them if
1649 the copy kills ref. */
1650 else if (vn_walk_kind
== VN_WALKREWRITE
1651 && gimple_assign_single_p (def_stmt
)
1652 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1653 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1654 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1657 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1659 vec
<vn_reference_op_s
>
1661 vn_reference_op_t vro
;
1667 /* See if the assignment kills REF. */
1668 base2
= ao_ref_base (&lhs_ref
);
1669 offset2
= lhs_ref
.offset
;
1670 size2
= lhs_ref
.size
;
1671 maxsize2
= lhs_ref
.max_size
;
1673 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1675 || offset2
+ size2
< offset
+ maxsize
)
1678 /* Find the common base of ref and the lhs. lhs_ops already
1679 contains valueized operands for the lhs. */
1680 i
= vr
->operands
.length () - 1;
1681 j
= lhs_ops
.length () - 1;
1682 while (j
>= 0 && i
>= 0
1683 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1689 /* ??? The innermost op should always be a MEM_REF and we already
1690 checked that the assignment to the lhs kills vr. Thus for
1691 aggregate copies using char[] types the vn_reference_op_eq
1692 may fail when comparing types for compatibility. But we really
1693 don't care here - further lookups with the rewritten operands
1694 will simply fail if we messed up types too badly. */
1695 if (j
== 0 && i
>= 0
1696 && lhs_ops
[0].opcode
== MEM_REF
1697 && lhs_ops
[0].off
!= -1
1698 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1701 /* i now points to the first additional op.
1702 ??? LHS may not be completely contained in VR, one or more
1703 VIEW_CONVERT_EXPRs could be in its way. We could at least
1704 try handling outermost VIEW_CONVERT_EXPRs. */
1708 /* Now re-write REF to be based on the rhs of the assignment. */
1709 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1710 /* We need to pre-pend vr->operands[0..i] to rhs. */
1711 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1713 vec
<vn_reference_op_s
> old
= vr
->operands
;
1714 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1715 if (old
== shared_lookup_references
1716 && vr
->operands
!= old
)
1717 shared_lookup_references
= vNULL
;
1720 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1721 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1722 vr
->operands
[i
+ 1 + j
] = *vro
;
1724 vr
->operands
= valueize_refs (vr
->operands
);
1725 vr
->hashcode
= vn_reference_compute_hash (vr
);
1727 /* Adjust *ref from the new operands. */
1728 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1730 /* This can happen with bitfields. */
1731 if (ref
->size
!= r
.size
)
1735 /* Do not update last seen VUSE after translating. */
1736 last_vuse_ptr
= NULL
;
1738 /* Keep looking for the adjusted *REF / VR pair. */
1742 /* 6) For memcpy copies translate the reference through them if
1743 the copy kills ref. */
1744 else if (vn_walk_kind
== VN_WALKREWRITE
1745 && is_gimple_reg_type (vr
->type
)
1746 /* ??? Handle BCOPY as well. */
1747 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1748 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1749 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1750 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1751 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1752 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1753 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1754 && host_integerp (gimple_call_arg (def_stmt
, 2), 1))
1758 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1759 vn_reference_op_s op
;
1763 /* Only handle non-variable, addressable refs. */
1764 if (ref
->size
!= maxsize
1765 || offset
% BITS_PER_UNIT
!= 0
1766 || ref
->size
% BITS_PER_UNIT
!= 0)
1769 /* Extract a pointer base and an offset for the destination. */
1770 lhs
= gimple_call_arg (def_stmt
, 0);
1772 if (TREE_CODE (lhs
) == SSA_NAME
)
1773 lhs
= SSA_VAL (lhs
);
1774 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1776 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1780 if (TREE_CODE (tem
) == MEM_REF
1781 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1783 lhs
= TREE_OPERAND (tem
, 0);
1784 lhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1786 else if (DECL_P (tem
))
1787 lhs
= build_fold_addr_expr (tem
);
1791 if (TREE_CODE (lhs
) != SSA_NAME
1792 && TREE_CODE (lhs
) != ADDR_EXPR
)
1795 /* Extract a pointer base and an offset for the source. */
1796 rhs
= gimple_call_arg (def_stmt
, 1);
1798 if (TREE_CODE (rhs
) == SSA_NAME
)
1799 rhs
= SSA_VAL (rhs
);
1800 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1802 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1806 if (TREE_CODE (tem
) == MEM_REF
1807 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1809 rhs
= TREE_OPERAND (tem
, 0);
1810 rhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1812 else if (DECL_P (tem
))
1813 rhs
= build_fold_addr_expr (tem
);
1817 if (TREE_CODE (rhs
) != SSA_NAME
1818 && TREE_CODE (rhs
) != ADDR_EXPR
)
1821 copy_size
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2));
1823 /* The bases of the destination and the references have to agree. */
1824 if ((TREE_CODE (base
) != MEM_REF
1826 || (TREE_CODE (base
) == MEM_REF
1827 && (TREE_OPERAND (base
, 0) != lhs
1828 || !host_integerp (TREE_OPERAND (base
, 1), 1)))
1830 && (TREE_CODE (lhs
) != ADDR_EXPR
1831 || TREE_OPERAND (lhs
, 0) != base
)))
1834 /* And the access has to be contained within the memcpy destination. */
1835 at
= offset
/ BITS_PER_UNIT
;
1836 if (TREE_CODE (base
) == MEM_REF
)
1837 at
+= TREE_INT_CST_LOW (TREE_OPERAND (base
, 1));
1839 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1842 /* Make room for 2 operands in the new reference. */
1843 if (vr
->operands
.length () < 2)
1845 vec
<vn_reference_op_s
> old
= vr
->operands
;
1846 vr
->operands
.safe_grow_cleared (2);
1847 if (old
== shared_lookup_references
1848 && vr
->operands
!= old
)
1849 shared_lookup_references
.create (0);
1852 vr
->operands
.truncate (2);
1854 /* The looked-through reference is a simple MEM_REF. */
1855 memset (&op
, 0, sizeof (op
));
1857 op
.opcode
= MEM_REF
;
1858 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
1859 op
.off
= at
- lhs_offset
+ rhs_offset
;
1860 vr
->operands
[0] = op
;
1861 op
.type
= TREE_TYPE (rhs
);
1862 op
.opcode
= TREE_CODE (rhs
);
1865 vr
->operands
[1] = op
;
1866 vr
->hashcode
= vn_reference_compute_hash (vr
);
1868 /* Adjust *ref from the new operands. */
1869 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1871 /* This can happen with bitfields. */
1872 if (ref
->size
!= r
.size
)
1876 /* Do not update last seen VUSE after translating. */
1877 last_vuse_ptr
= NULL
;
1879 /* Keep looking for the adjusted *REF / VR pair. */
1883 /* Bail out and stop walking. */
1887 /* Lookup a reference operation by it's parts, in the current hash table.
1888 Returns the resulting value number if it exists in the hash table,
1889 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1890 vn_reference_t stored in the hashtable if something is found. */
1893 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
1894 vec
<vn_reference_op_s
> operands
,
1895 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
1897 struct vn_reference_s vr1
;
1905 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1906 shared_lookup_references
.truncate (0);
1907 shared_lookup_references
.safe_grow (operands
.length ());
1908 memcpy (shared_lookup_references
.address (),
1909 operands
.address (),
1910 sizeof (vn_reference_op_s
)
1911 * operands
.length ());
1912 vr1
.operands
= operands
= shared_lookup_references
1913 = valueize_refs (shared_lookup_references
);
1916 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1917 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
1920 vn_reference_lookup_1 (&vr1
, vnresult
);
1922 && kind
!= VN_NOWALK
1926 vn_walk_kind
= kind
;
1927 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
1929 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1930 vn_reference_lookup_2
,
1931 vn_reference_lookup_3
, &vr1
);
1932 if (vr1
.operands
!= operands
)
1933 vr1
.operands
.release ();
1937 return (*vnresult
)->result
;
1942 /* Lookup OP in the current hash table, and return the resulting value
1943 number if it exists in the hash table. Return NULL_TREE if it does
1944 not exist in the hash table or if the result field of the structure
1945 was NULL.. VNRESULT will be filled in with the vn_reference_t
1946 stored in the hashtable if one exists. */
1949 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
1950 vn_reference_t
*vnresult
)
1952 vec
<vn_reference_op_s
> operands
;
1953 struct vn_reference_s vr1
;
1955 bool valuezied_anything
;
1960 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1961 vr1
.operands
= operands
1962 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
1963 vr1
.type
= TREE_TYPE (op
);
1964 vr1
.set
= get_alias_set (op
);
1965 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1966 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
1969 if (kind
!= VN_NOWALK
1972 vn_reference_t wvnresult
;
1974 /* Make sure to use a valueized reference if we valueized anything.
1975 Otherwise preserve the full reference for advanced TBAA. */
1976 if (!valuezied_anything
1977 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
1979 ao_ref_init (&r
, op
);
1980 vn_walk_kind
= kind
;
1982 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1983 vn_reference_lookup_2
,
1984 vn_reference_lookup_3
, &vr1
);
1985 if (vr1
.operands
!= operands
)
1986 vr1
.operands
.release ();
1990 *vnresult
= wvnresult
;
1991 return wvnresult
->result
;
1997 return vn_reference_lookup_1 (&vr1
, vnresult
);
2001 /* Insert OP into the current hash table with a value number of
2002 RESULT, and return the resulting reference structure we created. */
2005 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2010 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2011 if (TREE_CODE (result
) == SSA_NAME
)
2012 vr1
->value_id
= VN_INFO (result
)->value_id
;
2014 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2015 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2016 vr1
->operands
= valueize_refs (create_reference_ops_from_ref (op
));
2017 vr1
->type
= TREE_TYPE (op
);
2018 vr1
->set
= get_alias_set (op
);
2019 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2020 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2021 vr1
->result_vdef
= vdef
;
2023 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
2026 /* Because we lookup stores using vuses, and value number failures
2027 using the vdefs (see visit_reference_op_store for how and why),
2028 it's possible that on failure we may try to insert an already
2029 inserted store. This is not wrong, there is no ssa name for a
2030 store that we could use as a differentiator anyway. Thus, unlike
2031 the other lookup functions, you cannot gcc_assert (!*slot)
2034 /* But free the old slot in case of a collision. */
2036 free_reference (*slot
);
2042 /* Insert a reference by it's pieces into the current hash table with
2043 a value number of RESULT. Return the resulting reference
2044 structure we created. */
2047 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2048 vec
<vn_reference_op_s
> operands
,
2049 tree result
, unsigned int value_id
)
2055 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2056 vr1
->value_id
= value_id
;
2057 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2058 vr1
->operands
= valueize_refs (operands
);
2061 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2062 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2063 result
= SSA_VAL (result
);
2064 vr1
->result
= result
;
2066 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
2069 /* At this point we should have all the things inserted that we have
2070 seen before, and we should never try inserting something that
2072 gcc_assert (!*slot
);
2074 free_reference (*slot
);
2080 /* Compute and return the hash value for nary operation VBO1. */
2083 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2088 for (i
= 0; i
< vno1
->length
; ++i
)
2089 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2090 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2092 if (vno1
->length
== 2
2093 && commutative_tree_code (vno1
->opcode
)
2094 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2096 tree temp
= vno1
->op
[0];
2097 vno1
->op
[0] = vno1
->op
[1];
2101 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2102 for (i
= 0; i
< vno1
->length
; ++i
)
2103 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2108 /* Return the computed hashcode for nary operation P1. */
2111 vn_nary_op_hash (const void *p1
)
2113 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
2114 return vno1
->hashcode
;
2117 /* Compare nary operations P1 and P2 and return true if they are
2121 vn_nary_op_eq (const void *p1
, const void *p2
)
2123 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
2124 const_vn_nary_op_t
const vno2
= (const_vn_nary_op_t
) p2
;
2127 if (vno1
->hashcode
!= vno2
->hashcode
)
2130 if (vno1
->length
!= vno2
->length
)
2133 if (vno1
->opcode
!= vno2
->opcode
2134 || !types_compatible_p (vno1
->type
, vno2
->type
))
2137 for (i
= 0; i
< vno1
->length
; ++i
)
2138 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2144 /* Initialize VNO from the pieces provided. */
2147 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2148 enum tree_code code
, tree type
, tree
*ops
)
2151 vno
->length
= length
;
2153 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2156 /* Initialize VNO from OP. */
2159 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2163 vno
->opcode
= TREE_CODE (op
);
2164 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2165 vno
->type
= TREE_TYPE (op
);
2166 for (i
= 0; i
< vno
->length
; ++i
)
2167 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2170 /* Return the number of operands for a vn_nary ops structure from STMT. */
2173 vn_nary_length_from_stmt (gimple stmt
)
2175 switch (gimple_assign_rhs_code (stmt
))
2179 case VIEW_CONVERT_EXPR
:
2186 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2189 return gimple_num_ops (stmt
) - 1;
2193 /* Initialize VNO from STMT. */
2196 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2200 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2201 vno
->type
= gimple_expr_type (stmt
);
2202 switch (vno
->opcode
)
2206 case VIEW_CONVERT_EXPR
:
2208 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2213 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2214 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2215 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2219 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2220 for (i
= 0; i
< vno
->length
; ++i
)
2221 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2225 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2226 vno
->length
= gimple_num_ops (stmt
) - 1;
2227 for (i
= 0; i
< vno
->length
; ++i
)
2228 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2232 /* Compute the hashcode for VNO and look for it in the hash table;
2233 return the resulting value number if it exists in the hash table.
2234 Return NULL_TREE if it does not exist in the hash table or if the
2235 result field of the operation is NULL. VNRESULT will contain the
2236 vn_nary_op_t from the hashtable if it exists. */
2239 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2246 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2247 slot
= htab_find_slot_with_hash (current_info
->nary
, vno
, vno
->hashcode
,
2249 if (!slot
&& current_info
== optimistic_info
)
2250 slot
= htab_find_slot_with_hash (valid_info
->nary
, vno
, vno
->hashcode
,
2255 *vnresult
= (vn_nary_op_t
)*slot
;
2256 return ((vn_nary_op_t
)*slot
)->result
;
2259 /* Lookup a n-ary operation by its pieces and return the resulting value
2260 number if it exists in the hash table. Return NULL_TREE if it does
2261 not exist in the hash table or if the result field of the operation
2262 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2266 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2267 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2269 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2270 sizeof_vn_nary_op (length
));
2271 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2272 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2275 /* Lookup OP in the current hash table, and return the resulting value
2276 number if it exists in the hash table. Return NULL_TREE if it does
2277 not exist in the hash table or if the result field of the operation
2278 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2282 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2285 = XALLOCAVAR (struct vn_nary_op_s
,
2286 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2287 init_vn_nary_op_from_op (vno1
, op
);
2288 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2291 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2292 value number if it exists in the hash table. Return NULL_TREE if
2293 it does not exist in the hash table. VNRESULT will contain the
2294 vn_nary_op_t from the hashtable if it exists. */
2297 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2300 = XALLOCAVAR (struct vn_nary_op_s
,
2301 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2302 init_vn_nary_op_from_stmt (vno1
, stmt
);
2303 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2306 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2309 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2311 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2314 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2318 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2320 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2321 ¤t_info
->nary_obstack
);
2323 vno1
->value_id
= value_id
;
2324 vno1
->length
= length
;
2325 vno1
->result
= result
;
2330 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2331 VNO->HASHCODE first. */
2334 vn_nary_op_insert_into (vn_nary_op_t vno
, htab_t table
, bool compute_hash
)
2339 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2341 slot
= htab_find_slot_with_hash (table
, vno
, vno
->hashcode
, INSERT
);
2342 gcc_assert (!*slot
);
2348 /* Insert a n-ary operation into the current hash table using it's
2349 pieces. Return the vn_nary_op_t structure we created and put in
2353 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2354 tree type
, tree
*ops
,
2355 tree result
, unsigned int value_id
)
2357 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2358 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2359 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2362 /* Insert OP into the current hash table with a value number of
2363 RESULT. Return the vn_nary_op_t structure we created and put in
2367 vn_nary_op_insert (tree op
, tree result
)
2369 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2372 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2373 init_vn_nary_op_from_op (vno1
, op
);
2374 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2377 /* Insert the rhs of STMT into the current hash table with a value number of
2381 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2384 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2385 result
, VN_INFO (result
)->value_id
);
2386 init_vn_nary_op_from_stmt (vno1
, stmt
);
2387 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2390 /* Compute a hashcode for PHI operation VP1 and return it. */
2392 static inline hashval_t
2393 vn_phi_compute_hash (vn_phi_t vp1
)
2400 result
= vp1
->block
->index
;
2402 /* If all PHI arguments are constants we need to distinguish
2403 the PHI node via its type. */
2405 result
+= vn_hash_type (type
);
2407 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2409 if (phi1op
== VN_TOP
)
2411 result
= iterative_hash_expr (phi1op
, result
);
2417 /* Return the computed hashcode for phi operation P1. */
2420 vn_phi_hash (const void *p1
)
2422 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
2423 return vp1
->hashcode
;
2426 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2429 vn_phi_eq (const void *p1
, const void *p2
)
2431 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
2432 const_vn_phi_t
const vp2
= (const_vn_phi_t
) p2
;
2434 if (vp1
->hashcode
!= vp2
->hashcode
)
2437 if (vp1
->block
== vp2
->block
)
2442 /* If the PHI nodes do not have compatible types
2443 they are not the same. */
2444 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2447 /* Any phi in the same block will have it's arguments in the
2448 same edge order, because of how we store phi nodes. */
2449 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2451 tree phi2op
= vp2
->phiargs
[i
];
2452 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2454 if (!expressions_equal_p (phi1op
, phi2op
))
2462 static vec
<tree
> shared_lookup_phiargs
;
2464 /* Lookup PHI in the current hash table, and return the resulting
2465 value number if it exists in the hash table. Return NULL_TREE if
2466 it does not exist in the hash table. */
2469 vn_phi_lookup (gimple phi
)
2472 struct vn_phi_s vp1
;
2475 shared_lookup_phiargs
.truncate (0);
2477 /* Canonicalize the SSA_NAME's to their value number. */
2478 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2480 tree def
= PHI_ARG_DEF (phi
, i
);
2481 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2482 shared_lookup_phiargs
.safe_push (def
);
2484 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2485 vp1
.phiargs
= shared_lookup_phiargs
;
2486 vp1
.block
= gimple_bb (phi
);
2487 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2488 slot
= htab_find_slot_with_hash (current_info
->phis
, &vp1
, vp1
.hashcode
,
2490 if (!slot
&& current_info
== optimistic_info
)
2491 slot
= htab_find_slot_with_hash (valid_info
->phis
, &vp1
, vp1
.hashcode
,
2495 return ((vn_phi_t
)*slot
)->result
;
2498 /* Insert PHI into the current hash table with a value number of
2502 vn_phi_insert (gimple phi
, tree result
)
2505 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2507 vec
<tree
> args
= vNULL
;
2509 /* Canonicalize the SSA_NAME's to their value number. */
2510 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2512 tree def
= PHI_ARG_DEF (phi
, i
);
2513 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2514 args
.safe_push (def
);
2516 vp1
->value_id
= VN_INFO (result
)->value_id
;
2517 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2518 vp1
->phiargs
= args
;
2519 vp1
->block
= gimple_bb (phi
);
2520 vp1
->result
= result
;
2521 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2523 slot
= htab_find_slot_with_hash (current_info
->phis
, vp1
, vp1
->hashcode
,
2526 /* Because we iterate over phi operations more than once, it's
2527 possible the slot might already exist here, hence no assert.*/
2533 /* Print set of components in strongly connected component SCC to OUT. */
2536 print_scc (FILE *out
, vec
<tree
> scc
)
2541 fprintf (out
, "SCC consists of:");
2542 FOR_EACH_VEC_ELT (scc
, i
, var
)
2545 print_generic_expr (out
, var
, 0);
2547 fprintf (out
, "\n");
2550 /* Set the value number of FROM to TO, return true if it has changed
2554 set_ssa_val_to (tree from
, tree to
)
2556 tree currval
= SSA_VAL (from
);
2560 if (currval
== from
)
2562 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2564 fprintf (dump_file
, "Not changing value number of ");
2565 print_generic_expr (dump_file
, from
, 0);
2566 fprintf (dump_file
, " from VARYING to ");
2567 print_generic_expr (dump_file
, to
, 0);
2568 fprintf (dump_file
, "\n");
2572 else if (TREE_CODE (to
) == SSA_NAME
2573 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2577 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2578 and invariants. So assert that here. */
2579 gcc_assert (to
!= NULL_TREE
2581 || TREE_CODE (to
) == SSA_NAME
2582 || is_gimple_min_invariant (to
)));
2584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2586 fprintf (dump_file
, "Setting value number of ");
2587 print_generic_expr (dump_file
, from
, 0);
2588 fprintf (dump_file
, " to ");
2589 print_generic_expr (dump_file
, to
, 0);
2592 if (currval
!= to
&& !operand_equal_p (currval
, to
, OEP_PURE_SAME
))
2594 VN_INFO (from
)->valnum
= to
;
2595 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2596 fprintf (dump_file
, " (changed)\n");
2599 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2600 fprintf (dump_file
, "\n");
2604 /* Mark as processed all the definitions in the defining stmt of USE, or
2608 mark_use_processed (tree use
)
2612 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2614 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2616 VN_INFO (use
)->use_processed
= true;
2620 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2622 tree def
= DEF_FROM_PTR (defp
);
2624 VN_INFO (def
)->use_processed
= true;
2628 /* Set all definitions in STMT to value number to themselves.
2629 Return true if a value number changed. */
2632 defs_to_varying (gimple stmt
)
2634 bool changed
= false;
2638 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2640 tree def
= DEF_FROM_PTR (defp
);
2641 changed
|= set_ssa_val_to (def
, def
);
2646 static bool expr_has_constants (tree expr
);
2647 static tree
valueize_expr (tree expr
);
2649 /* Visit a copy between LHS and RHS, return true if the value number
2653 visit_copy (tree lhs
, tree rhs
)
2655 /* Follow chains of copies to their destination. */
2656 while (TREE_CODE (rhs
) == SSA_NAME
2657 && SSA_VAL (rhs
) != rhs
)
2658 rhs
= SSA_VAL (rhs
);
2660 /* The copy may have a more interesting constant filled expression
2661 (we don't, since we know our RHS is just an SSA name). */
2662 if (TREE_CODE (rhs
) == SSA_NAME
)
2664 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2665 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2668 return set_ssa_val_to (lhs
, rhs
);
2671 /* Visit a nary operator RHS, value number it, and return true if the
2672 value number of LHS has changed as a result. */
2675 visit_nary_op (tree lhs
, gimple stmt
)
2677 bool changed
= false;
2678 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2681 changed
= set_ssa_val_to (lhs
, result
);
2684 changed
= set_ssa_val_to (lhs
, lhs
);
2685 vn_nary_op_insert_stmt (stmt
, lhs
);
2691 /* Visit a call STMT storing into LHS. Return true if the value number
2692 of the LHS has changed as a result. */
2695 visit_reference_op_call (tree lhs
, gimple stmt
)
2697 bool changed
= false;
2698 struct vn_reference_s vr1
;
2699 vn_reference_t vnresult
= NULL
;
2700 tree vuse
= gimple_vuse (stmt
);
2701 tree vdef
= gimple_vdef (stmt
);
2703 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2704 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2707 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2708 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2709 vr1
.type
= gimple_expr_type (stmt
);
2711 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2712 vn_reference_lookup_1 (&vr1
, &vnresult
);
2716 if (vnresult
->result_vdef
)
2717 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2719 if (!vnresult
->result
&& lhs
)
2720 vnresult
->result
= lhs
;
2722 if (vnresult
->result
&& lhs
)
2724 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2726 if (VN_INFO (vnresult
->result
)->has_constants
)
2727 VN_INFO (lhs
)->has_constants
= true;
2735 changed
|= set_ssa_val_to (vdef
, vdef
);
2737 changed
|= set_ssa_val_to (lhs
, lhs
);
2738 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2739 vr2
->vuse
= vr1
.vuse
;
2740 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2741 vr2
->type
= vr1
.type
;
2743 vr2
->hashcode
= vr1
.hashcode
;
2745 vr2
->result_vdef
= vdef
;
2746 slot
= htab_find_slot_with_hash (current_info
->references
,
2747 vr2
, vr2
->hashcode
, INSERT
);
2749 free_reference (*slot
);
2756 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2757 and return true if the value number of the LHS has changed as a result. */
2760 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2762 bool changed
= false;
2766 last_vuse
= gimple_vuse (stmt
);
2767 last_vuse_ptr
= &last_vuse
;
2768 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2769 default_vn_walk_kind
, NULL
);
2770 last_vuse_ptr
= NULL
;
2772 /* If we have a VCE, try looking up its operand as it might be stored in
2773 a different type. */
2774 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2775 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2776 default_vn_walk_kind
, NULL
);
2778 /* We handle type-punning through unions by value-numbering based
2779 on offset and size of the access. Be prepared to handle a
2780 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2782 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2784 /* We will be setting the value number of lhs to the value number
2785 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2786 So first simplify and lookup this expression to see if it
2787 is already available. */
2788 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2789 if ((CONVERT_EXPR_P (val
)
2790 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2791 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2793 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2794 if ((CONVERT_EXPR_P (tem
)
2795 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2796 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2797 TREE_TYPE (val
), tem
)))
2801 if (!is_gimple_min_invariant (val
)
2802 && TREE_CODE (val
) != SSA_NAME
)
2803 result
= vn_nary_op_lookup (val
, NULL
);
2804 /* If the expression is not yet available, value-number lhs to
2805 a new SSA_NAME we create. */
2808 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2810 /* Initialize value-number information properly. */
2811 VN_INFO_GET (result
)->valnum
= result
;
2812 VN_INFO (result
)->value_id
= get_next_value_id ();
2813 VN_INFO (result
)->expr
= val
;
2814 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2815 VN_INFO (result
)->needs_insertion
= true;
2816 /* As all "inserted" statements are singleton SCCs, insert
2817 to the valid table. This is strictly needed to
2818 avoid re-generating new value SSA_NAMEs for the same
2819 expression during SCC iteration over and over (the
2820 optimistic table gets cleared after each iteration).
2821 We do not need to insert into the optimistic table, as
2822 lookups there will fall back to the valid table. */
2823 if (current_info
== optimistic_info
)
2825 current_info
= valid_info
;
2826 vn_nary_op_insert (val
, result
);
2827 current_info
= optimistic_info
;
2830 vn_nary_op_insert (val
, result
);
2831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2833 fprintf (dump_file
, "Inserting name ");
2834 print_generic_expr (dump_file
, result
, 0);
2835 fprintf (dump_file
, " for expression ");
2836 print_generic_expr (dump_file
, val
, 0);
2837 fprintf (dump_file
, "\n");
2844 changed
= set_ssa_val_to (lhs
, result
);
2845 if (TREE_CODE (result
) == SSA_NAME
2846 && VN_INFO (result
)->has_constants
)
2848 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2849 VN_INFO (lhs
)->has_constants
= true;
2854 changed
= set_ssa_val_to (lhs
, lhs
);
2855 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
2862 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2863 and return true if the value number of the LHS has changed as a result. */
2866 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2868 bool changed
= false;
2869 vn_reference_t vnresult
= NULL
;
2870 tree result
, assign
;
2871 bool resultsame
= false;
2872 tree vuse
= gimple_vuse (stmt
);
2873 tree vdef
= gimple_vdef (stmt
);
2875 /* First we want to lookup using the *vuses* from the store and see
2876 if there the last store to this location with the same address
2879 The vuses represent the memory state before the store. If the
2880 memory state, address, and value of the store is the same as the
2881 last store to this location, then this store will produce the
2882 same memory state as that store.
2884 In this case the vdef versions for this store are value numbered to those
2885 vuse versions, since they represent the same memory state after
2888 Otherwise, the vdefs for the store are used when inserting into
2889 the table, since the store generates a new memory state. */
2891 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
2895 if (TREE_CODE (result
) == SSA_NAME
)
2896 result
= SSA_VAL (result
);
2897 if (TREE_CODE (op
) == SSA_NAME
)
2899 resultsame
= expressions_equal_p (result
, op
);
2902 if (!result
|| !resultsame
)
2904 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2905 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
2908 VN_INFO (vdef
)->use_processed
= true;
2909 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2913 if (!result
|| !resultsame
)
2915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2917 fprintf (dump_file
, "No store match\n");
2918 fprintf (dump_file
, "Value numbering store ");
2919 print_generic_expr (dump_file
, lhs
, 0);
2920 fprintf (dump_file
, " to ");
2921 print_generic_expr (dump_file
, op
, 0);
2922 fprintf (dump_file
, "\n");
2924 /* Have to set value numbers before insert, since insert is
2925 going to valueize the references in-place. */
2928 changed
|= set_ssa_val_to (vdef
, vdef
);
2931 /* Do not insert structure copies into the tables. */
2932 if (is_gimple_min_invariant (op
)
2933 || is_gimple_reg (op
))
2934 vn_reference_insert (lhs
, op
, vdef
, NULL
);
2936 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2937 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
2941 /* We had a match, so value number the vdef to have the value
2942 number of the vuse it came from. */
2944 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2945 fprintf (dump_file
, "Store matched earlier value,"
2946 "value numbering store vdefs to matching vuses.\n");
2948 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
2954 /* Visit and value number PHI, return true if the value number
2958 visit_phi (gimple phi
)
2960 bool changed
= false;
2962 tree sameval
= VN_TOP
;
2963 bool allsame
= true;
2966 /* TODO: We could check for this in init_sccvn, and replace this
2967 with a gcc_assert. */
2968 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
2969 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
2971 /* See if all non-TOP arguments have the same value. TOP is
2972 equivalent to everything, so we can ignore it. */
2973 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2975 tree def
= PHI_ARG_DEF (phi
, i
);
2977 if (TREE_CODE (def
) == SSA_NAME
)
2978 def
= SSA_VAL (def
);
2981 if (sameval
== VN_TOP
)
2987 if (!expressions_equal_p (def
, sameval
))
2995 /* If all value numbered to the same value, the phi node has that
2999 if (is_gimple_min_invariant (sameval
))
3001 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
3002 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3006 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3007 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3010 if (TREE_CODE (sameval
) == SSA_NAME
)
3011 return visit_copy (PHI_RESULT (phi
), sameval
);
3013 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3016 /* Otherwise, see if it is equivalent to a phi node in this block. */
3017 result
= vn_phi_lookup (phi
);
3020 if (TREE_CODE (result
) == SSA_NAME
)
3021 changed
= visit_copy (PHI_RESULT (phi
), result
);
3023 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3027 vn_phi_insert (phi
, PHI_RESULT (phi
));
3028 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3029 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3030 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3036 /* Return true if EXPR contains constants. */
3039 expr_has_constants (tree expr
)
3041 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3044 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3047 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3048 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3049 /* Constants inside reference ops are rarely interesting, but
3050 it can take a lot of looking to find them. */
3052 case tcc_declaration
:
3055 return is_gimple_min_invariant (expr
);
3060 /* Return true if STMT contains constants. */
3063 stmt_has_constants (gimple stmt
)
3065 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3068 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3070 case GIMPLE_UNARY_RHS
:
3071 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
3073 case GIMPLE_BINARY_RHS
:
3074 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
3075 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
)));
3076 case GIMPLE_TERNARY_RHS
:
3077 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
3078 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
))
3079 || is_gimple_min_invariant (gimple_assign_rhs3 (stmt
)));
3080 case GIMPLE_SINGLE_RHS
:
3081 /* Constants inside reference ops are rarely interesting, but
3082 it can take a lot of looking to find them. */
3083 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
3090 /* Replace SSA_NAMES in expr with their value numbers, and return the
3092 This is performed in place. */
3095 valueize_expr (tree expr
)
3097 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3100 TREE_OPERAND (expr
, 1) = vn_valueize (TREE_OPERAND (expr
, 1));
3103 TREE_OPERAND (expr
, 0) = vn_valueize (TREE_OPERAND (expr
, 0));
3110 /* Simplify the binary expression RHS, and return the result if
3114 simplify_binary_expression (gimple stmt
)
3116 tree result
= NULL_TREE
;
3117 tree op0
= gimple_assign_rhs1 (stmt
);
3118 tree op1
= gimple_assign_rhs2 (stmt
);
3119 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3121 /* This will not catch every single case we could combine, but will
3122 catch those with constants. The goal here is to simultaneously
3123 combine constants between expressions, but avoid infinite
3124 expansion of expressions during simplification. */
3125 if (TREE_CODE (op0
) == SSA_NAME
)
3127 if (VN_INFO (op0
)->has_constants
3128 || TREE_CODE_CLASS (code
) == tcc_comparison
3129 || code
== COMPLEX_EXPR
)
3130 op0
= valueize_expr (vn_get_expr_for (op0
));
3132 op0
= vn_valueize (op0
);
3135 if (TREE_CODE (op1
) == SSA_NAME
)
3137 if (VN_INFO (op1
)->has_constants
3138 || code
== COMPLEX_EXPR
)
3139 op1
= valueize_expr (vn_get_expr_for (op1
));
3141 op1
= vn_valueize (op1
);
3144 /* Pointer plus constant can be represented as invariant address.
3145 Do so to allow further propatation, see also tree forwprop. */
3146 if (code
== POINTER_PLUS_EXPR
3147 && host_integerp (op1
, 1)
3148 && TREE_CODE (op0
) == ADDR_EXPR
3149 && is_gimple_min_invariant (op0
))
3150 return build_invariant_address (TREE_TYPE (op0
),
3151 TREE_OPERAND (op0
, 0),
3152 TREE_INT_CST_LOW (op1
));
3154 /* Avoid folding if nothing changed. */
3155 if (op0
== gimple_assign_rhs1 (stmt
)
3156 && op1
== gimple_assign_rhs2 (stmt
))
3159 fold_defer_overflow_warnings ();
3161 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3163 STRIP_USELESS_TYPE_CONVERSION (result
);
3165 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3168 /* Make sure result is not a complex expression consisting
3169 of operators of operators (IE (a + b) + (a + c))
3170 Otherwise, we will end up with unbounded expressions if
3171 fold does anything at all. */
3172 if (result
&& valid_gimple_rhs_p (result
))
3178 /* Simplify the unary expression RHS, and return the result if
3182 simplify_unary_expression (gimple stmt
)
3184 tree result
= NULL_TREE
;
3185 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3186 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3188 /* We handle some tcc_reference codes here that are all
3189 GIMPLE_ASSIGN_SINGLE codes. */
3190 if (code
== REALPART_EXPR
3191 || code
== IMAGPART_EXPR
3192 || code
== VIEW_CONVERT_EXPR
3193 || code
== BIT_FIELD_REF
)
3194 op0
= TREE_OPERAND (op0
, 0);
3196 if (TREE_CODE (op0
) != SSA_NAME
)
3200 if (VN_INFO (op0
)->has_constants
)
3201 op0
= valueize_expr (vn_get_expr_for (op0
));
3202 else if (CONVERT_EXPR_CODE_P (code
)
3203 || code
== REALPART_EXPR
3204 || code
== IMAGPART_EXPR
3205 || code
== VIEW_CONVERT_EXPR
3206 || code
== BIT_FIELD_REF
)
3208 /* We want to do tree-combining on conversion-like expressions.
3209 Make sure we feed only SSA_NAMEs or constants to fold though. */
3210 tree tem
= valueize_expr (vn_get_expr_for (op0
));
3211 if (UNARY_CLASS_P (tem
)
3212 || BINARY_CLASS_P (tem
)
3213 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3214 || TREE_CODE (tem
) == SSA_NAME
3215 || TREE_CODE (tem
) == CONSTRUCTOR
3216 || is_gimple_min_invariant (tem
))
3220 /* Avoid folding if nothing changed, but remember the expression. */
3221 if (op0
== orig_op0
)
3224 if (code
== BIT_FIELD_REF
)
3226 tree rhs
= gimple_assign_rhs1 (stmt
);
3227 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3228 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3231 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3234 STRIP_USELESS_TYPE_CONVERSION (result
);
3235 if (valid_gimple_rhs_p (result
))
3242 /* Try to simplify RHS using equivalences and constant folding. */
3245 try_to_simplify (gimple stmt
)
3247 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3250 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3251 in this case, there is no point in doing extra work. */
3252 if (code
== SSA_NAME
)
3255 /* First try constant folding based on our current lattice. */
3256 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3258 && (TREE_CODE (tem
) == SSA_NAME
3259 || is_gimple_min_invariant (tem
)))
3262 /* If that didn't work try combining multiple statements. */
3263 switch (TREE_CODE_CLASS (code
))
3266 /* Fallthrough for some unary codes that can operate on registers. */
3267 if (!(code
== REALPART_EXPR
3268 || code
== IMAGPART_EXPR
3269 || code
== VIEW_CONVERT_EXPR
3270 || code
== BIT_FIELD_REF
))
3272 /* We could do a little more with unary ops, if they expand
3273 into binary ops, but it's debatable whether it is worth it. */
3275 return simplify_unary_expression (stmt
);
3277 case tcc_comparison
:
3279 return simplify_binary_expression (stmt
);
3288 /* Visit and value number USE, return true if the value number
3292 visit_use (tree use
)
3294 bool changed
= false;
3295 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3297 mark_use_processed (use
);
3299 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3300 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3301 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3303 fprintf (dump_file
, "Value numbering ");
3304 print_generic_expr (dump_file
, use
, 0);
3305 fprintf (dump_file
, " stmt = ");
3306 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3309 /* Handle uninitialized uses. */
3310 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3311 changed
= set_ssa_val_to (use
, use
);
3314 if (gimple_code (stmt
) == GIMPLE_PHI
)
3315 changed
= visit_phi (stmt
);
3316 else if (gimple_has_volatile_ops (stmt
))
3317 changed
= defs_to_varying (stmt
);
3318 else if (is_gimple_assign (stmt
))
3320 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3321 tree lhs
= gimple_assign_lhs (stmt
);
3322 tree rhs1
= gimple_assign_rhs1 (stmt
);
3325 /* Shortcut for copies. Simplifying copies is pointless,
3326 since we copy the expression and value they represent. */
3327 if (code
== SSA_NAME
3328 && TREE_CODE (lhs
) == SSA_NAME
)
3330 changed
= visit_copy (lhs
, rhs1
);
3333 simplified
= try_to_simplify (stmt
);
3336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3338 fprintf (dump_file
, "RHS ");
3339 print_gimple_expr (dump_file
, stmt
, 0, 0);
3340 fprintf (dump_file
, " simplified to ");
3341 print_generic_expr (dump_file
, simplified
, 0);
3342 if (TREE_CODE (lhs
) == SSA_NAME
)
3343 fprintf (dump_file
, " has constants %d\n",
3344 expr_has_constants (simplified
));
3346 fprintf (dump_file
, "\n");
3349 /* Setting value numbers to constants will occasionally
3350 screw up phi congruence because constants are not
3351 uniquely associated with a single ssa name that can be
3354 && is_gimple_min_invariant (simplified
)
3355 && TREE_CODE (lhs
) == SSA_NAME
)
3357 VN_INFO (lhs
)->expr
= simplified
;
3358 VN_INFO (lhs
)->has_constants
= true;
3359 changed
= set_ssa_val_to (lhs
, simplified
);
3363 && TREE_CODE (simplified
) == SSA_NAME
3364 && TREE_CODE (lhs
) == SSA_NAME
)
3366 changed
= visit_copy (lhs
, simplified
);
3369 else if (simplified
)
3371 if (TREE_CODE (lhs
) == SSA_NAME
)
3373 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3374 /* We have to unshare the expression or else
3375 valuizing may change the IL stream. */
3376 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3379 else if (stmt_has_constants (stmt
)
3380 && TREE_CODE (lhs
) == SSA_NAME
)
3381 VN_INFO (lhs
)->has_constants
= true;
3382 else if (TREE_CODE (lhs
) == SSA_NAME
)
3384 /* We reset expr and constantness here because we may
3385 have been value numbering optimistically, and
3386 iterating. They may become non-constant in this case,
3387 even if they were optimistically constant. */
3389 VN_INFO (lhs
)->has_constants
= false;
3390 VN_INFO (lhs
)->expr
= NULL_TREE
;
3393 if ((TREE_CODE (lhs
) == SSA_NAME
3394 /* We can substitute SSA_NAMEs that are live over
3395 abnormal edges with their constant value. */
3396 && !(gimple_assign_copy_p (stmt
)
3397 && is_gimple_min_invariant (rhs1
))
3399 && is_gimple_min_invariant (simplified
))
3400 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3401 /* Stores or copies from SSA_NAMEs that are live over
3402 abnormal edges are a problem. */
3403 || (code
== SSA_NAME
3404 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3405 changed
= defs_to_varying (stmt
);
3406 else if (REFERENCE_CLASS_P (lhs
)
3408 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3409 else if (TREE_CODE (lhs
) == SSA_NAME
)
3411 if ((gimple_assign_copy_p (stmt
)
3412 && is_gimple_min_invariant (rhs1
))
3414 && is_gimple_min_invariant (simplified
)))
3416 VN_INFO (lhs
)->has_constants
= true;
3418 changed
= set_ssa_val_to (lhs
, simplified
);
3420 changed
= set_ssa_val_to (lhs
, rhs1
);
3424 /* First try to lookup the simplified expression. */
3427 enum gimple_rhs_class rhs_class
;
3430 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3431 if ((rhs_class
== GIMPLE_UNARY_RHS
3432 || rhs_class
== GIMPLE_BINARY_RHS
3433 || rhs_class
== GIMPLE_TERNARY_RHS
)
3434 && valid_gimple_rhs_p (simplified
))
3436 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3439 changed
= set_ssa_val_to (lhs
, result
);
3445 /* Otherwise visit the original statement. */
3446 switch (vn_get_stmt_kind (stmt
))
3449 changed
= visit_nary_op (lhs
, stmt
);
3452 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3455 changed
= defs_to_varying (stmt
);
3461 changed
= defs_to_varying (stmt
);
3463 else if (is_gimple_call (stmt
))
3465 tree lhs
= gimple_call_lhs (stmt
);
3467 /* ??? We could try to simplify calls. */
3469 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3471 if (stmt_has_constants (stmt
))
3472 VN_INFO (lhs
)->has_constants
= true;
3475 /* We reset expr and constantness here because we may
3476 have been value numbering optimistically, and
3477 iterating. They may become non-constant in this case,
3478 even if they were optimistically constant. */
3479 VN_INFO (lhs
)->has_constants
= false;
3480 VN_INFO (lhs
)->expr
= NULL_TREE
;
3483 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3485 changed
= defs_to_varying (stmt
);
3490 if (!gimple_call_internal_p (stmt
)
3491 && (/* Calls to the same function with the same vuse
3492 and the same operands do not necessarily return the same
3493 value, unless they're pure or const. */
3494 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3495 /* If calls have a vdef, subsequent calls won't have
3496 the same incoming vuse. So, if 2 calls with vdef have the
3497 same vuse, we know they're not subsequent.
3498 We can value number 2 calls to the same function with the
3499 same vuse and the same operands which are not subsequent
3500 the same, because there is no code in the program that can
3501 compare the 2 values. */
3502 || gimple_vdef (stmt
)))
3503 changed
= visit_reference_op_call (lhs
, stmt
);
3505 changed
= defs_to_varying (stmt
);
3508 changed
= defs_to_varying (stmt
);
3514 /* Compare two operands by reverse postorder index */
3517 compare_ops (const void *pa
, const void *pb
)
3519 const tree opa
= *((const tree
*)pa
);
3520 const tree opb
= *((const tree
*)pb
);
3521 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3522 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3526 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3527 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3528 else if (gimple_nop_p (opstmta
))
3530 else if (gimple_nop_p (opstmtb
))
3533 bba
= gimple_bb (opstmta
);
3534 bbb
= gimple_bb (opstmtb
);
3537 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3545 if (gimple_code (opstmta
) == GIMPLE_PHI
3546 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3547 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3548 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3550 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3552 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3553 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3555 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3557 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3560 /* Sort an array containing members of a strongly connected component
3561 SCC so that the members are ordered by RPO number.
3562 This means that when the sort is complete, iterating through the
3563 array will give you the members in RPO order. */
3566 sort_scc (vec
<tree
> scc
)
3568 scc
.qsort (compare_ops
);
3571 /* Insert the no longer used nary ONARY to the hash INFO. */
3574 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3576 size_t size
= sizeof_vn_nary_op (onary
->length
);
3577 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3578 &info
->nary_obstack
);
3579 memcpy (nary
, onary
, size
);
3580 vn_nary_op_insert_into (nary
, info
->nary
, false);
3583 /* Insert the no longer used phi OPHI to the hash INFO. */
3586 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3588 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3590 memcpy (phi
, ophi
, sizeof (*phi
));
3591 ophi
->phiargs
.create (0);
3592 slot
= htab_find_slot_with_hash (info
->phis
, phi
, phi
->hashcode
, INSERT
);
3593 gcc_assert (!*slot
);
3597 /* Insert the no longer used reference OREF to the hash INFO. */
3600 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3604 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3605 memcpy (ref
, oref
, sizeof (*ref
));
3606 oref
->operands
.create (0);
3607 slot
= htab_find_slot_with_hash (info
->references
, ref
, ref
->hashcode
,
3610 free_reference (*slot
);
3614 /* Process a strongly connected component in the SSA graph. */
3617 process_scc (vec
<tree
> scc
)
3621 unsigned int iterations
= 0;
3622 bool changed
= true;
3628 /* If the SCC has a single member, just visit it. */
3629 if (scc
.length () == 1)
3632 if (VN_INFO (use
)->use_processed
)
3634 /* We need to make sure it doesn't form a cycle itself, which can
3635 happen for self-referential PHI nodes. In that case we would
3636 end up inserting an expression with VN_TOP operands into the
3637 valid table which makes us derive bogus equivalences later.
3638 The cheapest way to check this is to assume it for all PHI nodes. */
3639 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3640 /* Fallthru to iteration. */ ;
3648 /* Iterate over the SCC with the optimistic table until it stops
3650 current_info
= optimistic_info
;
3655 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3656 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3657 /* As we are value-numbering optimistically we have to
3658 clear the expression tables and the simplified expressions
3659 in each iteration until we converge. */
3660 htab_empty (optimistic_info
->nary
);
3661 htab_empty (optimistic_info
->phis
);
3662 htab_empty (optimistic_info
->references
);
3663 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3664 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3665 empty_alloc_pool (optimistic_info
->phis_pool
);
3666 empty_alloc_pool (optimistic_info
->references_pool
);
3667 FOR_EACH_VEC_ELT (scc
, i
, var
)
3668 VN_INFO (var
)->expr
= NULL_TREE
;
3669 FOR_EACH_VEC_ELT (scc
, i
, var
)
3670 changed
|= visit_use (var
);
3673 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3675 /* Finally, copy the contents of the no longer used optimistic
3676 table to the valid table. */
3677 FOR_EACH_HTAB_ELEMENT (optimistic_info
->nary
, nary
, vn_nary_op_t
, hi
)
3678 copy_nary (nary
, valid_info
);
3679 FOR_EACH_HTAB_ELEMENT (optimistic_info
->phis
, phi
, vn_phi_t
, hi
)
3680 copy_phi (phi
, valid_info
);
3681 FOR_EACH_HTAB_ELEMENT (optimistic_info
->references
, ref
, vn_reference_t
, hi
)
3682 copy_reference (ref
, valid_info
);
3684 current_info
= valid_info
;
3688 /* Pop the components of the found SCC for NAME off the SCC stack
3689 and process them. Returns true if all went well, false if
3690 we run into resource limits. */
3693 extract_and_process_scc_for_name (tree name
)
3695 vec
<tree
> scc
= vNULL
;
3698 /* Found an SCC, pop the components off the SCC stack and
3702 x
= sccstack
.pop ();
3704 VN_INFO (x
)->on_sccstack
= false;
3706 } while (x
!= name
);
3708 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3710 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3713 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3714 "SCC size %u exceeding %u\n", scc
.length (),
3715 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3721 if (scc
.length () > 1)
3724 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3725 print_scc (dump_file
, scc
);
3734 /* Depth first search on NAME to discover and process SCC's in the SSA
3736 Execution of this algorithm relies on the fact that the SCC's are
3737 popped off the stack in topological order.
3738 Returns true if successful, false if we stopped processing SCC's due
3739 to resource constraints. */
3744 vec
<ssa_op_iter
> itervec
= vNULL
;
3745 vec
<tree
> namevec
= vNULL
;
3746 use_operand_p usep
= NULL
;
3753 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3754 VN_INFO (name
)->visited
= true;
3755 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3757 sccstack
.safe_push (name
);
3758 VN_INFO (name
)->on_sccstack
= true;
3759 defstmt
= SSA_NAME_DEF_STMT (name
);
3761 /* Recursively DFS on our operands, looking for SCC's. */
3762 if (!gimple_nop_p (defstmt
))
3764 /* Push a new iterator. */
3765 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3766 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3768 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3771 clear_and_done_ssa_iter (&iter
);
3775 /* If we are done processing uses of a name, go up the stack
3776 of iterators and process SCCs as we found them. */
3777 if (op_iter_done (&iter
))
3779 /* See if we found an SCC. */
3780 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3781 if (!extract_and_process_scc_for_name (name
))
3788 /* Check if we are done. */
3789 if (namevec
.is_empty ())
3796 /* Restore the last use walker and continue walking there. */
3798 name
= namevec
.pop ();
3799 memcpy (&iter
, &itervec
.last (),
3800 sizeof (ssa_op_iter
));
3802 goto continue_walking
;
3805 use
= USE_FROM_PTR (usep
);
3807 /* Since we handle phi nodes, we will sometimes get
3808 invariants in the use expression. */
3809 if (TREE_CODE (use
) == SSA_NAME
)
3811 if (! (VN_INFO (use
)->visited
))
3813 /* Recurse by pushing the current use walking state on
3814 the stack and starting over. */
3815 itervec
.safe_push (iter
);
3816 namevec
.safe_push (name
);
3821 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3822 VN_INFO (use
)->low
);
3824 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3825 && VN_INFO (use
)->on_sccstack
)
3827 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3828 VN_INFO (name
)->low
);
3832 usep
= op_iter_next_use (&iter
);
3836 /* Allocate a value number table. */
3839 allocate_vn_table (vn_tables_t table
)
3841 table
->phis
= htab_create (23, vn_phi_hash
, vn_phi_eq
, free_phi
);
3842 table
->nary
= htab_create (23, vn_nary_op_hash
, vn_nary_op_eq
, NULL
);
3843 table
->references
= htab_create (23, vn_reference_hash
, vn_reference_eq
,
3846 gcc_obstack_init (&table
->nary_obstack
);
3847 table
->phis_pool
= create_alloc_pool ("VN phis",
3848 sizeof (struct vn_phi_s
),
3850 table
->references_pool
= create_alloc_pool ("VN references",
3851 sizeof (struct vn_reference_s
),
3855 /* Free a value number table. */
3858 free_vn_table (vn_tables_t table
)
3860 htab_delete (table
->phis
);
3861 htab_delete (table
->nary
);
3862 htab_delete (table
->references
);
3863 obstack_free (&table
->nary_obstack
, NULL
);
3864 free_alloc_pool (table
->phis_pool
);
3865 free_alloc_pool (table
->references_pool
);
3873 int *rpo_numbers_temp
;
3875 calculate_dominance_info (CDI_DOMINATORS
);
3876 sccstack
.create (0);
3877 constant_to_value_id
= htab_create (23, vn_constant_hash
, vn_constant_eq
,
3880 constant_value_ids
= BITMAP_ALLOC (NULL
);
3885 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
3886 /* VEC_alloc doesn't actually grow it to the right size, it just
3887 preallocates the space to do so. */
3888 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
3889 gcc_obstack_init (&vn_ssa_aux_obstack
);
3891 shared_lookup_phiargs
.create (0);
3892 shared_lookup_references
.create (0);
3893 rpo_numbers
= XNEWVEC (int, last_basic_block
);
3894 rpo_numbers_temp
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3895 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
3897 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3898 the i'th block in RPO order is bb. We want to map bb's to RPO
3899 numbers, so we need to rearrange this array. */
3900 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
3901 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
3903 XDELETE (rpo_numbers_temp
);
3905 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
3907 /* Create the VN_INFO structures, and initialize value numbers to
3909 for (i
= 0; i
< num_ssa_names
; i
++)
3911 tree name
= ssa_name (i
);
3914 VN_INFO_GET (name
)->valnum
= VN_TOP
;
3915 VN_INFO (name
)->expr
= NULL_TREE
;
3916 VN_INFO (name
)->value_id
= 0;
3920 renumber_gimple_stmt_uids ();
3922 /* Create the valid and optimistic value numbering tables. */
3923 valid_info
= XCNEW (struct vn_tables_s
);
3924 allocate_vn_table (valid_info
);
3925 optimistic_info
= XCNEW (struct vn_tables_s
);
3926 allocate_vn_table (optimistic_info
);
3934 htab_delete (constant_to_value_id
);
3935 BITMAP_FREE (constant_value_ids
);
3936 shared_lookup_phiargs
.release ();
3937 shared_lookup_references
.release ();
3938 XDELETEVEC (rpo_numbers
);
3940 for (i
= 0; i
< num_ssa_names
; i
++)
3942 tree name
= ssa_name (i
);
3944 && VN_INFO (name
)->needs_insertion
)
3945 release_ssa_name (name
);
3947 obstack_free (&vn_ssa_aux_obstack
, NULL
);
3948 vn_ssa_aux_table
.release ();
3950 sccstack
.release ();
3951 free_vn_table (valid_info
);
3952 XDELETE (valid_info
);
3953 free_vn_table (optimistic_info
);
3954 XDELETE (optimistic_info
);
3957 /* Set *ID according to RESULT. */
3960 set_value_id_for_result (tree result
, unsigned int *id
)
3962 if (result
&& TREE_CODE (result
) == SSA_NAME
)
3963 *id
= VN_INFO (result
)->value_id
;
3964 else if (result
&& is_gimple_min_invariant (result
))
3965 *id
= get_or_alloc_constant_value_id (result
);
3967 *id
= get_next_value_id ();
3970 /* Set the value ids in the valid hash tables. */
3973 set_hashtable_value_ids (void)
3980 /* Now set the value ids of the things we had put in the hash
3983 FOR_EACH_HTAB_ELEMENT (valid_info
->nary
,
3984 vno
, vn_nary_op_t
, hi
)
3985 set_value_id_for_result (vno
->result
, &vno
->value_id
);
3987 FOR_EACH_HTAB_ELEMENT (valid_info
->phis
,
3989 set_value_id_for_result (vp
->result
, &vp
->value_id
);
3991 FOR_EACH_HTAB_ELEMENT (valid_info
->references
,
3992 vr
, vn_reference_t
, hi
)
3993 set_value_id_for_result (vr
->result
, &vr
->value_id
);
3996 /* Do SCCVN. Returns true if it finished, false if we bailed out
3997 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
3998 how we use the alias oracle walking during the VN process. */
4001 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4006 default_vn_walk_kind
= default_vn_walk_kind_
;
4009 current_info
= valid_info
;
4011 for (param
= DECL_ARGUMENTS (current_function_decl
);
4013 param
= DECL_CHAIN (param
))
4015 tree def
= ssa_default_def (cfun
, param
);
4017 VN_INFO (def
)->valnum
= def
;
4020 for (i
= 1; i
< num_ssa_names
; ++i
)
4022 tree name
= ssa_name (i
);
4024 && VN_INFO (name
)->visited
== false
4025 && !has_zero_uses (name
))
4033 /* Initialize the value ids. */
4035 for (i
= 1; i
< num_ssa_names
; ++i
)
4037 tree name
= ssa_name (i
);
4041 info
= VN_INFO (name
);
4042 if (info
->valnum
== name
4043 || info
->valnum
== VN_TOP
)
4044 info
->value_id
= get_next_value_id ();
4045 else if (is_gimple_min_invariant (info
->valnum
))
4046 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4050 for (i
= 1; i
< num_ssa_names
; ++i
)
4052 tree name
= ssa_name (i
);
4056 info
= VN_INFO (name
);
4057 if (TREE_CODE (info
->valnum
) == SSA_NAME
4058 && info
->valnum
!= name
4059 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4060 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4063 set_hashtable_value_ids ();
4065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4067 fprintf (dump_file
, "Value numbers:\n");
4068 for (i
= 0; i
< num_ssa_names
; i
++)
4070 tree name
= ssa_name (i
);
4072 && VN_INFO (name
)->visited
4073 && SSA_VAL (name
) != name
)
4075 print_generic_expr (dump_file
, name
, 0);
4076 fprintf (dump_file
, " = ");
4077 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4078 fprintf (dump_file
, "\n");
4086 /* Return the maximum value id we have ever seen. */
4089 get_max_value_id (void)
4091 return next_value_id
;
4094 /* Return the next unique value id. */
4097 get_next_value_id (void)
4099 return next_value_id
++;
4103 /* Compare two expressions E1 and E2 and return true if they are equal. */
4106 expressions_equal_p (tree e1
, tree e2
)
4108 /* The obvious case. */
4112 /* If only one of them is null, they cannot be equal. */
4116 /* Now perform the actual comparison. */
4117 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4118 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4125 /* Return true if the nary operation NARY may trap. This is a copy
4126 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4129 vn_nary_may_trap (vn_nary_op_t nary
)
4132 tree rhs2
= NULL_TREE
;
4133 bool honor_nans
= false;
4134 bool honor_snans
= false;
4135 bool fp_operation
= false;
4136 bool honor_trapv
= false;
4140 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4141 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4142 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4145 fp_operation
= FLOAT_TYPE_P (type
);
4148 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4149 honor_snans
= flag_signaling_nans
!= 0;
4151 else if (INTEGRAL_TYPE_P (type
)
4152 && TYPE_OVERFLOW_TRAPS (type
))
4155 if (nary
->length
>= 2)
4157 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4159 honor_nans
, honor_snans
, rhs2
,
4165 for (i
= 0; i
< nary
->length
; ++i
)
4166 if (tree_could_trap_p (nary
->op
[i
]))