1 /* SCC value numbering for trees
2 Copyright (C) 2006-2015 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"
30 #include "fold-const.h"
31 #include "stor-layout.h"
33 #include "gimple-pretty-print.h"
34 #include "tree-inline.h"
35 #include "internal-fn.h"
36 #include "gimple-fold.h"
40 #include "insn-config.h"
52 #include "alloc-pool.h"
55 #include "tree-ssa-propagate.h"
56 #include "tree-ssa-sccvn.h"
60 #include "gimple-iterator.h"
61 #include "gimple-match.h"
63 /* This algorithm is based on the SCC algorithm presented by Keith
64 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
65 (http://citeseer.ist.psu.edu/41805.html). In
66 straight line code, it is equivalent to a regular hash based value
67 numbering that is performed in reverse postorder.
69 For code with cycles, there are two alternatives, both of which
70 require keeping the hashtables separate from the actual list of
71 value numbers for SSA names.
73 1. Iterate value numbering in an RPO walk of the blocks, removing
74 all the entries from the hashtable after each iteration (but
75 keeping the SSA name->value number mapping between iterations).
76 Iterate until it does not change.
78 2. Perform value numbering as part of an SCC walk on the SSA graph,
79 iterating only the cycles in the SSA graph until they do not change
80 (using a separate, optimistic hashtable for value numbering the SCC
83 The second is not just faster in practice (because most SSA graph
84 cycles do not involve all the variables in the graph), it also has
87 One of these nice properties is that when we pop an SCC off the
88 stack, we are guaranteed to have processed all the operands coming from
89 *outside of that SCC*, so we do not need to do anything special to
90 ensure they have value numbers.
92 Another nice property is that the SCC walk is done as part of a DFS
93 of the SSA graph, which makes it easy to perform combining and
94 simplifying operations at the same time.
96 The code below is deliberately written in a way that makes it easy
97 to separate the SCC walk from the other work it does.
99 In order to propagate constants through the code, we track which
100 expressions contain constants, and use those while folding. In
101 theory, we could also track expressions whose value numbers are
102 replaced, in case we end up folding based on expression
105 In order to value number memory, we assign value numbers to vuses.
106 This enables us to note that, for example, stores to the same
107 address of the same value from the same starting memory states are
111 1. We can iterate only the changing portions of the SCC's, but
112 I have not seen an SCC big enough for this to be a win.
113 2. If you differentiate between phi nodes for loops and phi nodes
114 for if-then-else, you can properly consider phi nodes in different
115 blocks for equivalence.
116 3. We could value number vuses in more cases, particularly, whole
121 static tree
*last_vuse_ptr
;
122 static vn_lookup_kind vn_walk_kind
;
123 static vn_lookup_kind default_vn_walk_kind
;
126 /* vn_nary_op hashtable helpers. */
128 struct vn_nary_op_hasher
: nofree_ptr_hash
<vn_nary_op_s
>
130 typedef vn_nary_op_s
*compare_type
;
131 static inline hashval_t
hash (const vn_nary_op_s
*);
132 static inline bool equal (const vn_nary_op_s
*, const vn_nary_op_s
*);
135 /* Return the computed hashcode for nary operation P1. */
138 vn_nary_op_hasher::hash (const vn_nary_op_s
*vno1
)
140 return vno1
->hashcode
;
143 /* Compare nary operations P1 and P2 and return true if they are
147 vn_nary_op_hasher::equal (const vn_nary_op_s
*vno1
, const vn_nary_op_s
*vno2
)
149 return vn_nary_op_eq (vno1
, vno2
);
152 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
153 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
156 /* vn_phi hashtable helpers. */
159 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
161 struct vn_phi_hasher
: pointer_hash
<vn_phi_s
>
163 static inline hashval_t
hash (const vn_phi_s
*);
164 static inline bool equal (const vn_phi_s
*, const vn_phi_s
*);
165 static inline void remove (vn_phi_s
*);
168 /* Return the computed hashcode for phi operation P1. */
171 vn_phi_hasher::hash (const vn_phi_s
*vp1
)
173 return vp1
->hashcode
;
176 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
179 vn_phi_hasher::equal (const vn_phi_s
*vp1
, const vn_phi_s
*vp2
)
181 return vn_phi_eq (vp1
, vp2
);
184 /* Free a phi operation structure VP. */
187 vn_phi_hasher::remove (vn_phi_s
*phi
)
189 phi
->phiargs
.release ();
192 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
193 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
196 /* Compare two reference operands P1 and P2 for equality. Return true if
197 they are equal, and false otherwise. */
200 vn_reference_op_eq (const void *p1
, const void *p2
)
202 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
203 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
205 return (vro1
->opcode
== vro2
->opcode
206 /* We do not care for differences in type qualification. */
207 && (vro1
->type
== vro2
->type
208 || (vro1
->type
&& vro2
->type
209 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
210 TYPE_MAIN_VARIANT (vro2
->type
))))
211 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
212 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
213 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
216 /* Free a reference operation structure VP. */
219 free_reference (vn_reference_s
*vr
)
221 vr
->operands
.release ();
225 /* vn_reference hashtable helpers. */
227 struct vn_reference_hasher
: pointer_hash
<vn_reference_s
>
229 static inline hashval_t
hash (const vn_reference_s
*);
230 static inline bool equal (const vn_reference_s
*, const vn_reference_s
*);
231 static inline void remove (vn_reference_s
*);
234 /* Return the hashcode for a given reference operation P1. */
237 vn_reference_hasher::hash (const vn_reference_s
*vr1
)
239 return vr1
->hashcode
;
243 vn_reference_hasher::equal (const vn_reference_s
*v
, const vn_reference_s
*c
)
245 return vn_reference_eq (v
, c
);
249 vn_reference_hasher::remove (vn_reference_s
*v
)
254 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
255 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
258 /* The set of hashtables and alloc_pool's for their items. */
260 typedef struct vn_tables_s
262 vn_nary_op_table_type
*nary
;
263 vn_phi_table_type
*phis
;
264 vn_reference_table_type
*references
;
265 struct obstack nary_obstack
;
266 object_allocator
<vn_phi_s
> *phis_pool
;
267 object_allocator
<vn_reference_s
> *references_pool
;
271 /* vn_constant hashtable helpers. */
273 struct vn_constant_hasher
: free_ptr_hash
<vn_constant_s
>
275 static inline hashval_t
hash (const vn_constant_s
*);
276 static inline bool equal (const vn_constant_s
*, const vn_constant_s
*);
279 /* Hash table hash function for vn_constant_t. */
282 vn_constant_hasher::hash (const vn_constant_s
*vc1
)
284 return vc1
->hashcode
;
287 /* Hash table equality function for vn_constant_t. */
290 vn_constant_hasher::equal (const vn_constant_s
*vc1
, const vn_constant_s
*vc2
)
292 if (vc1
->hashcode
!= vc2
->hashcode
)
295 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
298 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
299 static bitmap constant_value_ids
;
302 /* Valid hashtables storing information we have proven to be
305 static vn_tables_t valid_info
;
307 /* Optimistic hashtables storing information we are making assumptions about
308 during iterations. */
310 static vn_tables_t optimistic_info
;
312 /* Pointer to the set of hashtables that is currently being used.
313 Should always point to either the optimistic_info, or the
316 static vn_tables_t current_info
;
319 /* Reverse post order index for each basic block. */
321 static int *rpo_numbers
;
323 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
325 /* Return the SSA value of the VUSE x, supporting released VDEFs
326 during elimination which will value-number the VDEF to the
327 associated VUSE (but not substitute in the whole lattice). */
330 vuse_ssa_val (tree x
)
339 while (SSA_NAME_IN_FREE_LIST (x
));
344 /* This represents the top of the VN lattice, which is the universal
349 /* Unique counter for our value ids. */
351 static unsigned int next_value_id
;
353 /* Next DFS number and the stack for strongly connected component
356 static unsigned int next_dfs_num
;
357 static vec
<tree
> sccstack
;
361 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
362 are allocated on an obstack for locality reasons, and to free them
363 without looping over the vec. */
365 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
366 static struct obstack vn_ssa_aux_obstack
;
368 /* Return whether there is value numbering information for a given SSA name. */
371 has_VN_INFO (tree name
)
373 if (SSA_NAME_VERSION (name
) < vn_ssa_aux_table
.length ())
374 return vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] != NULL
;
378 /* Return the value numbering information for a given SSA name. */
383 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
384 gcc_checking_assert (res
);
388 /* Set the value numbering info for a given SSA name to a given
392 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
394 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
397 /* Initialize the value numbering info for a given SSA name.
398 This should be called just once for every SSA name. */
401 VN_INFO_GET (tree name
)
403 vn_ssa_aux_t newinfo
;
405 gcc_assert (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ()
406 || vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] == NULL
);
407 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
408 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
409 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
410 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
411 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
416 /* Return the vn_kind the expression computed by the stmt should be
420 vn_get_stmt_kind (gimple
*stmt
)
422 switch (gimple_code (stmt
))
430 enum tree_code code
= gimple_assign_rhs_code (stmt
);
431 tree rhs1
= gimple_assign_rhs1 (stmt
);
432 switch (get_gimple_rhs_class (code
))
434 case GIMPLE_UNARY_RHS
:
435 case GIMPLE_BINARY_RHS
:
436 case GIMPLE_TERNARY_RHS
:
438 case GIMPLE_SINGLE_RHS
:
439 switch (TREE_CODE_CLASS (code
))
442 /* VOP-less references can go through unary case. */
443 if ((code
== REALPART_EXPR
444 || code
== IMAGPART_EXPR
445 || code
== VIEW_CONVERT_EXPR
446 || code
== BIT_FIELD_REF
)
447 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
451 case tcc_declaration
:
458 if (code
== ADDR_EXPR
)
459 return (is_gimple_min_invariant (rhs1
)
460 ? VN_CONSTANT
: VN_REFERENCE
);
461 else if (code
== CONSTRUCTOR
)
474 /* Lookup a value id for CONSTANT and return it. If it does not
478 get_constant_value_id (tree constant
)
480 vn_constant_s
**slot
;
481 struct vn_constant_s vc
;
483 vc
.hashcode
= vn_hash_constant_with_type (constant
);
484 vc
.constant
= constant
;
485 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
487 return (*slot
)->value_id
;
491 /* Lookup a value id for CONSTANT, and if it does not exist, create a
492 new one and return it. If it does exist, return it. */
495 get_or_alloc_constant_value_id (tree constant
)
497 vn_constant_s
**slot
;
498 struct vn_constant_s vc
;
501 vc
.hashcode
= vn_hash_constant_with_type (constant
);
502 vc
.constant
= constant
;
503 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
505 return (*slot
)->value_id
;
507 vcp
= XNEW (struct vn_constant_s
);
508 vcp
->hashcode
= vc
.hashcode
;
509 vcp
->constant
= constant
;
510 vcp
->value_id
= get_next_value_id ();
512 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
513 return vcp
->value_id
;
516 /* Return true if V is a value id for a constant. */
519 value_id_constant_p (unsigned int v
)
521 return bitmap_bit_p (constant_value_ids
, v
);
524 /* Compute the hash for a reference operand VRO1. */
527 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
529 hstate
.add_int (vro1
->opcode
);
531 inchash::add_expr (vro1
->op0
, hstate
);
533 inchash::add_expr (vro1
->op1
, hstate
);
535 inchash::add_expr (vro1
->op2
, hstate
);
538 /* Compute a hash for the reference operation VR1 and return it. */
541 vn_reference_compute_hash (const vn_reference_t vr1
)
543 inchash::hash hstate
;
546 vn_reference_op_t vro
;
547 HOST_WIDE_INT off
= -1;
550 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
552 if (vro
->opcode
== MEM_REF
)
554 else if (vro
->opcode
!= ADDR_EXPR
)
566 hstate
.add_int (off
);
569 && vro
->opcode
== ADDR_EXPR
)
573 tree op
= TREE_OPERAND (vro
->op0
, 0);
574 hstate
.add_int (TREE_CODE (op
));
575 inchash::add_expr (op
, hstate
);
579 vn_reference_op_compute_hash (vro
, hstate
);
582 result
= hstate
.end ();
583 /* ??? We would ICE later if we hash instead of adding that in. */
585 result
+= SSA_NAME_VERSION (vr1
->vuse
);
590 /* Return true if reference operations VR1 and VR2 are equivalent. This
591 means they have the same set of operands and vuses. */
594 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
598 /* Early out if this is not a hash collision. */
599 if (vr1
->hashcode
!= vr2
->hashcode
)
602 /* The VOP needs to be the same. */
603 if (vr1
->vuse
!= vr2
->vuse
)
606 /* If the operands are the same we are done. */
607 if (vr1
->operands
== vr2
->operands
)
610 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
613 if (INTEGRAL_TYPE_P (vr1
->type
)
614 && INTEGRAL_TYPE_P (vr2
->type
))
616 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
619 else if (INTEGRAL_TYPE_P (vr1
->type
)
620 && (TYPE_PRECISION (vr1
->type
)
621 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
623 else if (INTEGRAL_TYPE_P (vr2
->type
)
624 && (TYPE_PRECISION (vr2
->type
)
625 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
632 HOST_WIDE_INT off1
= 0, off2
= 0;
633 vn_reference_op_t vro1
, vro2
;
634 vn_reference_op_s tem1
, tem2
;
635 bool deref1
= false, deref2
= false;
636 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
638 if (vro1
->opcode
== MEM_REF
)
644 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
646 if (vro2
->opcode
== MEM_REF
)
654 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
656 memset (&tem1
, 0, sizeof (tem1
));
657 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
658 tem1
.type
= TREE_TYPE (tem1
.op0
);
659 tem1
.opcode
= TREE_CODE (tem1
.op0
);
663 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
665 memset (&tem2
, 0, sizeof (tem2
));
666 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
667 tem2
.type
= TREE_TYPE (tem2
.op0
);
668 tem2
.opcode
= TREE_CODE (tem2
.op0
);
672 if (deref1
!= deref2
)
674 if (!vn_reference_op_eq (vro1
, vro2
))
679 while (vr1
->operands
.length () != i
680 || vr2
->operands
.length () != j
);
685 /* Copy the operations present in load/store REF into RESULT, a vector of
686 vn_reference_op_s's. */
689 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
691 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
693 vn_reference_op_s temp
;
697 memset (&temp
, 0, sizeof (temp
));
698 temp
.type
= TREE_TYPE (ref
);
699 temp
.opcode
= TREE_CODE (ref
);
700 temp
.op0
= TMR_INDEX (ref
);
701 temp
.op1
= TMR_STEP (ref
);
702 temp
.op2
= TMR_OFFSET (ref
);
704 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
705 temp
.base
= MR_DEPENDENCE_BASE (ref
);
706 result
->quick_push (temp
);
708 memset (&temp
, 0, sizeof (temp
));
709 temp
.type
= NULL_TREE
;
710 temp
.opcode
= ERROR_MARK
;
711 temp
.op0
= TMR_INDEX2 (ref
);
713 result
->quick_push (temp
);
715 memset (&temp
, 0, sizeof (temp
));
716 temp
.type
= NULL_TREE
;
717 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
718 temp
.op0
= TMR_BASE (ref
);
720 result
->quick_push (temp
);
724 /* For non-calls, store the information that makes up the address. */
728 vn_reference_op_s temp
;
730 memset (&temp
, 0, sizeof (temp
));
731 temp
.type
= TREE_TYPE (ref
);
732 temp
.opcode
= TREE_CODE (ref
);
738 temp
.op0
= TREE_OPERAND (ref
, 1);
741 temp
.op0
= TREE_OPERAND (ref
, 1);
745 /* The base address gets its own vn_reference_op_s structure. */
746 temp
.op0
= TREE_OPERAND (ref
, 1);
747 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 1)))
748 temp
.off
= tree_to_shwi (TREE_OPERAND (ref
, 1));
749 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
750 temp
.base
= MR_DEPENDENCE_BASE (ref
);
753 /* Record bits and position. */
754 temp
.op0
= TREE_OPERAND (ref
, 1);
755 temp
.op1
= TREE_OPERAND (ref
, 2);
756 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 2)))
758 HOST_WIDE_INT off
= tree_to_shwi (TREE_OPERAND (ref
, 2));
759 if (off
% BITS_PER_UNIT
== 0)
760 temp
.off
= off
/ BITS_PER_UNIT
;
764 /* The field decl is enough to unambiguously specify the field,
765 a matching type is not necessary and a mismatching type
766 is always a spurious difference. */
767 temp
.type
= NULL_TREE
;
768 temp
.op0
= TREE_OPERAND (ref
, 1);
769 temp
.op1
= TREE_OPERAND (ref
, 2);
771 tree this_offset
= component_ref_field_offset (ref
);
773 && TREE_CODE (this_offset
) == INTEGER_CST
)
775 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
776 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
779 = (wi::to_offset (this_offset
)
780 + wi::lrshift (wi::to_offset (bit_offset
),
781 LOG2_BITS_PER_UNIT
));
782 if (wi::fits_shwi_p (off
)
783 /* Probibit value-numbering zero offset components
784 of addresses the same before the pass folding
785 __builtin_object_size had a chance to run
786 (checking cfun->after_inlining does the
788 && (TREE_CODE (orig
) != ADDR_EXPR
790 || cfun
->after_inlining
))
791 temp
.off
= off
.to_shwi ();
796 case ARRAY_RANGE_REF
:
798 /* Record index as operand. */
799 temp
.op0
= TREE_OPERAND (ref
, 1);
800 /* Always record lower bounds and element size. */
801 temp
.op1
= array_ref_low_bound (ref
);
802 temp
.op2
= array_ref_element_size (ref
);
803 if (TREE_CODE (temp
.op0
) == INTEGER_CST
804 && TREE_CODE (temp
.op1
) == INTEGER_CST
805 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
807 offset_int off
= ((wi::to_offset (temp
.op0
)
808 - wi::to_offset (temp
.op1
))
809 * wi::to_offset (temp
.op2
));
810 if (wi::fits_shwi_p (off
))
811 temp
.off
= off
.to_shwi();
815 if (DECL_HARD_REGISTER (ref
))
824 /* Canonicalize decls to MEM[&decl] which is what we end up with
825 when valueizing MEM[ptr] with ptr = &decl. */
826 temp
.opcode
= MEM_REF
;
827 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
829 result
->safe_push (temp
);
830 temp
.opcode
= ADDR_EXPR
;
831 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
832 temp
.type
= TREE_TYPE (temp
.op0
);
846 if (is_gimple_min_invariant (ref
))
852 /* These are only interesting for their operands, their
853 existence, and their type. They will never be the last
854 ref in the chain of references (IE they require an
855 operand), so we don't have to put anything
856 for op* as it will be handled by the iteration */
858 case VIEW_CONVERT_EXPR
:
862 /* This is only interesting for its constant offset. */
863 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
868 result
->safe_push (temp
);
870 if (REFERENCE_CLASS_P (ref
)
871 || TREE_CODE (ref
) == MODIFY_EXPR
872 || TREE_CODE (ref
) == WITH_SIZE_EXPR
873 || (TREE_CODE (ref
) == ADDR_EXPR
874 && !is_gimple_min_invariant (ref
)))
875 ref
= TREE_OPERAND (ref
, 0);
881 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
882 operands in *OPS, the reference alias set SET and the reference type TYPE.
883 Return true if something useful was produced. */
886 ao_ref_init_from_vn_reference (ao_ref
*ref
,
887 alias_set_type set
, tree type
,
888 vec
<vn_reference_op_s
> ops
)
890 vn_reference_op_t op
;
892 tree base
= NULL_TREE
;
894 offset_int offset
= 0;
896 offset_int size
= -1;
897 tree size_tree
= NULL_TREE
;
898 alias_set_type base_alias_set
= -1;
900 /* First get the final access size from just the outermost expression. */
902 if (op
->opcode
== COMPONENT_REF
)
903 size_tree
= DECL_SIZE (op
->op0
);
904 else if (op
->opcode
== BIT_FIELD_REF
)
908 machine_mode mode
= TYPE_MODE (type
);
910 size_tree
= TYPE_SIZE (type
);
912 size
= int (GET_MODE_BITSIZE (mode
));
914 if (size_tree
!= NULL_TREE
915 && TREE_CODE (size_tree
) == INTEGER_CST
)
916 size
= wi::to_offset (size_tree
);
918 /* Initially, maxsize is the same as the accessed element size.
919 In the following it will only grow (or become -1). */
922 /* Compute cumulative bit-offset for nested component-refs and array-refs,
923 and find the ultimate containing object. */
924 FOR_EACH_VEC_ELT (ops
, i
, op
)
928 /* These may be in the reference ops, but we cannot do anything
929 sensible with them here. */
931 /* Apart from ADDR_EXPR arguments to MEM_REF. */
932 if (base
!= NULL_TREE
933 && TREE_CODE (base
) == MEM_REF
935 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
937 vn_reference_op_t pop
= &ops
[i
-1];
938 base
= TREE_OPERAND (op
->op0
, 0);
945 offset
+= pop
->off
* BITS_PER_UNIT
;
953 /* Record the base objects. */
955 base_alias_set
= get_deref_alias_set (op
->op0
);
956 *op0_p
= build2 (MEM_REF
, op
->type
,
958 MR_DEPENDENCE_CLIQUE (*op0_p
) = op
->clique
;
959 MR_DEPENDENCE_BASE (*op0_p
) = op
->base
;
960 op0_p
= &TREE_OPERAND (*op0_p
, 0);
971 /* And now the usual component-reference style ops. */
973 offset
+= wi::to_offset (op
->op1
);
978 tree field
= op
->op0
;
979 /* We do not have a complete COMPONENT_REF tree here so we
980 cannot use component_ref_field_offset. Do the interesting
982 tree this_offset
= DECL_FIELD_OFFSET (field
);
984 if (op
->op1
|| TREE_CODE (this_offset
) != INTEGER_CST
)
988 offset_int woffset
= wi::lshift (wi::to_offset (this_offset
),
990 woffset
+= wi::to_offset (DECL_FIELD_BIT_OFFSET (field
));
996 case ARRAY_RANGE_REF
:
998 /* We recorded the lower bound and the element size. */
999 if (TREE_CODE (op
->op0
) != INTEGER_CST
1000 || TREE_CODE (op
->op1
) != INTEGER_CST
1001 || TREE_CODE (op
->op2
) != INTEGER_CST
)
1006 = wi::sext (wi::to_offset (op
->op0
) - wi::to_offset (op
->op1
),
1007 TYPE_PRECISION (TREE_TYPE (op
->op0
)));
1008 woffset
*= wi::to_offset (op
->op2
);
1009 woffset
= wi::lshift (woffset
, LOG2_BITS_PER_UNIT
);
1021 case VIEW_CONVERT_EXPR
:
1038 if (base
== NULL_TREE
)
1041 ref
->ref
= NULL_TREE
;
1043 ref
->ref_alias_set
= set
;
1044 if (base_alias_set
!= -1)
1045 ref
->base_alias_set
= base_alias_set
;
1047 ref
->base_alias_set
= get_alias_set (base
);
1048 /* We discount volatiles from value-numbering elsewhere. */
1049 ref
->volatile_p
= false;
1051 if (!wi::fits_shwi_p (size
) || wi::neg_p (size
))
1059 ref
->size
= size
.to_shwi ();
1061 if (!wi::fits_shwi_p (offset
))
1068 ref
->offset
= offset
.to_shwi ();
1070 if (!wi::fits_shwi_p (max_size
) || wi::neg_p (max_size
))
1073 ref
->max_size
= max_size
.to_shwi ();
1078 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1079 vn_reference_op_s's. */
1082 copy_reference_ops_from_call (gcall
*call
,
1083 vec
<vn_reference_op_s
> *result
)
1085 vn_reference_op_s temp
;
1087 tree lhs
= gimple_call_lhs (call
);
1090 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1091 different. By adding the lhs here in the vector, we ensure that the
1092 hashcode is different, guaranteeing a different value number. */
1093 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1095 memset (&temp
, 0, sizeof (temp
));
1096 temp
.opcode
= MODIFY_EXPR
;
1097 temp
.type
= TREE_TYPE (lhs
);
1100 result
->safe_push (temp
);
1103 /* Copy the type, opcode, function, static chain and EH region, if any. */
1104 memset (&temp
, 0, sizeof (temp
));
1105 temp
.type
= gimple_call_return_type (call
);
1106 temp
.opcode
= CALL_EXPR
;
1107 temp
.op0
= gimple_call_fn (call
);
1108 temp
.op1
= gimple_call_chain (call
);
1109 if (stmt_could_throw_p (call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1110 temp
.op2
= size_int (lr
);
1112 if (gimple_call_with_bounds_p (call
))
1113 temp
.with_bounds
= 1;
1114 result
->safe_push (temp
);
1116 /* Copy the call arguments. As they can be references as well,
1117 just chain them together. */
1118 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1120 tree callarg
= gimple_call_arg (call
, i
);
1121 copy_reference_ops_from_ref (callarg
, result
);
1125 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1126 *I_P to point to the last element of the replacement. */
1128 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1131 unsigned int i
= *i_p
;
1132 vn_reference_op_t op
= &(*ops
)[i
];
1133 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1135 HOST_WIDE_INT addr_offset
= 0;
1137 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1138 from .foo.bar to the preceding MEM_REF offset and replace the
1139 address with &OBJ. */
1140 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1142 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1143 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1145 offset_int off
= offset_int::from (mem_op
->op0
, SIGNED
);
1147 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1148 op
->op0
= build_fold_addr_expr (addr_base
);
1149 if (tree_fits_shwi_p (mem_op
->op0
))
1150 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1158 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1159 *I_P to point to the last element of the replacement. */
1161 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1164 unsigned int i
= *i_p
;
1165 vn_reference_op_t op
= &(*ops
)[i
];
1166 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1168 enum tree_code code
;
1171 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1172 if (!is_gimple_assign (def_stmt
))
1175 code
= gimple_assign_rhs_code (def_stmt
);
1176 if (code
!= ADDR_EXPR
1177 && code
!= POINTER_PLUS_EXPR
)
1180 off
= offset_int::from (mem_op
->op0
, SIGNED
);
1182 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1183 from .foo.bar to the preceding MEM_REF offset and replace the
1184 address with &OBJ. */
1185 if (code
== ADDR_EXPR
)
1187 tree addr
, addr_base
;
1188 HOST_WIDE_INT addr_offset
;
1190 addr
= gimple_assign_rhs1 (def_stmt
);
1191 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1193 /* If that didn't work because the address isn't invariant propagate
1194 the reference tree from the address operation in case the current
1195 dereference isn't offsetted. */
1197 && *i_p
== ops
->length () - 1
1199 /* This makes us disable this transform for PRE where the
1200 reference ops might be also used for code insertion which
1202 && default_vn_walk_kind
== VN_WALKREWRITE
)
1204 auto_vec
<vn_reference_op_s
, 32> tem
;
1205 copy_reference_ops_from_ref (TREE_OPERAND (addr
, 0), &tem
);
1208 ops
->safe_splice (tem
);
1213 || TREE_CODE (addr_base
) != MEM_REF
)
1217 off
+= mem_ref_offset (addr_base
);
1218 op
->op0
= TREE_OPERAND (addr_base
, 0);
1223 ptr
= gimple_assign_rhs1 (def_stmt
);
1224 ptroff
= gimple_assign_rhs2 (def_stmt
);
1225 if (TREE_CODE (ptr
) != SSA_NAME
1226 || TREE_CODE (ptroff
) != INTEGER_CST
)
1229 off
+= wi::to_offset (ptroff
);
1233 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1234 if (tree_fits_shwi_p (mem_op
->op0
))
1235 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1238 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1239 op
->op0
= SSA_VAL (op
->op0
);
1240 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1241 op
->opcode
= TREE_CODE (op
->op0
);
1244 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1245 vn_reference_maybe_forwprop_address (ops
, i_p
);
1246 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1247 vn_reference_fold_indirect (ops
, i_p
);
1251 /* Optimize the reference REF to a constant if possible or return
1252 NULL_TREE if not. */
1255 fully_constant_vn_reference_p (vn_reference_t ref
)
1257 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1258 vn_reference_op_t op
;
1260 /* Try to simplify the translated expression if it is
1261 a call to a builtin function with at most two arguments. */
1263 if (op
->opcode
== CALL_EXPR
1264 && TREE_CODE (op
->op0
) == ADDR_EXPR
1265 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1266 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1267 && operands
.length () >= 2
1268 && operands
.length () <= 3)
1270 vn_reference_op_t arg0
, arg1
= NULL
;
1271 bool anyconst
= false;
1272 arg0
= &operands
[1];
1273 if (operands
.length () > 2)
1274 arg1
= &operands
[2];
1275 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1276 || (arg0
->opcode
== ADDR_EXPR
1277 && is_gimple_min_invariant (arg0
->op0
)))
1280 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1281 || (arg1
->opcode
== ADDR_EXPR
1282 && is_gimple_min_invariant (arg1
->op0
))))
1286 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1289 arg1
? arg1
->op0
: NULL
);
1291 && TREE_CODE (folded
) == NOP_EXPR
)
1292 folded
= TREE_OPERAND (folded
, 0);
1294 && is_gimple_min_invariant (folded
))
1299 /* Simplify reads from constants or constant initializers. */
1300 else if (BITS_PER_UNIT
== 8
1301 && is_gimple_reg_type (ref
->type
)
1302 && (!INTEGRAL_TYPE_P (ref
->type
)
1303 || TYPE_PRECISION (ref
->type
) % BITS_PER_UNIT
== 0))
1305 HOST_WIDE_INT off
= 0;
1307 if (INTEGRAL_TYPE_P (ref
->type
))
1308 size
= TYPE_PRECISION (ref
->type
);
1310 size
= tree_to_shwi (TYPE_SIZE (ref
->type
));
1311 if (size
% BITS_PER_UNIT
!= 0
1312 || size
> MAX_BITSIZE_MODE_ANY_MODE
)
1314 size
/= BITS_PER_UNIT
;
1316 for (i
= 0; i
< operands
.length (); ++i
)
1318 if (operands
[i
].off
== -1)
1320 off
+= operands
[i
].off
;
1321 if (operands
[i
].opcode
== MEM_REF
)
1327 vn_reference_op_t base
= &operands
[--i
];
1328 tree ctor
= error_mark_node
;
1329 tree decl
= NULL_TREE
;
1330 if (TREE_CODE_CLASS (base
->opcode
) == tcc_constant
)
1332 else if (base
->opcode
== MEM_REF
1333 && base
[1].opcode
== ADDR_EXPR
1334 && (TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == VAR_DECL
1335 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == CONST_DECL
))
1337 decl
= TREE_OPERAND (base
[1].op0
, 0);
1338 ctor
= ctor_for_folding (decl
);
1340 if (ctor
== NULL_TREE
)
1341 return build_zero_cst (ref
->type
);
1342 else if (ctor
!= error_mark_node
)
1346 tree res
= fold_ctor_reference (ref
->type
, ctor
,
1347 off
* BITS_PER_UNIT
,
1348 size
* BITS_PER_UNIT
, decl
);
1351 STRIP_USELESS_TYPE_CONVERSION (res
);
1352 if (is_gimple_min_invariant (res
))
1358 unsigned char buf
[MAX_BITSIZE_MODE_ANY_MODE
/ BITS_PER_UNIT
];
1359 if (native_encode_expr (ctor
, buf
, size
, off
) > 0)
1360 return native_interpret_expr (ref
->type
, buf
, size
);
1368 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1369 structures into their value numbers. This is done in-place, and
1370 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1371 whether any operands were valueized. */
1373 static vec
<vn_reference_op_s
>
1374 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1376 vn_reference_op_t vro
;
1379 *valueized_anything
= false;
1381 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1383 if (vro
->opcode
== SSA_NAME
1384 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1386 tree tem
= SSA_VAL (vro
->op0
);
1387 if (tem
!= vro
->op0
)
1389 *valueized_anything
= true;
1392 /* If it transforms from an SSA_NAME to a constant, update
1394 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1395 vro
->opcode
= TREE_CODE (vro
->op0
);
1397 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1399 tree tem
= SSA_VAL (vro
->op1
);
1400 if (tem
!= vro
->op1
)
1402 *valueized_anything
= true;
1406 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1408 tree tem
= SSA_VAL (vro
->op2
);
1409 if (tem
!= vro
->op2
)
1411 *valueized_anything
= true;
1415 /* If it transforms from an SSA_NAME to an address, fold with
1416 a preceding indirect reference. */
1419 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1420 && orig
[i
- 1].opcode
== MEM_REF
)
1422 if (vn_reference_fold_indirect (&orig
, &i
))
1423 *valueized_anything
= true;
1426 && vro
->opcode
== SSA_NAME
1427 && orig
[i
- 1].opcode
== MEM_REF
)
1429 if (vn_reference_maybe_forwprop_address (&orig
, &i
))
1430 *valueized_anything
= true;
1432 /* If it transforms a non-constant ARRAY_REF into a constant
1433 one, adjust the constant offset. */
1434 else if (vro
->opcode
== ARRAY_REF
1436 && TREE_CODE (vro
->op0
) == INTEGER_CST
1437 && TREE_CODE (vro
->op1
) == INTEGER_CST
1438 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1440 offset_int off
= ((wi::to_offset (vro
->op0
)
1441 - wi::to_offset (vro
->op1
))
1442 * wi::to_offset (vro
->op2
));
1443 if (wi::fits_shwi_p (off
))
1444 vro
->off
= off
.to_shwi ();
1451 static vec
<vn_reference_op_s
>
1452 valueize_refs (vec
<vn_reference_op_s
> orig
)
1455 return valueize_refs_1 (orig
, &tem
);
1458 static vec
<vn_reference_op_s
> shared_lookup_references
;
1460 /* Create a vector of vn_reference_op_s structures from REF, a
1461 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1462 this function. *VALUEIZED_ANYTHING will specify whether any
1463 operands were valueized. */
1465 static vec
<vn_reference_op_s
>
1466 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1470 shared_lookup_references
.truncate (0);
1471 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1472 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1473 valueized_anything
);
1474 return shared_lookup_references
;
1477 /* Create a vector of vn_reference_op_s structures from CALL, a
1478 call statement. The vector is shared among all callers of
1481 static vec
<vn_reference_op_s
>
1482 valueize_shared_reference_ops_from_call (gcall
*call
)
1486 shared_lookup_references
.truncate (0);
1487 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1488 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1489 return shared_lookup_references
;
1492 /* Lookup a SCCVN reference operation VR in the current hash table.
1493 Returns the resulting value number if it exists in the hash table,
1494 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1495 vn_reference_t stored in the hashtable if something is found. */
1498 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1500 vn_reference_s
**slot
;
1503 hash
= vr
->hashcode
;
1504 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1505 if (!slot
&& current_info
== optimistic_info
)
1506 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1510 *vnresult
= (vn_reference_t
)*slot
;
1511 return ((vn_reference_t
)*slot
)->result
;
1517 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1518 with the current VUSE and performs the expression lookup. */
1521 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1522 unsigned int cnt
, void *vr_
)
1524 vn_reference_t vr
= (vn_reference_t
)vr_
;
1525 vn_reference_s
**slot
;
1528 /* This bounds the stmt walks we perform on reference lookups
1529 to O(1) instead of O(N) where N is the number of dominating
1531 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1535 *last_vuse_ptr
= vuse
;
1537 /* Fixup vuse and hash. */
1539 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1540 vr
->vuse
= vuse_ssa_val (vuse
);
1542 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1544 hash
= vr
->hashcode
;
1545 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1546 if (!slot
&& current_info
== optimistic_info
)
1547 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1554 /* Lookup an existing or insert a new vn_reference entry into the
1555 value table for the VUSE, SET, TYPE, OPERANDS reference which
1556 has the value VALUE which is either a constant or an SSA name. */
1558 static vn_reference_t
1559 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1562 vec
<vn_reference_op_s
,
1567 vn_reference_t result
;
1570 vr1
.operands
= operands
;
1573 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1574 if (vn_reference_lookup_1 (&vr1
, &result
))
1576 if (TREE_CODE (value
) == SSA_NAME
)
1577 value_id
= VN_INFO (value
)->value_id
;
1579 value_id
= get_or_alloc_constant_value_id (value
);
1580 return vn_reference_insert_pieces (vuse
, set
, type
,
1581 operands
.copy (), value
, value_id
);
1584 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1585 from the statement defining VUSE and if not successful tries to
1586 translate *REFP and VR_ through an aggregate copy at the definition
1587 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
1588 of *REF and *VR. If only disambiguation was performed then
1589 *DISAMBIGUATE_ONLY is set to true. */
1592 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
,
1593 bool *disambiguate_only
)
1595 vn_reference_t vr
= (vn_reference_t
)vr_
;
1596 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1597 tree base
= ao_ref_base (ref
);
1598 HOST_WIDE_INT offset
, maxsize
;
1599 static vec
<vn_reference_op_s
>
1602 bool lhs_ref_ok
= false;
1604 /* If the reference is based on a parameter that was determined as
1605 pointing to readonly memory it doesn't change. */
1606 if (TREE_CODE (base
) == MEM_REF
1607 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
1608 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base
, 0))
1609 && bitmap_bit_p (const_parms
,
1610 SSA_NAME_VERSION (TREE_OPERAND (base
, 0))))
1612 *disambiguate_only
= true;
1616 /* First try to disambiguate after value-replacing in the definitions LHS. */
1617 if (is_gimple_assign (def_stmt
))
1619 tree lhs
= gimple_assign_lhs (def_stmt
);
1620 bool valueized_anything
= false;
1621 /* Avoid re-allocation overhead. */
1622 lhs_ops
.truncate (0);
1623 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1624 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1625 if (valueized_anything
)
1627 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1628 get_alias_set (lhs
),
1629 TREE_TYPE (lhs
), lhs_ops
);
1631 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1633 *disambiguate_only
= true;
1639 ao_ref_init (&lhs_ref
, lhs
);
1643 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
1644 && gimple_call_num_args (def_stmt
) <= 4)
1646 /* For builtin calls valueize its arguments and call the
1647 alias oracle again. Valueization may improve points-to
1648 info of pointers and constify size and position arguments.
1649 Originally this was motivated by PR61034 which has
1650 conditional calls to free falsely clobbering ref because
1651 of imprecise points-to info of the argument. */
1653 bool valueized_anything
= false;
1654 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1656 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
1657 if (TREE_CODE (oldargs
[i
]) == SSA_NAME
1658 && VN_INFO (oldargs
[i
])->valnum
!= oldargs
[i
])
1660 gimple_call_set_arg (def_stmt
, i
, VN_INFO (oldargs
[i
])->valnum
);
1661 valueized_anything
= true;
1664 if (valueized_anything
)
1666 bool res
= call_may_clobber_ref_p_1 (as_a
<gcall
*> (def_stmt
),
1668 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1669 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
1672 *disambiguate_only
= true;
1678 if (*disambiguate_only
)
1681 offset
= ref
->offset
;
1682 maxsize
= ref
->max_size
;
1684 /* If we cannot constrain the size of the reference we cannot
1685 test if anything kills it. */
1689 /* We can't deduce anything useful from clobbers. */
1690 if (gimple_clobber_p (def_stmt
))
1693 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1694 from that definition.
1696 if (is_gimple_reg_type (vr
->type
)
1697 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1698 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1699 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1700 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1702 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1704 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1705 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1706 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1707 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1708 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1710 && operand_equal_p (base
, base2
, 0)
1711 && offset2
<= offset
1712 && offset2
+ size2
>= offset
+ maxsize
)
1714 tree val
= build_zero_cst (vr
->type
);
1715 return vn_reference_lookup_or_insert_for_pieces
1716 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1720 /* 2) Assignment from an empty CONSTRUCTOR. */
1721 else if (is_gimple_reg_type (vr
->type
)
1722 && gimple_assign_single_p (def_stmt
)
1723 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1724 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1727 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1728 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1729 &offset2
, &size2
, &maxsize2
);
1731 && operand_equal_p (base
, base2
, 0)
1732 && offset2
<= offset
1733 && offset2
+ size2
>= offset
+ maxsize
)
1735 tree val
= build_zero_cst (vr
->type
);
1736 return vn_reference_lookup_or_insert_for_pieces
1737 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1741 /* 3) Assignment from a constant. We can use folds native encode/interpret
1742 routines to extract the assigned bits. */
1743 else if (vn_walk_kind
== VN_WALKREWRITE
1744 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1745 && ref
->size
== maxsize
1746 && maxsize
% BITS_PER_UNIT
== 0
1747 && offset
% BITS_PER_UNIT
== 0
1748 && is_gimple_reg_type (vr
->type
)
1749 && gimple_assign_single_p (def_stmt
)
1750 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1753 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1754 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1755 &offset2
, &size2
, &maxsize2
);
1757 && maxsize2
== size2
1758 && size2
% BITS_PER_UNIT
== 0
1759 && offset2
% BITS_PER_UNIT
== 0
1760 && operand_equal_p (base
, base2
, 0)
1761 && offset2
<= offset
1762 && offset2
+ size2
>= offset
+ maxsize
)
1764 /* We support up to 512-bit values (for V8DFmode). */
1765 unsigned char buffer
[64];
1768 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1769 buffer
, sizeof (buffer
));
1772 tree val
= native_interpret_expr (vr
->type
,
1774 + ((offset
- offset2
)
1776 ref
->size
/ BITS_PER_UNIT
);
1778 return vn_reference_lookup_or_insert_for_pieces
1779 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1784 /* 4) Assignment from an SSA name which definition we may be able
1785 to access pieces from. */
1786 else if (ref
->size
== maxsize
1787 && is_gimple_reg_type (vr
->type
)
1788 && gimple_assign_single_p (def_stmt
)
1789 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1791 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1792 gimple
*def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1793 if (is_gimple_assign (def_stmt2
)
1794 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1795 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1796 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1799 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1800 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1801 &offset2
, &size2
, &maxsize2
);
1802 off
= offset
- offset2
;
1804 && maxsize2
== size2
1805 && operand_equal_p (base
, base2
, 0)
1806 && offset2
<= offset
1807 && offset2
+ size2
>= offset
+ maxsize
)
1809 tree val
= NULL_TREE
;
1811 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1812 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1815 val
= gimple_assign_rhs1 (def_stmt2
);
1816 else if (off
== elsz
)
1817 val
= gimple_assign_rhs2 (def_stmt2
);
1819 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1822 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1823 unsigned i
= off
/ elsz
;
1824 if (i
< CONSTRUCTOR_NELTS (ctor
))
1826 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1827 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1829 if (TREE_CODE (TREE_TYPE (elt
->value
))
1836 return vn_reference_lookup_or_insert_for_pieces
1837 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1842 /* 5) For aggregate copies translate the reference through them if
1843 the copy kills ref. */
1844 else if (vn_walk_kind
== VN_WALKREWRITE
1845 && gimple_assign_single_p (def_stmt
)
1846 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1847 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1848 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1851 HOST_WIDE_INT maxsize2
;
1853 auto_vec
<vn_reference_op_s
> rhs
;
1854 vn_reference_op_t vro
;
1860 /* See if the assignment kills REF. */
1861 base2
= ao_ref_base (&lhs_ref
);
1862 maxsize2
= lhs_ref
.max_size
;
1865 && (TREE_CODE (base
) != MEM_REF
1866 || TREE_CODE (base2
) != MEM_REF
1867 || TREE_OPERAND (base
, 0) != TREE_OPERAND (base2
, 0)
1868 || !tree_int_cst_equal (TREE_OPERAND (base
, 1),
1869 TREE_OPERAND (base2
, 1))))
1870 || !stmt_kills_ref_p (def_stmt
, ref
))
1873 /* Find the common base of ref and the lhs. lhs_ops already
1874 contains valueized operands for the lhs. */
1875 i
= vr
->operands
.length () - 1;
1876 j
= lhs_ops
.length () - 1;
1877 while (j
>= 0 && i
>= 0
1878 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1884 /* ??? The innermost op should always be a MEM_REF and we already
1885 checked that the assignment to the lhs kills vr. Thus for
1886 aggregate copies using char[] types the vn_reference_op_eq
1887 may fail when comparing types for compatibility. But we really
1888 don't care here - further lookups with the rewritten operands
1889 will simply fail if we messed up types too badly. */
1890 HOST_WIDE_INT extra_off
= 0;
1891 if (j
== 0 && i
>= 0
1892 && lhs_ops
[0].opcode
== MEM_REF
1893 && lhs_ops
[0].off
!= -1)
1895 if (lhs_ops
[0].off
== vr
->operands
[i
].off
)
1897 else if (vr
->operands
[i
].opcode
== MEM_REF
1898 && vr
->operands
[i
].off
!= -1)
1900 extra_off
= vr
->operands
[i
].off
- lhs_ops
[0].off
;
1905 /* i now points to the first additional op.
1906 ??? LHS may not be completely contained in VR, one or more
1907 VIEW_CONVERT_EXPRs could be in its way. We could at least
1908 try handling outermost VIEW_CONVERT_EXPRs. */
1912 /* Now re-write REF to be based on the rhs of the assignment. */
1913 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1915 /* Apply an extra offset to the inner MEM_REF of the RHS. */
1918 if (rhs
.length () < 2
1919 || rhs
[0].opcode
!= MEM_REF
1920 || rhs
[0].off
== -1)
1922 rhs
[0].off
+= extra_off
;
1923 rhs
[0].op0
= int_const_binop (PLUS_EXPR
, rhs
[0].op0
,
1924 build_int_cst (TREE_TYPE (rhs
[0].op0
),
1928 /* We need to pre-pend vr->operands[0..i] to rhs. */
1929 vec
<vn_reference_op_s
> old
= vr
->operands
;
1930 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1932 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1933 if (old
== shared_lookup_references
)
1934 shared_lookup_references
= vr
->operands
;
1937 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1938 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1939 vr
->operands
[i
+ 1 + j
] = *vro
;
1940 vr
->operands
= valueize_refs (vr
->operands
);
1941 if (old
== shared_lookup_references
)
1942 shared_lookup_references
= vr
->operands
;
1943 vr
->hashcode
= vn_reference_compute_hash (vr
);
1945 /* Try folding the new reference to a constant. */
1946 tree val
= fully_constant_vn_reference_p (vr
);
1948 return vn_reference_lookup_or_insert_for_pieces
1949 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1951 /* Adjust *ref from the new operands. */
1952 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1954 /* This can happen with bitfields. */
1955 if (ref
->size
!= r
.size
)
1959 /* Do not update last seen VUSE after translating. */
1960 last_vuse_ptr
= NULL
;
1962 /* Keep looking for the adjusted *REF / VR pair. */
1966 /* 6) For memcpy copies translate the reference through them if
1967 the copy kills ref. */
1968 else if (vn_walk_kind
== VN_WALKREWRITE
1969 && is_gimple_reg_type (vr
->type
)
1970 /* ??? Handle BCOPY as well. */
1971 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1972 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1973 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1974 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1975 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1976 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1977 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1978 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
1982 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1983 vn_reference_op_s op
;
1987 /* Only handle non-variable, addressable refs. */
1988 if (ref
->size
!= maxsize
1989 || offset
% BITS_PER_UNIT
!= 0
1990 || ref
->size
% BITS_PER_UNIT
!= 0)
1993 /* Extract a pointer base and an offset for the destination. */
1994 lhs
= gimple_call_arg (def_stmt
, 0);
1996 if (TREE_CODE (lhs
) == SSA_NAME
)
1998 lhs
= SSA_VAL (lhs
);
1999 if (TREE_CODE (lhs
) == SSA_NAME
)
2001 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
2002 if (gimple_assign_single_p (def_stmt
)
2003 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2004 lhs
= gimple_assign_rhs1 (def_stmt
);
2007 if (TREE_CODE (lhs
) == ADDR_EXPR
)
2009 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
2013 if (TREE_CODE (tem
) == MEM_REF
2014 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
2016 lhs
= TREE_OPERAND (tem
, 0);
2017 if (TREE_CODE (lhs
) == SSA_NAME
)
2018 lhs
= SSA_VAL (lhs
);
2019 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
2021 else if (DECL_P (tem
))
2022 lhs
= build_fold_addr_expr (tem
);
2026 if (TREE_CODE (lhs
) != SSA_NAME
2027 && TREE_CODE (lhs
) != ADDR_EXPR
)
2030 /* Extract a pointer base and an offset for the source. */
2031 rhs
= gimple_call_arg (def_stmt
, 1);
2033 if (TREE_CODE (rhs
) == SSA_NAME
)
2034 rhs
= SSA_VAL (rhs
);
2035 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2037 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
2041 if (TREE_CODE (tem
) == MEM_REF
2042 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
2044 rhs
= TREE_OPERAND (tem
, 0);
2045 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
2047 else if (DECL_P (tem
))
2048 rhs
= build_fold_addr_expr (tem
);
2052 if (TREE_CODE (rhs
) != SSA_NAME
2053 && TREE_CODE (rhs
) != ADDR_EXPR
)
2056 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
2058 /* The bases of the destination and the references have to agree. */
2059 if ((TREE_CODE (base
) != MEM_REF
2061 || (TREE_CODE (base
) == MEM_REF
2062 && (TREE_OPERAND (base
, 0) != lhs
2063 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
2065 && (TREE_CODE (lhs
) != ADDR_EXPR
2066 || TREE_OPERAND (lhs
, 0) != base
)))
2069 at
= offset
/ BITS_PER_UNIT
;
2070 if (TREE_CODE (base
) == MEM_REF
)
2071 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
2072 /* If the access is completely outside of the memcpy destination
2073 area there is no aliasing. */
2074 if (lhs_offset
>= at
+ maxsize
/ BITS_PER_UNIT
2075 || lhs_offset
+ copy_size
<= at
)
2077 /* And the access has to be contained within the memcpy destination. */
2079 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
2082 /* Make room for 2 operands in the new reference. */
2083 if (vr
->operands
.length () < 2)
2085 vec
<vn_reference_op_s
> old
= vr
->operands
;
2086 vr
->operands
.safe_grow_cleared (2);
2087 if (old
== shared_lookup_references
2088 && vr
->operands
!= old
)
2089 shared_lookup_references
= vr
->operands
;
2092 vr
->operands
.truncate (2);
2094 /* The looked-through reference is a simple MEM_REF. */
2095 memset (&op
, 0, sizeof (op
));
2097 op
.opcode
= MEM_REF
;
2098 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
2099 op
.off
= at
- lhs_offset
+ rhs_offset
;
2100 vr
->operands
[0] = op
;
2101 op
.type
= TREE_TYPE (rhs
);
2102 op
.opcode
= TREE_CODE (rhs
);
2105 vr
->operands
[1] = op
;
2106 vr
->hashcode
= vn_reference_compute_hash (vr
);
2108 /* Adjust *ref from the new operands. */
2109 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2111 /* This can happen with bitfields. */
2112 if (ref
->size
!= r
.size
)
2116 /* Do not update last seen VUSE after translating. */
2117 last_vuse_ptr
= NULL
;
2119 /* Keep looking for the adjusted *REF / VR pair. */
2123 /* Bail out and stop walking. */
2127 /* Lookup a reference operation by it's parts, in the current hash table.
2128 Returns the resulting value number if it exists in the hash table,
2129 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2130 vn_reference_t stored in the hashtable if something is found. */
2133 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2134 vec
<vn_reference_op_s
> operands
,
2135 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2137 struct vn_reference_s vr1
;
2145 vr1
.vuse
= vuse_ssa_val (vuse
);
2146 shared_lookup_references
.truncate (0);
2147 shared_lookup_references
.safe_grow (operands
.length ());
2148 memcpy (shared_lookup_references
.address (),
2149 operands
.address (),
2150 sizeof (vn_reference_op_s
)
2151 * operands
.length ());
2152 vr1
.operands
= operands
= shared_lookup_references
2153 = valueize_refs (shared_lookup_references
);
2156 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2157 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2160 vn_reference_lookup_1 (&vr1
, vnresult
);
2162 && kind
!= VN_NOWALK
2166 vn_walk_kind
= kind
;
2167 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2169 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2170 vn_reference_lookup_2
,
2171 vn_reference_lookup_3
,
2172 vuse_ssa_val
, &vr1
);
2173 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2177 return (*vnresult
)->result
;
2182 /* Lookup OP in the current hash table, and return the resulting value
2183 number if it exists in the hash table. Return NULL_TREE if it does
2184 not exist in the hash table or if the result field of the structure
2185 was NULL.. VNRESULT will be filled in with the vn_reference_t
2186 stored in the hashtable if one exists. */
2189 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2190 vn_reference_t
*vnresult
)
2192 vec
<vn_reference_op_s
> operands
;
2193 struct vn_reference_s vr1
;
2195 bool valuezied_anything
;
2200 vr1
.vuse
= vuse_ssa_val (vuse
);
2201 vr1
.operands
= operands
2202 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2203 vr1
.type
= TREE_TYPE (op
);
2204 vr1
.set
= get_alias_set (op
);
2205 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2206 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2209 if (kind
!= VN_NOWALK
2212 vn_reference_t wvnresult
;
2214 /* Make sure to use a valueized reference if we valueized anything.
2215 Otherwise preserve the full reference for advanced TBAA. */
2216 if (!valuezied_anything
2217 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2219 ao_ref_init (&r
, op
);
2220 vn_walk_kind
= kind
;
2222 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2223 vn_reference_lookup_2
,
2224 vn_reference_lookup_3
,
2225 vuse_ssa_val
, &vr1
);
2226 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2230 *vnresult
= wvnresult
;
2231 return wvnresult
->result
;
2237 return vn_reference_lookup_1 (&vr1
, vnresult
);
2240 /* Lookup CALL in the current hash table and return the entry in
2241 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2244 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
2250 tree vuse
= gimple_vuse (call
);
2252 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2253 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
2254 vr
->type
= gimple_expr_type (call
);
2256 vr
->hashcode
= vn_reference_compute_hash (vr
);
2257 vn_reference_lookup_1 (vr
, vnresult
);
2260 /* Insert OP into the current hash table with a value number of
2261 RESULT, and return the resulting reference structure we created. */
2263 static vn_reference_t
2264 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2266 vn_reference_s
**slot
;
2270 vr1
= current_info
->references_pool
->allocate ();
2271 if (TREE_CODE (result
) == SSA_NAME
)
2272 vr1
->value_id
= VN_INFO (result
)->value_id
;
2274 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2275 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2276 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2277 vr1
->type
= TREE_TYPE (op
);
2278 vr1
->set
= get_alias_set (op
);
2279 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2280 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2281 vr1
->result_vdef
= vdef
;
2283 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2286 /* Because we lookup stores using vuses, and value number failures
2287 using the vdefs (see visit_reference_op_store for how and why),
2288 it's possible that on failure we may try to insert an already
2289 inserted store. This is not wrong, there is no ssa name for a
2290 store that we could use as a differentiator anyway. Thus, unlike
2291 the other lookup functions, you cannot gcc_assert (!*slot)
2294 /* But free the old slot in case of a collision. */
2296 free_reference (*slot
);
2302 /* Insert a reference by it's pieces into the current hash table with
2303 a value number of RESULT. Return the resulting reference
2304 structure we created. */
2307 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2308 vec
<vn_reference_op_s
> operands
,
2309 tree result
, unsigned int value_id
)
2312 vn_reference_s
**slot
;
2315 vr1
= current_info
->references_pool
->allocate ();
2316 vr1
->value_id
= value_id
;
2317 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2318 vr1
->operands
= valueize_refs (operands
);
2321 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2322 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2323 result
= SSA_VAL (result
);
2324 vr1
->result
= result
;
2326 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2329 /* At this point we should have all the things inserted that we have
2330 seen before, and we should never try inserting something that
2332 gcc_assert (!*slot
);
2334 free_reference (*slot
);
2340 /* Compute and return the hash value for nary operation VBO1. */
2343 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2345 inchash::hash hstate
;
2348 for (i
= 0; i
< vno1
->length
; ++i
)
2349 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2350 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2352 if (((vno1
->length
== 2
2353 && commutative_tree_code (vno1
->opcode
))
2354 || (vno1
->length
== 3
2355 && commutative_ternary_tree_code (vno1
->opcode
)))
2356 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2357 std::swap (vno1
->op
[0], vno1
->op
[1]);
2358 else if (TREE_CODE_CLASS (vno1
->opcode
) == tcc_comparison
2359 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2361 std::swap (vno1
->op
[0], vno1
->op
[1]);
2362 vno1
->opcode
= swap_tree_comparison (vno1
->opcode
);
2365 hstate
.add_int (vno1
->opcode
);
2366 for (i
= 0; i
< vno1
->length
; ++i
)
2367 inchash::add_expr (vno1
->op
[i
], hstate
);
2369 return hstate
.end ();
2372 /* Compare nary operations VNO1 and VNO2 and return true if they are
2376 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2380 if (vno1
->hashcode
!= vno2
->hashcode
)
2383 if (vno1
->length
!= vno2
->length
)
2386 if (vno1
->opcode
!= vno2
->opcode
2387 || !types_compatible_p (vno1
->type
, vno2
->type
))
2390 for (i
= 0; i
< vno1
->length
; ++i
)
2391 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2397 /* Initialize VNO from the pieces provided. */
2400 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2401 enum tree_code code
, tree type
, tree
*ops
)
2404 vno
->length
= length
;
2406 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2409 /* Initialize VNO from OP. */
2412 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2416 vno
->opcode
= TREE_CODE (op
);
2417 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2418 vno
->type
= TREE_TYPE (op
);
2419 for (i
= 0; i
< vno
->length
; ++i
)
2420 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2423 /* Return the number of operands for a vn_nary ops structure from STMT. */
2426 vn_nary_length_from_stmt (gimple
*stmt
)
2428 switch (gimple_assign_rhs_code (stmt
))
2432 case VIEW_CONVERT_EXPR
:
2439 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2442 return gimple_num_ops (stmt
) - 1;
2446 /* Initialize VNO from STMT. */
2449 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple
*stmt
)
2453 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2454 vno
->type
= gimple_expr_type (stmt
);
2455 switch (vno
->opcode
)
2459 case VIEW_CONVERT_EXPR
:
2461 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2466 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2467 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2468 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2472 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2473 for (i
= 0; i
< vno
->length
; ++i
)
2474 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2478 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2479 vno
->length
= gimple_num_ops (stmt
) - 1;
2480 for (i
= 0; i
< vno
->length
; ++i
)
2481 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2485 /* Compute the hashcode for VNO and look for it in the hash table;
2486 return the resulting value number if it exists in the hash table.
2487 Return NULL_TREE if it does not exist in the hash table or if the
2488 result field of the operation is NULL. VNRESULT will contain the
2489 vn_nary_op_t from the hashtable if it exists. */
2492 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2494 vn_nary_op_s
**slot
;
2499 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2500 slot
= current_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2502 if (!slot
&& current_info
== optimistic_info
)
2503 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2509 return (*slot
)->result
;
2512 /* Lookup a n-ary operation by its pieces and return the resulting value
2513 number if it exists in the hash table. Return NULL_TREE if it does
2514 not exist in the hash table or if the result field of the operation
2515 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2519 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2520 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2522 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2523 sizeof_vn_nary_op (length
));
2524 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2525 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2528 /* Lookup OP in the current hash table, and return the resulting value
2529 number if it exists in the hash table. Return NULL_TREE if it does
2530 not exist in the hash table or if the result field of the operation
2531 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2535 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2538 = XALLOCAVAR (struct vn_nary_op_s
,
2539 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2540 init_vn_nary_op_from_op (vno1
, op
);
2541 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2544 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2545 value number if it exists in the hash table. Return NULL_TREE if
2546 it does not exist in the hash table. VNRESULT will contain the
2547 vn_nary_op_t from the hashtable if it exists. */
2550 vn_nary_op_lookup_stmt (gimple
*stmt
, vn_nary_op_t
*vnresult
)
2553 = XALLOCAVAR (struct vn_nary_op_s
,
2554 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2555 init_vn_nary_op_from_stmt (vno1
, stmt
);
2556 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2559 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
2562 vn_lookup_simplify_result (code_helper rcode
, tree type
, tree
*ops
)
2564 if (!rcode
.is_tree_code ())
2566 vn_nary_op_t vnresult
= NULL
;
2567 return vn_nary_op_lookup_pieces (TREE_CODE_LENGTH ((tree_code
) rcode
),
2568 (tree_code
) rcode
, type
, ops
, &vnresult
);
2571 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2574 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2576 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2579 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2583 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2585 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2586 ¤t_info
->nary_obstack
);
2588 vno1
->value_id
= value_id
;
2589 vno1
->length
= length
;
2590 vno1
->result
= result
;
2595 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2596 VNO->HASHCODE first. */
2599 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
2602 vn_nary_op_s
**slot
;
2605 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2607 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2608 gcc_assert (!*slot
);
2614 /* Insert a n-ary operation into the current hash table using it's
2615 pieces. Return the vn_nary_op_t structure we created and put in
2619 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2620 tree type
, tree
*ops
,
2621 tree result
, unsigned int value_id
)
2623 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2624 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2625 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2628 /* Insert OP into the current hash table with a value number of
2629 RESULT. Return the vn_nary_op_t structure we created and put in
2633 vn_nary_op_insert (tree op
, tree result
)
2635 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2638 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2639 init_vn_nary_op_from_op (vno1
, op
);
2640 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2643 /* Insert the rhs of STMT into the current hash table with a value number of
2647 vn_nary_op_insert_stmt (gimple
*stmt
, tree result
)
2650 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2651 result
, VN_INFO (result
)->value_id
);
2652 init_vn_nary_op_from_stmt (vno1
, stmt
);
2653 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2656 /* Compute a hashcode for PHI operation VP1 and return it. */
2658 static inline hashval_t
2659 vn_phi_compute_hash (vn_phi_t vp1
)
2661 inchash::hash
hstate (vp1
->phiargs
.length () > 2
2662 ? vp1
->block
->index
: vp1
->phiargs
.length ());
2668 /* If all PHI arguments are constants we need to distinguish
2669 the PHI node via its type. */
2671 hstate
.merge_hash (vn_hash_type (type
));
2673 FOR_EACH_EDGE (e
, ei
, vp1
->block
->preds
)
2675 /* Don't hash backedge values they need to be handled as VN_TOP
2676 for optimistic value-numbering. */
2677 if (e
->flags
& EDGE_DFS_BACK
)
2680 phi1op
= vp1
->phiargs
[e
->dest_idx
];
2681 if (phi1op
== VN_TOP
)
2683 inchash::add_expr (phi1op
, hstate
);
2686 return hstate
.end ();
2690 /* Return true if COND1 and COND2 represent the same condition, set
2691 *INVERTED_P if one needs to be inverted to make it the same as
2695 cond_stmts_equal_p (gcond
*cond1
, gcond
*cond2
, bool *inverted_p
)
2697 enum tree_code code1
= gimple_cond_code (cond1
);
2698 enum tree_code code2
= gimple_cond_code (cond2
);
2699 tree lhs1
= gimple_cond_lhs (cond1
);
2700 tree lhs2
= gimple_cond_lhs (cond2
);
2701 tree rhs1
= gimple_cond_rhs (cond1
);
2702 tree rhs2
= gimple_cond_rhs (cond2
);
2704 *inverted_p
= false;
2707 else if (code1
== swap_tree_comparison (code2
))
2708 std::swap (lhs2
, rhs2
);
2709 else if (code1
== invert_tree_comparison (code2
, HONOR_NANS (lhs2
)))
2711 else if (code1
== invert_tree_comparison
2712 (swap_tree_comparison (code2
), HONOR_NANS (lhs2
)))
2714 std::swap (lhs2
, rhs2
);
2720 if (! expressions_equal_p (vn_valueize (lhs1
), vn_valueize (lhs2
))
2721 || ! expressions_equal_p (vn_valueize (rhs1
), vn_valueize (rhs2
)))
2727 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2730 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2732 if (vp1
->hashcode
!= vp2
->hashcode
)
2735 if (vp1
->block
!= vp2
->block
)
2737 if (vp1
->phiargs
.length () != vp2
->phiargs
.length ())
2740 switch (vp1
->phiargs
.length ())
2743 /* Single-arg PHIs are just copies. */
2748 /* Rule out backedges into the PHI. */
2749 if (vp1
->block
->loop_father
->header
== vp1
->block
2750 || vp2
->block
->loop_father
->header
== vp2
->block
)
2753 /* If the PHI nodes do not have compatible types
2754 they are not the same. */
2755 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2759 = get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
2761 = get_immediate_dominator (CDI_DOMINATORS
, vp2
->block
);
2762 /* If the immediate dominator end in switch stmts multiple
2763 values may end up in the same PHI arg via intermediate
2765 if (EDGE_COUNT (idom1
->succs
) != 2
2766 || EDGE_COUNT (idom2
->succs
) != 2)
2769 /* Verify the controlling stmt is the same. */
2770 gimple
*last1
= last_stmt (idom1
);
2771 gimple
*last2
= last_stmt (idom2
);
2772 if (gimple_code (last1
) != GIMPLE_COND
2773 || gimple_code (last2
) != GIMPLE_COND
)
2776 if (! cond_stmts_equal_p (as_a
<gcond
*> (last1
),
2777 as_a
<gcond
*> (last2
), &inverted_p
))
2780 /* Get at true/false controlled edges into the PHI. */
2781 edge te1
, te2
, fe1
, fe2
;
2782 if (! extract_true_false_controlled_edges (idom1
, vp1
->block
,
2784 || ! extract_true_false_controlled_edges (idom2
, vp2
->block
,
2788 /* Swap edges if the second condition is the inverted of the
2791 std::swap (te2
, fe2
);
2793 /* ??? Handle VN_TOP specially. */
2794 if (! expressions_equal_p (vp1
->phiargs
[te1
->dest_idx
],
2795 vp2
->phiargs
[te2
->dest_idx
])
2796 || ! expressions_equal_p (vp1
->phiargs
[fe1
->dest_idx
],
2797 vp2
->phiargs
[fe2
->dest_idx
]))
2808 /* If the PHI nodes do not have compatible types
2809 they are not the same. */
2810 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2813 /* Any phi in the same block will have it's arguments in the
2814 same edge order, because of how we store phi nodes. */
2817 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2819 tree phi2op
= vp2
->phiargs
[i
];
2820 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2822 if (!expressions_equal_p (phi1op
, phi2op
))
2829 static vec
<tree
> shared_lookup_phiargs
;
2831 /* Lookup PHI in the current hash table, and return the resulting
2832 value number if it exists in the hash table. Return NULL_TREE if
2833 it does not exist in the hash table. */
2836 vn_phi_lookup (gimple
*phi
)
2839 struct vn_phi_s vp1
;
2843 shared_lookup_phiargs
.truncate (0);
2844 shared_lookup_phiargs
.safe_grow (gimple_phi_num_args (phi
));
2846 /* Canonicalize the SSA_NAME's to their value number. */
2847 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2849 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
2850 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2851 shared_lookup_phiargs
[e
->dest_idx
] = def
;
2853 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2854 vp1
.phiargs
= shared_lookup_phiargs
;
2855 vp1
.block
= gimple_bb (phi
);
2856 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2857 slot
= current_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2859 if (!slot
&& current_info
== optimistic_info
)
2860 slot
= valid_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2864 return (*slot
)->result
;
2867 /* Insert PHI into the current hash table with a value number of
2871 vn_phi_insert (gimple
*phi
, tree result
)
2874 vn_phi_t vp1
= current_info
->phis_pool
->allocate ();
2875 vec
<tree
> args
= vNULL
;
2879 args
.safe_grow (gimple_phi_num_args (phi
));
2881 /* Canonicalize the SSA_NAME's to their value number. */
2882 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2884 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
2885 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2886 args
[e
->dest_idx
] = def
;
2888 vp1
->value_id
= VN_INFO (result
)->value_id
;
2889 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2890 vp1
->phiargs
= args
;
2891 vp1
->block
= gimple_bb (phi
);
2892 vp1
->result
= result
;
2893 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2895 slot
= current_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2897 /* Because we iterate over phi operations more than once, it's
2898 possible the slot might already exist here, hence no assert.*/
2904 /* Print set of components in strongly connected component SCC to OUT. */
2907 print_scc (FILE *out
, vec
<tree
> scc
)
2912 fprintf (out
, "SCC consists of:");
2913 FOR_EACH_VEC_ELT (scc
, i
, var
)
2916 print_generic_expr (out
, var
, 0);
2918 fprintf (out
, "\n");
2921 /* Set the value number of FROM to TO, return true if it has changed
2925 set_ssa_val_to (tree from
, tree to
)
2927 tree currval
= SSA_VAL (from
);
2928 HOST_WIDE_INT toff
, coff
;
2930 /* The only thing we allow as value numbers are ssa_names
2931 and invariants. So assert that here. We don't allow VN_TOP
2932 as visiting a stmt should produce a value-number other than
2934 ??? Still VN_TOP can happen for unreachable code, so force
2935 it to varying in that case. Not all code is prepared to
2936 get VN_TOP on valueization. */
2939 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2940 fprintf (dump_file
, "Forcing value number to varying on "
2941 "receiving VN_TOP\n");
2945 gcc_assert (to
!= NULL_TREE
2946 && ((TREE_CODE (to
) == SSA_NAME
2947 && (to
== from
|| SSA_VAL (to
) == to
))
2948 || is_gimple_min_invariant (to
)));
2952 if (currval
== from
)
2954 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2956 fprintf (dump_file
, "Not changing value number of ");
2957 print_generic_expr (dump_file
, from
, 0);
2958 fprintf (dump_file
, " from VARYING to ");
2959 print_generic_expr (dump_file
, to
, 0);
2960 fprintf (dump_file
, "\n");
2964 else if (TREE_CODE (to
) == SSA_NAME
2965 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2971 fprintf (dump_file
, "Setting value number of ");
2972 print_generic_expr (dump_file
, from
, 0);
2973 fprintf (dump_file
, " to ");
2974 print_generic_expr (dump_file
, to
, 0);
2978 && !operand_equal_p (currval
, to
, 0)
2979 /* ??? For addresses involving volatile objects or types operand_equal_p
2980 does not reliably detect ADDR_EXPRs as equal. We know we are only
2981 getting invariant gimple addresses here, so can use
2982 get_addr_base_and_unit_offset to do this comparison. */
2983 && !(TREE_CODE (currval
) == ADDR_EXPR
2984 && TREE_CODE (to
) == ADDR_EXPR
2985 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2986 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2989 VN_INFO (from
)->valnum
= to
;
2990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2991 fprintf (dump_file
, " (changed)\n");
2994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2995 fprintf (dump_file
, "\n");
2999 /* Mark as processed all the definitions in the defining stmt of USE, or
3003 mark_use_processed (tree use
)
3007 gimple
*stmt
= SSA_NAME_DEF_STMT (use
);
3009 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
3011 VN_INFO (use
)->use_processed
= true;
3015 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
3017 tree def
= DEF_FROM_PTR (defp
);
3019 VN_INFO (def
)->use_processed
= true;
3023 /* Set all definitions in STMT to value number to themselves.
3024 Return true if a value number changed. */
3027 defs_to_varying (gimple
*stmt
)
3029 bool changed
= false;
3033 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
3035 tree def
= DEF_FROM_PTR (defp
);
3036 changed
|= set_ssa_val_to (def
, def
);
3041 /* Visit a copy between LHS and RHS, return true if the value number
3045 visit_copy (tree lhs
, tree rhs
)
3048 rhs
= SSA_VAL (rhs
);
3050 return set_ssa_val_to (lhs
, rhs
);
3053 /* Visit a nary operator RHS, value number it, and return true if the
3054 value number of LHS has changed as a result. */
3057 visit_nary_op (tree lhs
, gimple
*stmt
)
3059 bool changed
= false;
3060 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
3063 changed
= set_ssa_val_to (lhs
, result
);
3066 changed
= set_ssa_val_to (lhs
, lhs
);
3067 vn_nary_op_insert_stmt (stmt
, lhs
);
3073 /* Visit a call STMT storing into LHS. Return true if the value number
3074 of the LHS has changed as a result. */
3077 visit_reference_op_call (tree lhs
, gcall
*stmt
)
3079 bool changed
= false;
3080 struct vn_reference_s vr1
;
3081 vn_reference_t vnresult
= NULL
;
3082 tree vdef
= gimple_vdef (stmt
);
3084 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
3085 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
3088 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
3091 if (vnresult
->result_vdef
&& vdef
)
3092 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3094 if (!vnresult
->result
&& lhs
)
3095 vnresult
->result
= lhs
;
3097 if (vnresult
->result
&& lhs
)
3098 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
3103 vn_reference_s
**slot
;
3105 changed
|= set_ssa_val_to (vdef
, vdef
);
3107 changed
|= set_ssa_val_to (lhs
, lhs
);
3108 vr2
= current_info
->references_pool
->allocate ();
3109 vr2
->vuse
= vr1
.vuse
;
3110 /* As we are not walking the virtual operand chain we know the
3111 shared_lookup_references are still original so we can re-use
3113 vr2
->operands
= vr1
.operands
.copy ();
3114 vr2
->type
= vr1
.type
;
3116 vr2
->hashcode
= vr1
.hashcode
;
3118 vr2
->result_vdef
= vdef
;
3119 slot
= current_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
3121 gcc_assert (!*slot
);
3128 /* Visit a load from a reference operator RHS, part of STMT, value number it,
3129 and return true if the value number of the LHS has changed as a result. */
3132 visit_reference_op_load (tree lhs
, tree op
, gimple
*stmt
)
3134 bool changed
= false;
3138 last_vuse
= gimple_vuse (stmt
);
3139 last_vuse_ptr
= &last_vuse
;
3140 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
3141 default_vn_walk_kind
, NULL
);
3142 last_vuse_ptr
= NULL
;
3144 /* We handle type-punning through unions by value-numbering based
3145 on offset and size of the access. Be prepared to handle a
3146 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
3148 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
3150 /* We will be setting the value number of lhs to the value number
3151 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
3152 So first simplify and lookup this expression to see if it
3153 is already available. */
3154 mprts_hook
= vn_lookup_simplify_result
;
3155 code_helper rcode
= VIEW_CONVERT_EXPR
;
3156 tree ops
[3] = { result
};
3157 bool res
= gimple_resimplify1 (NULL
, &rcode
, TREE_TYPE (op
), ops
,
3160 gimple
*new_stmt
= NULL
;
3162 && gimple_simplified_result_is_gimple_val (rcode
, ops
))
3163 /* The expression is already available. */
3167 tree val
= vn_lookup_simplify_result (rcode
, TREE_TYPE (op
), ops
);
3170 gimple_seq stmts
= NULL
;
3171 result
= maybe_push_res_to_seq (rcode
, TREE_TYPE (op
), ops
,
3173 gcc_assert (result
&& gimple_seq_singleton_p (stmts
));
3174 new_stmt
= gimple_seq_first_stmt (stmts
);
3177 /* The expression is already available. */
3182 /* The expression is not yet available, value-number lhs to
3183 the new SSA_NAME we created. */
3184 /* Initialize value-number information properly. */
3185 VN_INFO_GET (result
)->valnum
= result
;
3186 VN_INFO (result
)->value_id
= get_next_value_id ();
3187 gimple_seq_add_stmt_without_update (&VN_INFO (result
)->expr
,
3189 VN_INFO (result
)->needs_insertion
= true;
3190 /* As all "inserted" statements are singleton SCCs, insert
3191 to the valid table. This is strictly needed to
3192 avoid re-generating new value SSA_NAMEs for the same
3193 expression during SCC iteration over and over (the
3194 optimistic table gets cleared after each iteration).
3195 We do not need to insert into the optimistic table, as
3196 lookups there will fall back to the valid table. */
3197 if (current_info
== optimistic_info
)
3199 current_info
= valid_info
;
3200 vn_nary_op_insert_stmt (new_stmt
, result
);
3201 current_info
= optimistic_info
;
3204 vn_nary_op_insert_stmt (new_stmt
, result
);
3205 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3207 fprintf (dump_file
, "Inserting name ");
3208 print_generic_expr (dump_file
, result
, 0);
3209 fprintf (dump_file
, " for expression ");
3210 print_gimple_expr (dump_file
, new_stmt
, 0, TDF_SLIM
);
3211 fprintf (dump_file
, "\n");
3217 changed
= set_ssa_val_to (lhs
, result
);
3220 changed
= set_ssa_val_to (lhs
, lhs
);
3221 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
3228 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3229 and return true if the value number of the LHS has changed as a result. */
3232 visit_reference_op_store (tree lhs
, tree op
, gimple
*stmt
)
3234 bool changed
= false;
3235 vn_reference_t vnresult
= NULL
;
3236 tree result
, assign
;
3237 bool resultsame
= false;
3238 tree vuse
= gimple_vuse (stmt
);
3239 tree vdef
= gimple_vdef (stmt
);
3241 if (TREE_CODE (op
) == SSA_NAME
)
3244 /* First we want to lookup using the *vuses* from the store and see
3245 if there the last store to this location with the same address
3248 The vuses represent the memory state before the store. If the
3249 memory state, address, and value of the store is the same as the
3250 last store to this location, then this store will produce the
3251 same memory state as that store.
3253 In this case the vdef versions for this store are value numbered to those
3254 vuse versions, since they represent the same memory state after
3257 Otherwise, the vdefs for the store are used when inserting into
3258 the table, since the store generates a new memory state. */
3260 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
3264 if (TREE_CODE (result
) == SSA_NAME
)
3265 result
= SSA_VAL (result
);
3266 resultsame
= expressions_equal_p (result
, op
);
3269 if ((!result
|| !resultsame
)
3270 /* Only perform the following when being called from PRE
3271 which embeds tail merging. */
3272 && default_vn_walk_kind
== VN_WALK
)
3274 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3275 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
3278 VN_INFO (vdef
)->use_processed
= true;
3279 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3283 if (!result
|| !resultsame
)
3285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3287 fprintf (dump_file
, "No store match\n");
3288 fprintf (dump_file
, "Value numbering store ");
3289 print_generic_expr (dump_file
, lhs
, 0);
3290 fprintf (dump_file
, " to ");
3291 print_generic_expr (dump_file
, op
, 0);
3292 fprintf (dump_file
, "\n");
3294 /* Have to set value numbers before insert, since insert is
3295 going to valueize the references in-place. */
3298 changed
|= set_ssa_val_to (vdef
, vdef
);
3301 /* Do not insert structure copies into the tables. */
3302 if (is_gimple_min_invariant (op
)
3303 || is_gimple_reg (op
))
3304 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3306 /* Only perform the following when being called from PRE
3307 which embeds tail merging. */
3308 if (default_vn_walk_kind
== VN_WALK
)
3310 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3311 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3316 /* We had a match, so value number the vdef to have the value
3317 number of the vuse it came from. */
3319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3320 fprintf (dump_file
, "Store matched earlier value,"
3321 "value numbering store vdefs to matching vuses.\n");
3323 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3329 /* Visit and value number PHI, return true if the value number
3333 visit_phi (gimple
*phi
)
3335 bool changed
= false;
3337 tree sameval
= VN_TOP
;
3338 bool allsame
= true;
3340 /* TODO: We could check for this in init_sccvn, and replace this
3341 with a gcc_assert. */
3342 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3343 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3345 /* See if all non-TOP arguments have the same value. TOP is
3346 equivalent to everything, so we can ignore it. */
3349 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3350 if (e
->flags
& EDGE_EXECUTABLE
)
3352 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3354 if (TREE_CODE (def
) == SSA_NAME
)
3355 def
= SSA_VAL (def
);
3358 if (sameval
== VN_TOP
)
3360 else if (!expressions_equal_p (def
, sameval
))
3367 /* If none of the edges was executable or all incoming values are
3368 undefined keep the value-number at VN_TOP. */
3369 if (sameval
== VN_TOP
)
3370 return set_ssa_val_to (PHI_RESULT (phi
), VN_TOP
);
3372 /* First see if it is equivalent to a phi node in this block. We prefer
3373 this as it allows IV elimination - see PRs 66502 and 67167. */
3374 result
= vn_phi_lookup (phi
);
3376 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3377 /* Otherwise all value numbered to the same value, the phi node has that
3380 changed
= set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3383 vn_phi_insert (phi
, PHI_RESULT (phi
));
3384 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3390 /* Try to simplify RHS using equivalences and constant folding. */
3393 try_to_simplify (gassign
*stmt
)
3395 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3398 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3399 in this case, there is no point in doing extra work. */
3400 if (code
== SSA_NAME
)
3403 /* First try constant folding based on our current lattice. */
3404 mprts_hook
= vn_lookup_simplify_result
;
3405 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
, vn_valueize
);
3408 && (TREE_CODE (tem
) == SSA_NAME
3409 || is_gimple_min_invariant (tem
)))
3415 /* Visit and value number USE, return true if the value number
3419 visit_use (tree use
)
3421 bool changed
= false;
3422 gimple
*stmt
= SSA_NAME_DEF_STMT (use
);
3424 mark_use_processed (use
);
3426 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3427 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3428 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3430 fprintf (dump_file
, "Value numbering ");
3431 print_generic_expr (dump_file
, use
, 0);
3432 fprintf (dump_file
, " stmt = ");
3433 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3436 /* Handle uninitialized uses. */
3437 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3438 changed
= set_ssa_val_to (use
, use
);
3439 else if (gimple_code (stmt
) == GIMPLE_PHI
)
3440 changed
= visit_phi (stmt
);
3441 else if (gimple_has_volatile_ops (stmt
))
3442 changed
= defs_to_varying (stmt
);
3443 else if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
3445 enum tree_code code
= gimple_assign_rhs_code (ass
);
3446 tree lhs
= gimple_assign_lhs (ass
);
3447 tree rhs1
= gimple_assign_rhs1 (ass
);
3450 /* Shortcut for copies. Simplifying copies is pointless,
3451 since we copy the expression and value they represent. */
3452 if (code
== SSA_NAME
3453 && TREE_CODE (lhs
) == SSA_NAME
)
3455 changed
= visit_copy (lhs
, rhs1
);
3458 simplified
= try_to_simplify (ass
);
3461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3463 fprintf (dump_file
, "RHS ");
3464 print_gimple_expr (dump_file
, ass
, 0, 0);
3465 fprintf (dump_file
, " simplified to ");
3466 print_generic_expr (dump_file
, simplified
, 0);
3467 fprintf (dump_file
, "\n");
3470 /* Setting value numbers to constants will occasionally
3471 screw up phi congruence because constants are not
3472 uniquely associated with a single ssa name that can be
3475 && is_gimple_min_invariant (simplified
)
3476 && TREE_CODE (lhs
) == SSA_NAME
)
3478 changed
= set_ssa_val_to (lhs
, simplified
);
3482 && TREE_CODE (simplified
) == SSA_NAME
3483 && TREE_CODE (lhs
) == SSA_NAME
)
3485 changed
= visit_copy (lhs
, simplified
);
3489 if ((TREE_CODE (lhs
) == SSA_NAME
3490 /* We can substitute SSA_NAMEs that are live over
3491 abnormal edges with their constant value. */
3492 && !(gimple_assign_copy_p (ass
)
3493 && is_gimple_min_invariant (rhs1
))
3495 && is_gimple_min_invariant (simplified
))
3496 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3497 /* Stores or copies from SSA_NAMEs that are live over
3498 abnormal edges are a problem. */
3499 || (code
== SSA_NAME
3500 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3501 changed
= defs_to_varying (ass
);
3502 else if (REFERENCE_CLASS_P (lhs
)
3504 changed
= visit_reference_op_store (lhs
, rhs1
, ass
);
3505 else if (TREE_CODE (lhs
) == SSA_NAME
)
3507 if ((gimple_assign_copy_p (ass
)
3508 && is_gimple_min_invariant (rhs1
))
3510 && is_gimple_min_invariant (simplified
)))
3513 changed
= set_ssa_val_to (lhs
, simplified
);
3515 changed
= set_ssa_val_to (lhs
, rhs1
);
3519 /* Visit the original statement. */
3520 switch (vn_get_stmt_kind (ass
))
3523 changed
= visit_nary_op (lhs
, ass
);
3526 changed
= visit_reference_op_load (lhs
, rhs1
, ass
);
3529 changed
= defs_to_varying (ass
);
3535 changed
= defs_to_varying (ass
);
3537 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
3539 tree lhs
= gimple_call_lhs (call_stmt
);
3540 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3542 /* Try constant folding based on our current lattice. */
3543 tree simplified
= gimple_fold_stmt_to_constant_1 (call_stmt
,
3547 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3549 fprintf (dump_file
, "call ");
3550 print_gimple_expr (dump_file
, call_stmt
, 0, 0);
3551 fprintf (dump_file
, " simplified to ");
3552 print_generic_expr (dump_file
, simplified
, 0);
3553 fprintf (dump_file
, "\n");
3556 /* Setting value numbers to constants will occasionally
3557 screw up phi congruence because constants are not
3558 uniquely associated with a single ssa name that can be
3561 && is_gimple_min_invariant (simplified
))
3563 changed
= set_ssa_val_to (lhs
, simplified
);
3564 if (gimple_vdef (call_stmt
))
3565 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
3566 SSA_VAL (gimple_vuse (call_stmt
)));
3570 && TREE_CODE (simplified
) == SSA_NAME
)
3572 changed
= visit_copy (lhs
, simplified
);
3573 if (gimple_vdef (call_stmt
))
3574 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
3575 SSA_VAL (gimple_vuse (call_stmt
)));
3578 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3580 changed
= defs_to_varying (call_stmt
);
3585 if (!gimple_call_internal_p (call_stmt
)
3586 && (/* Calls to the same function with the same vuse
3587 and the same operands do not necessarily return the same
3588 value, unless they're pure or const. */
3589 gimple_call_flags (call_stmt
) & (ECF_PURE
| ECF_CONST
)
3590 /* If calls have a vdef, subsequent calls won't have
3591 the same incoming vuse. So, if 2 calls with vdef have the
3592 same vuse, we know they're not subsequent.
3593 We can value number 2 calls to the same function with the
3594 same vuse and the same operands which are not subsequent
3595 the same, because there is no code in the program that can
3596 compare the 2 values... */
3597 || (gimple_vdef (call_stmt
)
3598 /* ... unless the call returns a pointer which does
3599 not alias with anything else. In which case the
3600 information that the values are distinct are encoded
3602 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
3603 /* Only perform the following when being called from PRE
3604 which embeds tail merging. */
3605 && default_vn_walk_kind
== VN_WALK
)))
3606 changed
= visit_reference_op_call (lhs
, call_stmt
);
3608 changed
= defs_to_varying (call_stmt
);
3611 changed
= defs_to_varying (stmt
);
3616 /* Compare two operands by reverse postorder index */
3619 compare_ops (const void *pa
, const void *pb
)
3621 const tree opa
= *((const tree
*)pa
);
3622 const tree opb
= *((const tree
*)pb
);
3623 gimple
*opstmta
= SSA_NAME_DEF_STMT (opa
);
3624 gimple
*opstmtb
= SSA_NAME_DEF_STMT (opb
);
3628 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3629 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3630 else if (gimple_nop_p (opstmta
))
3632 else if (gimple_nop_p (opstmtb
))
3635 bba
= gimple_bb (opstmta
);
3636 bbb
= gimple_bb (opstmtb
);
3639 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3647 if (gimple_code (opstmta
) == GIMPLE_PHI
3648 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3649 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3650 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3652 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3654 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3655 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3657 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3659 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3662 /* Sort an array containing members of a strongly connected component
3663 SCC so that the members are ordered by RPO number.
3664 This means that when the sort is complete, iterating through the
3665 array will give you the members in RPO order. */
3668 sort_scc (vec
<tree
> scc
)
3670 scc
.qsort (compare_ops
);
3673 /* Insert the no longer used nary ONARY to the hash INFO. */
3676 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3678 size_t size
= sizeof_vn_nary_op (onary
->length
);
3679 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3680 &info
->nary_obstack
);
3681 memcpy (nary
, onary
, size
);
3682 vn_nary_op_insert_into (nary
, info
->nary
, false);
3685 /* Insert the no longer used phi OPHI to the hash INFO. */
3688 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3690 vn_phi_t phi
= info
->phis_pool
->allocate ();
3692 memcpy (phi
, ophi
, sizeof (*phi
));
3693 ophi
->phiargs
.create (0);
3694 slot
= info
->phis
->find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3695 gcc_assert (!*slot
);
3699 /* Insert the no longer used reference OREF to the hash INFO. */
3702 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3705 vn_reference_s
**slot
;
3706 ref
= info
->references_pool
->allocate ();
3707 memcpy (ref
, oref
, sizeof (*ref
));
3708 oref
->operands
.create (0);
3709 slot
= info
->references
->find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3711 free_reference (*slot
);
3715 /* Process a strongly connected component in the SSA graph. */
3718 process_scc (vec
<tree
> scc
)
3722 unsigned int iterations
= 0;
3723 bool changed
= true;
3724 vn_nary_op_iterator_type hin
;
3725 vn_phi_iterator_type hip
;
3726 vn_reference_iterator_type hir
;
3731 /* If the SCC has a single member, just visit it. */
3732 if (scc
.length () == 1)
3735 if (VN_INFO (use
)->use_processed
)
3737 /* We need to make sure it doesn't form a cycle itself, which can
3738 happen for self-referential PHI nodes. In that case we would
3739 end up inserting an expression with VN_TOP operands into the
3740 valid table which makes us derive bogus equivalences later.
3741 The cheapest way to check this is to assume it for all PHI nodes. */
3742 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3743 /* Fallthru to iteration. */ ;
3751 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3752 print_scc (dump_file
, scc
);
3754 /* Iterate over the SCC with the optimistic table until it stops
3756 current_info
= optimistic_info
;
3761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3762 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3763 /* As we are value-numbering optimistically we have to
3764 clear the expression tables and the simplified expressions
3765 in each iteration until we converge. */
3766 optimistic_info
->nary
->empty ();
3767 optimistic_info
->phis
->empty ();
3768 optimistic_info
->references
->empty ();
3769 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3770 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3771 optimistic_info
->phis_pool
->release ();
3772 optimistic_info
->references_pool
->release ();
3773 FOR_EACH_VEC_ELT (scc
, i
, var
)
3774 gcc_assert (!VN_INFO (var
)->needs_insertion
3775 && VN_INFO (var
)->expr
== NULL
);
3776 FOR_EACH_VEC_ELT (scc
, i
, var
)
3777 changed
|= visit_use (var
);
3780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3781 fprintf (dump_file
, "Processing SCC needed %d iterations\n", iterations
);
3782 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3784 /* Finally, copy the contents of the no longer used optimistic
3785 table to the valid table. */
3786 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3787 copy_nary (nary
, valid_info
);
3788 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3789 copy_phi (phi
, valid_info
);
3790 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->references
,
3791 ref
, vn_reference_t
, hir
)
3792 copy_reference (ref
, valid_info
);
3794 current_info
= valid_info
;
3798 /* Pop the components of the found SCC for NAME off the SCC stack
3799 and process them. Returns true if all went well, false if
3800 we run into resource limits. */
3803 extract_and_process_scc_for_name (tree name
)
3808 /* Found an SCC, pop the components off the SCC stack and
3812 x
= sccstack
.pop ();
3814 VN_INFO (x
)->on_sccstack
= false;
3816 } while (x
!= name
);
3818 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3820 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3823 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3824 "SCC size %u exceeding %u\n", scc
.length (),
3825 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3830 if (scc
.length () > 1)
3838 /* Depth first search on NAME to discover and process SCC's in the SSA
3840 Execution of this algorithm relies on the fact that the SCC's are
3841 popped off the stack in topological order.
3842 Returns true if successful, false if we stopped processing SCC's due
3843 to resource constraints. */
3848 vec
<ssa_op_iter
> itervec
= vNULL
;
3849 vec
<tree
> namevec
= vNULL
;
3850 use_operand_p usep
= NULL
;
3857 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3858 VN_INFO (name
)->visited
= true;
3859 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3861 sccstack
.safe_push (name
);
3862 VN_INFO (name
)->on_sccstack
= true;
3863 defstmt
= SSA_NAME_DEF_STMT (name
);
3865 /* Recursively DFS on our operands, looking for SCC's. */
3866 if (!gimple_nop_p (defstmt
))
3868 /* Push a new iterator. */
3869 if (gphi
*phi
= dyn_cast
<gphi
*> (defstmt
))
3870 usep
= op_iter_init_phiuse (&iter
, phi
, SSA_OP_ALL_USES
);
3872 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3875 clear_and_done_ssa_iter (&iter
);
3879 /* If we are done processing uses of a name, go up the stack
3880 of iterators and process SCCs as we found them. */
3881 if (op_iter_done (&iter
))
3883 /* See if we found an SCC. */
3884 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3885 if (!extract_and_process_scc_for_name (name
))
3892 /* Check if we are done. */
3893 if (namevec
.is_empty ())
3900 /* Restore the last use walker and continue walking there. */
3902 name
= namevec
.pop ();
3903 memcpy (&iter
, &itervec
.last (),
3904 sizeof (ssa_op_iter
));
3906 goto continue_walking
;
3909 use
= USE_FROM_PTR (usep
);
3911 /* Since we handle phi nodes, we will sometimes get
3912 invariants in the use expression. */
3913 if (TREE_CODE (use
) == SSA_NAME
)
3915 if (! (VN_INFO (use
)->visited
))
3917 /* Recurse by pushing the current use walking state on
3918 the stack and starting over. */
3919 itervec
.safe_push (iter
);
3920 namevec
.safe_push (name
);
3925 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3926 VN_INFO (use
)->low
);
3928 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3929 && VN_INFO (use
)->on_sccstack
)
3931 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3932 VN_INFO (name
)->low
);
3936 usep
= op_iter_next_use (&iter
);
3940 /* Allocate a value number table. */
3943 allocate_vn_table (vn_tables_t table
)
3945 table
->phis
= new vn_phi_table_type (23);
3946 table
->nary
= new vn_nary_op_table_type (23);
3947 table
->references
= new vn_reference_table_type (23);
3949 gcc_obstack_init (&table
->nary_obstack
);
3950 table
->phis_pool
= new object_allocator
<vn_phi_s
> ("VN phis");
3951 table
->references_pool
= new object_allocator
<vn_reference_s
>
3955 /* Free a value number table. */
3958 free_vn_table (vn_tables_t table
)
3964 delete table
->references
;
3965 table
->references
= NULL
;
3966 obstack_free (&table
->nary_obstack
, NULL
);
3967 delete table
->phis_pool
;
3968 delete table
->references_pool
;
3976 int *rpo_numbers_temp
;
3978 calculate_dominance_info (CDI_DOMINATORS
);
3979 mark_dfs_back_edges ();
3981 sccstack
.create (0);
3982 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
3984 constant_value_ids
= BITMAP_ALLOC (NULL
);
3989 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
3990 /* VEC_alloc doesn't actually grow it to the right size, it just
3991 preallocates the space to do so. */
3992 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
3993 gcc_obstack_init (&vn_ssa_aux_obstack
);
3995 shared_lookup_phiargs
.create (0);
3996 shared_lookup_references
.create (0);
3997 rpo_numbers
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
3999 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
4000 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
4002 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4003 the i'th block in RPO order is bb. We want to map bb's to RPO
4004 numbers, so we need to rearrange this array. */
4005 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
4006 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
4008 XDELETE (rpo_numbers_temp
);
4010 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
4012 renumber_gimple_stmt_uids ();
4014 /* Create the valid and optimistic value numbering tables. */
4015 valid_info
= XCNEW (struct vn_tables_s
);
4016 allocate_vn_table (valid_info
);
4017 optimistic_info
= XCNEW (struct vn_tables_s
);
4018 allocate_vn_table (optimistic_info
);
4019 current_info
= valid_info
;
4021 /* Create the VN_INFO structures, and initialize value numbers to
4022 TOP or VARYING for parameters. */
4023 for (i
= 1; i
< num_ssa_names
; i
++)
4025 tree name
= ssa_name (i
);
4029 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4030 VN_INFO (name
)->needs_insertion
= false;
4031 VN_INFO (name
)->expr
= NULL
;
4032 VN_INFO (name
)->value_id
= 0;
4034 if (!SSA_NAME_IS_DEFAULT_DEF (name
))
4037 switch (TREE_CODE (SSA_NAME_VAR (name
)))
4040 /* Undefined vars keep TOP. */
4044 /* Parameters are VARYING but we can record a condition
4045 if we know it is a non-NULL pointer. */
4046 VN_INFO (name
)->visited
= true;
4047 VN_INFO (name
)->valnum
= name
;
4048 if (POINTER_TYPE_P (TREE_TYPE (name
))
4049 && nonnull_arg_p (SSA_NAME_VAR (name
)))
4053 ops
[1] = build_int_cst (TREE_TYPE (name
), 0);
4054 vn_nary_op_insert_pieces (2, NE_EXPR
, boolean_type_node
, ops
,
4055 boolean_true_node
, 0);
4056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4058 fprintf (dump_file
, "Recording ");
4059 print_generic_expr (dump_file
, name
, TDF_SLIM
);
4060 fprintf (dump_file
, " != 0\n");
4066 /* If the result is passed by invisible reference the default
4067 def is initialized, otherwise it's uninitialized. */
4068 if (DECL_BY_REFERENCE (SSA_NAME_VAR (name
)))
4070 VN_INFO (name
)->visited
= true;
4071 VN_INFO (name
)->valnum
= name
;
4086 delete constant_to_value_id
;
4087 constant_to_value_id
= NULL
;
4088 BITMAP_FREE (constant_value_ids
);
4089 shared_lookup_phiargs
.release ();
4090 shared_lookup_references
.release ();
4091 XDELETEVEC (rpo_numbers
);
4093 for (i
= 0; i
< num_ssa_names
; i
++)
4095 tree name
= ssa_name (i
);
4097 && has_VN_INFO (name
)
4098 && VN_INFO (name
)->needs_insertion
)
4099 release_ssa_name (name
);
4101 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4102 vn_ssa_aux_table
.release ();
4104 sccstack
.release ();
4105 free_vn_table (valid_info
);
4106 XDELETE (valid_info
);
4107 free_vn_table (optimistic_info
);
4108 XDELETE (optimistic_info
);
4110 BITMAP_FREE (const_parms
);
4113 /* Set *ID according to RESULT. */
4116 set_value_id_for_result (tree result
, unsigned int *id
)
4118 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4119 *id
= VN_INFO (result
)->value_id
;
4120 else if (result
&& is_gimple_min_invariant (result
))
4121 *id
= get_or_alloc_constant_value_id (result
);
4123 *id
= get_next_value_id ();
4126 /* Set the value ids in the valid hash tables. */
4129 set_hashtable_value_ids (void)
4131 vn_nary_op_iterator_type hin
;
4132 vn_phi_iterator_type hip
;
4133 vn_reference_iterator_type hir
;
4138 /* Now set the value ids of the things we had put in the hash
4141 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4142 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4144 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4145 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4147 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4149 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4152 class sccvn_dom_walker
: public dom_walker
4156 : dom_walker (CDI_DOMINATORS
), fail (false), cond_stack (vNULL
) {}
4158 virtual void before_dom_children (basic_block
);
4159 virtual void after_dom_children (basic_block
);
4161 void record_cond (basic_block
,
4162 enum tree_code code
, tree lhs
, tree rhs
, bool value
);
4163 void record_conds (basic_block
,
4164 enum tree_code code
, tree lhs
, tree rhs
, bool value
);
4167 vec
<std::pair
<basic_block
, std::pair
<vn_nary_op_t
, vn_nary_op_t
> > >
4171 /* Record a temporary condition for the BB and its dominated blocks. */
4174 sccvn_dom_walker::record_cond (basic_block bb
,
4175 enum tree_code code
, tree lhs
, tree rhs
,
4178 tree ops
[2] = { lhs
, rhs
};
4179 vn_nary_op_t old
= NULL
;
4180 if (vn_nary_op_lookup_pieces (2, code
, boolean_type_node
, ops
, &old
))
4181 current_info
->nary
->remove_elt_with_hash (old
, old
->hashcode
);
4183 = vn_nary_op_insert_pieces (2, code
, boolean_type_node
, ops
,
4186 : boolean_false_node
, 0);
4187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4189 fprintf (dump_file
, "Recording temporarily ");
4190 print_generic_expr (dump_file
, ops
[0], TDF_SLIM
);
4191 fprintf (dump_file
, " %s ", get_tree_code_name (code
));
4192 print_generic_expr (dump_file
, ops
[1], TDF_SLIM
);
4193 fprintf (dump_file
, " == %s%s\n",
4194 value
? "true" : "false",
4195 old
? " (old entry saved)" : "");
4197 cond_stack
.safe_push (std::make_pair (bb
, std::make_pair (cond
, old
)));
4200 /* Record temporary conditions for the BB and its dominated blocks
4201 according to LHS CODE RHS == VALUE and its dominated conditions. */
4204 sccvn_dom_walker::record_conds (basic_block bb
,
4205 enum tree_code code
, tree lhs
, tree rhs
,
4208 /* Record the original condition. */
4209 record_cond (bb
, code
, lhs
, rhs
, value
);
4214 /* Record dominated conditions if the condition is true. Note that
4215 the inversion is already recorded. */
4220 record_cond (bb
, code
== LT_EXPR
? LE_EXPR
: GE_EXPR
, lhs
, rhs
, true);
4221 record_cond (bb
, NE_EXPR
, lhs
, rhs
, true);
4222 record_cond (bb
, EQ_EXPR
, lhs
, rhs
, false);
4226 record_cond (bb
, LE_EXPR
, lhs
, rhs
, true);
4227 record_cond (bb
, GE_EXPR
, lhs
, rhs
, true);
4228 record_cond (bb
, LT_EXPR
, lhs
, rhs
, false);
4229 record_cond (bb
, GT_EXPR
, lhs
, rhs
, false);
4237 /* Restore expressions and values derived from conditionals. */
4240 sccvn_dom_walker::after_dom_children (basic_block bb
)
4242 while (!cond_stack
.is_empty ()
4243 && cond_stack
.last ().first
== bb
)
4245 vn_nary_op_t cond
= cond_stack
.last ().second
.first
;
4246 vn_nary_op_t old
= cond_stack
.last ().second
.second
;
4247 current_info
->nary
->remove_elt_with_hash (cond
, cond
->hashcode
);
4249 vn_nary_op_insert_into (old
, current_info
->nary
, false);
4254 /* Value number all statements in BB. */
4257 sccvn_dom_walker::before_dom_children (basic_block bb
)
4265 /* If any of the predecessor edges that do not come from blocks dominated
4266 by us are still marked as possibly executable consider this block
4268 bool reachable
= bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
);
4269 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4270 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
4271 reachable
|= (e
->flags
& EDGE_EXECUTABLE
);
4273 /* If the block is not reachable all outgoing edges are not
4274 executable. Neither are incoming edges with src dominated by us. */
4277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4278 fprintf (dump_file
, "Marking all outgoing edges of unreachable "
4279 "BB %d as not executable\n", bb
->index
);
4281 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4282 e
->flags
&= ~EDGE_EXECUTABLE
;
4284 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4286 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
4288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4289 fprintf (dump_file
, "Marking backedge from BB %d into "
4290 "unreachable BB %d as not executable\n",
4291 e
->src
->index
, bb
->index
);
4292 e
->flags
&= ~EDGE_EXECUTABLE
;
4298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4299 fprintf (dump_file
, "Visiting BB %d\n", bb
->index
);
4301 /* If we have a single predecessor record the equivalence from a
4302 possible condition on the predecessor edge. */
4303 if (single_pred_p (bb
))
4305 edge e
= single_pred_edge (bb
);
4306 /* Check if there are multiple executable successor edges in
4307 the source block. Otherwise there is no additional info
4310 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4312 && e2
->flags
& EDGE_EXECUTABLE
)
4314 if (e2
&& (e2
->flags
& EDGE_EXECUTABLE
))
4316 gimple
*stmt
= last_stmt (e
->src
);
4318 && gimple_code (stmt
) == GIMPLE_COND
)
4320 enum tree_code code
= gimple_cond_code (stmt
);
4321 tree lhs
= gimple_cond_lhs (stmt
);
4322 tree rhs
= gimple_cond_rhs (stmt
);
4323 record_conds (bb
, code
, lhs
, rhs
,
4324 (e
->flags
& EDGE_TRUE_VALUE
) != 0);
4325 code
= invert_tree_comparison (code
, HONOR_NANS (lhs
));
4326 if (code
!= ERROR_MARK
)
4327 record_conds (bb
, code
, lhs
, rhs
,
4328 (e
->flags
& EDGE_TRUE_VALUE
) == 0);
4333 /* Value-number all defs in the basic-block. */
4334 for (gphi_iterator gsi
= gsi_start_phis (bb
);
4335 !gsi_end_p (gsi
); gsi_next (&gsi
))
4337 gphi
*phi
= gsi
.phi ();
4338 tree res
= PHI_RESULT (phi
);
4339 if (!VN_INFO (res
)->visited
4346 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
4347 !gsi_end_p (gsi
); gsi_next (&gsi
))
4351 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_ALL_DEFS
)
4352 if (!VN_INFO (op
)->visited
4360 /* Finally look at the last stmt. */
4361 gimple
*stmt
= last_stmt (bb
);
4365 enum gimple_code code
= gimple_code (stmt
);
4366 if (code
!= GIMPLE_COND
4367 && code
!= GIMPLE_SWITCH
4368 && code
!= GIMPLE_GOTO
)
4371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4373 fprintf (dump_file
, "Visiting control stmt ending BB %d: ", bb
->index
);
4374 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4377 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4378 if value-numbering can prove they are not reachable. Handling
4379 computed gotos is also possible. */
4385 tree lhs
= vn_valueize (gimple_cond_lhs (stmt
));
4386 tree rhs
= vn_valueize (gimple_cond_rhs (stmt
));
4387 val
= gimple_simplify (gimple_cond_code (stmt
),
4388 boolean_type_node
, lhs
, rhs
,
4390 /* If that didn't simplify to a constant see if we have recorded
4391 temporary expressions from taken edges. */
4392 if (!val
|| TREE_CODE (val
) != INTEGER_CST
)
4397 val
= vn_nary_op_lookup_pieces (2, gimple_cond_code (stmt
),
4398 boolean_type_node
, ops
, NULL
);
4403 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
4406 val
= gimple_goto_dest (stmt
);
4414 edge taken
= find_taken_edge (bb
, vn_valueize (val
));
4418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4419 fprintf (dump_file
, "Marking all edges out of BB %d but (%d -> %d) as "
4420 "not executable\n", bb
->index
, bb
->index
, taken
->dest
->index
);
4422 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4424 e
->flags
&= ~EDGE_EXECUTABLE
;
4427 /* Do SCCVN. Returns true if it finished, false if we bailed out
4428 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4429 how we use the alias oracle walking during the VN process. */
4432 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4437 default_vn_walk_kind
= default_vn_walk_kind_
;
4441 /* Collect pointers we know point to readonly memory. */
4442 const_parms
= BITMAP_ALLOC (NULL
);
4443 tree fnspec
= lookup_attribute ("fn spec",
4444 TYPE_ATTRIBUTES (TREE_TYPE (cfun
->decl
)));
4447 fnspec
= TREE_VALUE (TREE_VALUE (fnspec
));
4449 for (tree arg
= DECL_ARGUMENTS (cfun
->decl
);
4450 arg
; arg
= DECL_CHAIN (arg
), ++i
)
4452 if (i
>= (unsigned) TREE_STRING_LENGTH (fnspec
))
4454 if (TREE_STRING_POINTER (fnspec
)[i
] == 'R'
4455 || TREE_STRING_POINTER (fnspec
)[i
] == 'r')
4457 tree name
= ssa_default_def (cfun
, arg
);
4459 bitmap_set_bit (const_parms
, SSA_NAME_VERSION (name
));
4464 /* Mark all edges as possibly executable. */
4465 FOR_ALL_BB_FN (bb
, cfun
)
4469 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4470 e
->flags
|= EDGE_EXECUTABLE
;
4473 /* Walk all blocks in dominator order, value-numbering stmts
4474 SSA defs and decide whether outgoing edges are not executable. */
4475 sccvn_dom_walker walker
;
4476 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4483 /* Initialize the value ids and prune out remaining VN_TOPs
4485 for (i
= 1; i
< num_ssa_names
; ++i
)
4487 tree name
= ssa_name (i
);
4491 info
= VN_INFO (name
);
4493 info
->valnum
= name
;
4494 if (info
->valnum
== name
4495 || info
->valnum
== VN_TOP
)
4496 info
->value_id
= get_next_value_id ();
4497 else if (is_gimple_min_invariant (info
->valnum
))
4498 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4502 for (i
= 1; i
< num_ssa_names
; ++i
)
4504 tree name
= ssa_name (i
);
4508 info
= VN_INFO (name
);
4509 if (TREE_CODE (info
->valnum
) == SSA_NAME
4510 && info
->valnum
!= name
4511 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4512 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4515 set_hashtable_value_ids ();
4517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4519 fprintf (dump_file
, "Value numbers:\n");
4520 for (i
= 0; i
< num_ssa_names
; i
++)
4522 tree name
= ssa_name (i
);
4524 && VN_INFO (name
)->visited
4525 && SSA_VAL (name
) != name
)
4527 print_generic_expr (dump_file
, name
, 0);
4528 fprintf (dump_file
, " = ");
4529 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4530 fprintf (dump_file
, "\n");
4538 /* Return the maximum value id we have ever seen. */
4541 get_max_value_id (void)
4543 return next_value_id
;
4546 /* Return the next unique value id. */
4549 get_next_value_id (void)
4551 return next_value_id
++;
4555 /* Compare two expressions E1 and E2 and return true if they are equal. */
4558 expressions_equal_p (tree e1
, tree e2
)
4560 /* The obvious case. */
4564 /* If only one of them is null, they cannot be equal. */
4568 /* Now perform the actual comparison. */
4569 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4570 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4577 /* Return true if the nary operation NARY may trap. This is a copy
4578 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4581 vn_nary_may_trap (vn_nary_op_t nary
)
4584 tree rhs2
= NULL_TREE
;
4585 bool honor_nans
= false;
4586 bool honor_snans
= false;
4587 bool fp_operation
= false;
4588 bool honor_trapv
= false;
4592 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4593 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4594 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4597 fp_operation
= FLOAT_TYPE_P (type
);
4600 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4601 honor_snans
= flag_signaling_nans
!= 0;
4603 else if (INTEGRAL_TYPE_P (type
)
4604 && TYPE_OVERFLOW_TRAPS (type
))
4607 if (nary
->length
>= 2)
4609 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4611 honor_nans
, honor_snans
, rhs2
,
4617 for (i
= 0; i
< nary
->length
; ++i
)
4618 if (tree_could_trap_p (nary
->op
[i
]))