1 /* SCC value numbering for trees
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "stor-layout.h"
32 #include "hard-reg-set.h"
35 #include "dominance.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
40 #include "tree-inline.h"
41 #include "hash-table.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
45 #include "gimple-fold.h"
47 #include "gimple-expr.h"
51 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "stringpool.h"
55 #include "tree-ssanames.h"
60 #include "alloc-pool.h"
64 #include "tree-ssa-propagate.h"
65 #include "tree-ssa-sccvn.h"
69 #include "plugin-api.h"
72 /* This algorithm is based on the SCC algorithm presented by Keith
73 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
74 (http://citeseer.ist.psu.edu/41805.html). In
75 straight line code, it is equivalent to a regular hash based value
76 numbering that is performed in reverse postorder.
78 For code with cycles, there are two alternatives, both of which
79 require keeping the hashtables separate from the actual list of
80 value numbers for SSA names.
82 1. Iterate value numbering in an RPO walk of the blocks, removing
83 all the entries from the hashtable after each iteration (but
84 keeping the SSA name->value number mapping between iterations).
85 Iterate until it does not change.
87 2. Perform value numbering as part of an SCC walk on the SSA graph,
88 iterating only the cycles in the SSA graph until they do not change
89 (using a separate, optimistic hashtable for value numbering the SCC
92 The second is not just faster in practice (because most SSA graph
93 cycles do not involve all the variables in the graph), it also has
96 One of these nice properties is that when we pop an SCC off the
97 stack, we are guaranteed to have processed all the operands coming from
98 *outside of that SCC*, so we do not need to do anything special to
99 ensure they have value numbers.
101 Another nice property is that the SCC walk is done as part of a DFS
102 of the SSA graph, which makes it easy to perform combining and
103 simplifying operations at the same time.
105 The code below is deliberately written in a way that makes it easy
106 to separate the SCC walk from the other work it does.
108 In order to propagate constants through the code, we track which
109 expressions contain constants, and use those while folding. In
110 theory, we could also track expressions whose value numbers are
111 replaced, in case we end up folding based on expression
114 In order to value number memory, we assign value numbers to vuses.
115 This enables us to note that, for example, stores to the same
116 address of the same value from the same starting memory states are
120 1. We can iterate only the changing portions of the SCC's, but
121 I have not seen an SCC big enough for this to be a win.
122 2. If you differentiate between phi nodes for loops and phi nodes
123 for if-then-else, you can properly consider phi nodes in different
124 blocks for equivalence.
125 3. We could value number vuses in more cases, particularly, whole
130 /* vn_nary_op hashtable helpers. */
132 struct vn_nary_op_hasher
: typed_noop_remove
<vn_nary_op_s
>
134 typedef vn_nary_op_s value_type
;
135 typedef vn_nary_op_s compare_type
;
136 static inline hashval_t
hash (const value_type
*);
137 static inline bool equal (const value_type
*, const compare_type
*);
140 /* Return the computed hashcode for nary operation P1. */
143 vn_nary_op_hasher::hash (const value_type
*vno1
)
145 return vno1
->hashcode
;
148 /* Compare nary operations P1 and P2 and return true if they are
152 vn_nary_op_hasher::equal (const value_type
*vno1
, const compare_type
*vno2
)
154 return vn_nary_op_eq (vno1
, vno2
);
157 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
158 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
161 /* vn_phi hashtable helpers. */
164 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
168 typedef vn_phi_s value_type
;
169 typedef vn_phi_s compare_type
;
170 static inline hashval_t
hash (const value_type
*);
171 static inline bool equal (const value_type
*, const compare_type
*);
172 static inline void remove (value_type
*);
175 /* Return the computed hashcode for phi operation P1. */
178 vn_phi_hasher::hash (const value_type
*vp1
)
180 return vp1
->hashcode
;
183 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
186 vn_phi_hasher::equal (const value_type
*vp1
, const compare_type
*vp2
)
188 return vn_phi_eq (vp1
, vp2
);
191 /* Free a phi operation structure VP. */
194 vn_phi_hasher::remove (value_type
*phi
)
196 phi
->phiargs
.release ();
199 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
200 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
203 /* Compare two reference operands P1 and P2 for equality. Return true if
204 they are equal, and false otherwise. */
207 vn_reference_op_eq (const void *p1
, const void *p2
)
209 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
210 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
212 return (vro1
->opcode
== vro2
->opcode
213 /* We do not care for differences in type qualification. */
214 && (vro1
->type
== vro2
->type
215 || (vro1
->type
&& vro2
->type
216 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
217 TYPE_MAIN_VARIANT (vro2
->type
))))
218 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
219 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
220 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
223 /* Free a reference operation structure VP. */
226 free_reference (vn_reference_s
*vr
)
228 vr
->operands
.release ();
232 /* vn_reference hashtable helpers. */
234 struct vn_reference_hasher
236 typedef vn_reference_s value_type
;
237 typedef vn_reference_s compare_type
;
238 static inline hashval_t
hash (const value_type
*);
239 static inline bool equal (const value_type
*, const compare_type
*);
240 static inline void remove (value_type
*);
243 /* Return the hashcode for a given reference operation P1. */
246 vn_reference_hasher::hash (const value_type
*vr1
)
248 return vr1
->hashcode
;
252 vn_reference_hasher::equal (const value_type
*v
, const compare_type
*c
)
254 return vn_reference_eq (v
, c
);
258 vn_reference_hasher::remove (value_type
*v
)
263 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
264 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
267 /* The set of hashtables and alloc_pool's for their items. */
269 typedef struct vn_tables_s
271 vn_nary_op_table_type
*nary
;
272 vn_phi_table_type
*phis
;
273 vn_reference_table_type
*references
;
274 struct obstack nary_obstack
;
275 alloc_pool phis_pool
;
276 alloc_pool references_pool
;
280 /* vn_constant hashtable helpers. */
282 struct vn_constant_hasher
: typed_free_remove
<vn_constant_s
>
284 typedef vn_constant_s value_type
;
285 typedef vn_constant_s compare_type
;
286 static inline hashval_t
hash (const value_type
*);
287 static inline bool equal (const value_type
*, const compare_type
*);
290 /* Hash table hash function for vn_constant_t. */
293 vn_constant_hasher::hash (const value_type
*vc1
)
295 return vc1
->hashcode
;
298 /* Hash table equality function for vn_constant_t. */
301 vn_constant_hasher::equal (const value_type
*vc1
, const compare_type
*vc2
)
303 if (vc1
->hashcode
!= vc2
->hashcode
)
306 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
309 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
310 static bitmap constant_value_ids
;
313 /* Valid hashtables storing information we have proven to be
316 static vn_tables_t valid_info
;
318 /* Optimistic hashtables storing information we are making assumptions about
319 during iterations. */
321 static vn_tables_t optimistic_info
;
323 /* Pointer to the set of hashtables that is currently being used.
324 Should always point to either the optimistic_info, or the
327 static vn_tables_t current_info
;
330 /* Reverse post order index for each basic block. */
332 static int *rpo_numbers
;
334 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
336 /* Return the SSA value of the VUSE x, supporting released VDEFs
337 during elimination which will value-number the VDEF to the
338 associated VUSE (but not substitute in the whole lattice). */
341 vuse_ssa_val (tree x
)
350 while (SSA_NAME_IN_FREE_LIST (x
));
355 /* This represents the top of the VN lattice, which is the universal
360 /* Unique counter for our value ids. */
362 static unsigned int next_value_id
;
364 /* Next DFS number and the stack for strongly connected component
367 static unsigned int next_dfs_num
;
368 static vec
<tree
> sccstack
;
372 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
373 are allocated on an obstack for locality reasons, and to free them
374 without looping over the vec. */
376 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
377 static struct obstack vn_ssa_aux_obstack
;
379 /* Return the value numbering information for a given SSA name. */
384 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
385 gcc_checking_assert (res
);
389 /* Set the value numbering info for a given SSA name to a given
393 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
395 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
398 /* Initialize the value numbering info for a given SSA name.
399 This should be called just once for every SSA name. */
402 VN_INFO_GET (tree name
)
404 vn_ssa_aux_t newinfo
;
406 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
407 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
408 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
409 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
410 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
415 /* Get the representative expression for the SSA_NAME NAME. Returns
416 the representative SSA_NAME if there is no expression associated with it. */
419 vn_get_expr_for (tree name
)
421 vn_ssa_aux_t vn
= VN_INFO (name
);
423 tree expr
= NULL_TREE
;
426 if (vn
->valnum
== VN_TOP
)
429 /* If the value-number is a constant it is the representative
431 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
434 /* Get to the information of the value of this SSA_NAME. */
435 vn
= VN_INFO (vn
->valnum
);
437 /* If the value-number is a constant it is the representative
439 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
442 /* Else if we have an expression, return it. */
443 if (vn
->expr
!= NULL_TREE
)
446 /* Otherwise use the defining statement to build the expression. */
447 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
449 /* If the value number is not an assignment use it directly. */
450 if (!is_gimple_assign (def_stmt
))
453 /* Note that we can valueize here because we clear the cached
454 simplified expressions after each optimistic iteration. */
455 code
= gimple_assign_rhs_code (def_stmt
);
456 switch (TREE_CODE_CLASS (code
))
459 if ((code
== REALPART_EXPR
460 || code
== IMAGPART_EXPR
461 || code
== VIEW_CONVERT_EXPR
)
462 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
464 expr
= fold_build1 (code
,
465 gimple_expr_type (def_stmt
),
466 vn_valueize (TREE_OPERAND
467 (gimple_assign_rhs1 (def_stmt
), 0)));
471 expr
= fold_build1 (code
,
472 gimple_expr_type (def_stmt
),
473 vn_valueize (gimple_assign_rhs1 (def_stmt
)));
477 expr
= fold_build2 (code
,
478 gimple_expr_type (def_stmt
),
479 vn_valueize (gimple_assign_rhs1 (def_stmt
)),
480 vn_valueize (gimple_assign_rhs2 (def_stmt
)));
483 case tcc_exceptional
:
484 if (code
== CONSTRUCTOR
486 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
487 expr
= gimple_assign_rhs1 (def_stmt
);
492 if (expr
== NULL_TREE
)
495 /* Cache the expression. */
501 /* Return the vn_kind the expression computed by the stmt should be
505 vn_get_stmt_kind (gimple stmt
)
507 switch (gimple_code (stmt
))
515 enum tree_code code
= gimple_assign_rhs_code (stmt
);
516 tree rhs1
= gimple_assign_rhs1 (stmt
);
517 switch (get_gimple_rhs_class (code
))
519 case GIMPLE_UNARY_RHS
:
520 case GIMPLE_BINARY_RHS
:
521 case GIMPLE_TERNARY_RHS
:
523 case GIMPLE_SINGLE_RHS
:
524 switch (TREE_CODE_CLASS (code
))
527 /* VOP-less references can go through unary case. */
528 if ((code
== REALPART_EXPR
529 || code
== IMAGPART_EXPR
530 || code
== VIEW_CONVERT_EXPR
531 || code
== BIT_FIELD_REF
)
532 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
536 case tcc_declaration
:
543 if (code
== ADDR_EXPR
)
544 return (is_gimple_min_invariant (rhs1
)
545 ? VN_CONSTANT
: VN_REFERENCE
);
546 else if (code
== CONSTRUCTOR
)
559 /* Lookup a value id for CONSTANT and return it. If it does not
563 get_constant_value_id (tree constant
)
565 vn_constant_s
**slot
;
566 struct vn_constant_s vc
;
568 vc
.hashcode
= vn_hash_constant_with_type (constant
);
569 vc
.constant
= constant
;
570 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
572 return (*slot
)->value_id
;
576 /* Lookup a value id for CONSTANT, and if it does not exist, create a
577 new one and return it. If it does exist, return it. */
580 get_or_alloc_constant_value_id (tree constant
)
582 vn_constant_s
**slot
;
583 struct vn_constant_s vc
;
586 vc
.hashcode
= vn_hash_constant_with_type (constant
);
587 vc
.constant
= constant
;
588 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
590 return (*slot
)->value_id
;
592 vcp
= XNEW (struct vn_constant_s
);
593 vcp
->hashcode
= vc
.hashcode
;
594 vcp
->constant
= constant
;
595 vcp
->value_id
= get_next_value_id ();
597 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
598 return vcp
->value_id
;
601 /* Return true if V is a value id for a constant. */
604 value_id_constant_p (unsigned int v
)
606 return bitmap_bit_p (constant_value_ids
, v
);
609 /* Compute the hash for a reference operand VRO1. */
612 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
614 hstate
.add_int (vro1
->opcode
);
616 inchash::add_expr (vro1
->op0
, hstate
);
618 inchash::add_expr (vro1
->op1
, hstate
);
620 inchash::add_expr (vro1
->op2
, hstate
);
623 /* Compute a hash for the reference operation VR1 and return it. */
626 vn_reference_compute_hash (const vn_reference_t vr1
)
628 inchash::hash hstate
;
631 vn_reference_op_t vro
;
632 HOST_WIDE_INT off
= -1;
635 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
637 if (vro
->opcode
== MEM_REF
)
639 else if (vro
->opcode
!= ADDR_EXPR
)
651 hstate
.add_int (off
);
654 && vro
->opcode
== ADDR_EXPR
)
658 tree op
= TREE_OPERAND (vro
->op0
, 0);
659 hstate
.add_int (TREE_CODE (op
));
660 inchash::add_expr (op
, hstate
);
664 vn_reference_op_compute_hash (vro
, hstate
);
667 result
= hstate
.end ();
668 /* ??? We would ICE later if we hash instead of adding that in. */
670 result
+= SSA_NAME_VERSION (vr1
->vuse
);
675 /* Return true if reference operations VR1 and VR2 are equivalent. This
676 means they have the same set of operands and vuses. */
679 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
683 /* Early out if this is not a hash collision. */
684 if (vr1
->hashcode
!= vr2
->hashcode
)
687 /* The VOP needs to be the same. */
688 if (vr1
->vuse
!= vr2
->vuse
)
691 /* If the operands are the same we are done. */
692 if (vr1
->operands
== vr2
->operands
)
695 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
698 if (INTEGRAL_TYPE_P (vr1
->type
)
699 && INTEGRAL_TYPE_P (vr2
->type
))
701 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
704 else if (INTEGRAL_TYPE_P (vr1
->type
)
705 && (TYPE_PRECISION (vr1
->type
)
706 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
708 else if (INTEGRAL_TYPE_P (vr2
->type
)
709 && (TYPE_PRECISION (vr2
->type
)
710 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
717 HOST_WIDE_INT off1
= 0, off2
= 0;
718 vn_reference_op_t vro1
, vro2
;
719 vn_reference_op_s tem1
, tem2
;
720 bool deref1
= false, deref2
= false;
721 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
723 if (vro1
->opcode
== MEM_REF
)
729 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
731 if (vro2
->opcode
== MEM_REF
)
739 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
741 memset (&tem1
, 0, sizeof (tem1
));
742 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
743 tem1
.type
= TREE_TYPE (tem1
.op0
);
744 tem1
.opcode
= TREE_CODE (tem1
.op0
);
748 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
750 memset (&tem2
, 0, sizeof (tem2
));
751 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
752 tem2
.type
= TREE_TYPE (tem2
.op0
);
753 tem2
.opcode
= TREE_CODE (tem2
.op0
);
757 if (deref1
!= deref2
)
759 if (!vn_reference_op_eq (vro1
, vro2
))
764 while (vr1
->operands
.length () != i
765 || vr2
->operands
.length () != j
);
770 /* Copy the operations present in load/store REF into RESULT, a vector of
771 vn_reference_op_s's. */
774 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
776 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
778 vn_reference_op_s temp
;
782 memset (&temp
, 0, sizeof (temp
));
783 temp
.type
= TREE_TYPE (ref
);
784 temp
.opcode
= TREE_CODE (ref
);
785 temp
.op0
= TMR_INDEX (ref
);
786 temp
.op1
= TMR_STEP (ref
);
787 temp
.op2
= TMR_OFFSET (ref
);
789 result
->quick_push (temp
);
791 memset (&temp
, 0, sizeof (temp
));
792 temp
.type
= NULL_TREE
;
793 temp
.opcode
= ERROR_MARK
;
794 temp
.op0
= TMR_INDEX2 (ref
);
796 result
->quick_push (temp
);
798 memset (&temp
, 0, sizeof (temp
));
799 temp
.type
= NULL_TREE
;
800 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
801 temp
.op0
= TMR_BASE (ref
);
803 result
->quick_push (temp
);
807 /* For non-calls, store the information that makes up the address. */
811 vn_reference_op_s temp
;
813 memset (&temp
, 0, sizeof (temp
));
814 temp
.type
= TREE_TYPE (ref
);
815 temp
.opcode
= TREE_CODE (ref
);
821 temp
.op0
= TREE_OPERAND (ref
, 1);
824 temp
.op0
= TREE_OPERAND (ref
, 1);
828 /* The base address gets its own vn_reference_op_s structure. */
829 temp
.op0
= TREE_OPERAND (ref
, 1);
830 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 1)))
831 temp
.off
= tree_to_shwi (TREE_OPERAND (ref
, 1));
834 /* Record bits and position. */
835 temp
.op0
= TREE_OPERAND (ref
, 1);
836 temp
.op1
= TREE_OPERAND (ref
, 2);
839 /* The field decl is enough to unambiguously specify the field,
840 a matching type is not necessary and a mismatching type
841 is always a spurious difference. */
842 temp
.type
= NULL_TREE
;
843 temp
.op0
= TREE_OPERAND (ref
, 1);
844 temp
.op1
= TREE_OPERAND (ref
, 2);
846 tree this_offset
= component_ref_field_offset (ref
);
848 && TREE_CODE (this_offset
) == INTEGER_CST
)
850 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
851 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
854 = (wi::to_offset (this_offset
)
855 + wi::lrshift (wi::to_offset (bit_offset
),
856 LOG2_BITS_PER_UNIT
));
857 if (wi::fits_shwi_p (off
)
858 /* Probibit value-numbering zero offset components
859 of addresses the same before the pass folding
860 __builtin_object_size had a chance to run
861 (checking cfun->after_inlining does the
863 && (TREE_CODE (orig
) != ADDR_EXPR
865 || cfun
->after_inlining
))
866 temp
.off
= off
.to_shwi ();
871 case ARRAY_RANGE_REF
:
873 /* Record index as operand. */
874 temp
.op0
= TREE_OPERAND (ref
, 1);
875 /* Always record lower bounds and element size. */
876 temp
.op1
= array_ref_low_bound (ref
);
877 temp
.op2
= array_ref_element_size (ref
);
878 if (TREE_CODE (temp
.op0
) == INTEGER_CST
879 && TREE_CODE (temp
.op1
) == INTEGER_CST
880 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
882 offset_int off
= ((wi::to_offset (temp
.op0
)
883 - wi::to_offset (temp
.op1
))
884 * wi::to_offset (temp
.op2
));
885 if (wi::fits_shwi_p (off
))
886 temp
.off
= off
.to_shwi();
890 if (DECL_HARD_REGISTER (ref
))
899 /* Canonicalize decls to MEM[&decl] which is what we end up with
900 when valueizing MEM[ptr] with ptr = &decl. */
901 temp
.opcode
= MEM_REF
;
902 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
904 result
->safe_push (temp
);
905 temp
.opcode
= ADDR_EXPR
;
906 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
907 temp
.type
= TREE_TYPE (temp
.op0
);
921 if (is_gimple_min_invariant (ref
))
927 /* These are only interesting for their operands, their
928 existence, and their type. They will never be the last
929 ref in the chain of references (IE they require an
930 operand), so we don't have to put anything
931 for op* as it will be handled by the iteration */
933 case VIEW_CONVERT_EXPR
:
937 /* This is only interesting for its constant offset. */
938 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
943 result
->safe_push (temp
);
945 if (REFERENCE_CLASS_P (ref
)
946 || TREE_CODE (ref
) == MODIFY_EXPR
947 || TREE_CODE (ref
) == WITH_SIZE_EXPR
948 || (TREE_CODE (ref
) == ADDR_EXPR
949 && !is_gimple_min_invariant (ref
)))
950 ref
= TREE_OPERAND (ref
, 0);
956 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
957 operands in *OPS, the reference alias set SET and the reference type TYPE.
958 Return true if something useful was produced. */
961 ao_ref_init_from_vn_reference (ao_ref
*ref
,
962 alias_set_type set
, tree type
,
963 vec
<vn_reference_op_s
> ops
)
965 vn_reference_op_t op
;
967 tree base
= NULL_TREE
;
969 HOST_WIDE_INT offset
= 0;
970 HOST_WIDE_INT max_size
;
971 HOST_WIDE_INT size
= -1;
972 tree size_tree
= NULL_TREE
;
973 alias_set_type base_alias_set
= -1;
975 /* First get the final access size from just the outermost expression. */
977 if (op
->opcode
== COMPONENT_REF
)
978 size_tree
= DECL_SIZE (op
->op0
);
979 else if (op
->opcode
== BIT_FIELD_REF
)
983 machine_mode mode
= TYPE_MODE (type
);
985 size_tree
= TYPE_SIZE (type
);
987 size
= GET_MODE_BITSIZE (mode
);
989 if (size_tree
!= NULL_TREE
)
991 if (!tree_fits_uhwi_p (size_tree
))
994 size
= tree_to_uhwi (size_tree
);
997 /* Initially, maxsize is the same as the accessed element size.
998 In the following it will only grow (or become -1). */
1001 /* Compute cumulative bit-offset for nested component-refs and array-refs,
1002 and find the ultimate containing object. */
1003 FOR_EACH_VEC_ELT (ops
, i
, op
)
1007 /* These may be in the reference ops, but we cannot do anything
1008 sensible with them here. */
1010 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1011 if (base
!= NULL_TREE
1012 && TREE_CODE (base
) == MEM_REF
1014 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
1016 vn_reference_op_t pop
= &ops
[i
-1];
1017 base
= TREE_OPERAND (op
->op0
, 0);
1024 offset
+= pop
->off
* BITS_PER_UNIT
;
1032 /* Record the base objects. */
1034 base_alias_set
= get_deref_alias_set (op
->op0
);
1035 *op0_p
= build2 (MEM_REF
, op
->type
,
1036 NULL_TREE
, op
->op0
);
1037 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1048 /* And now the usual component-reference style ops. */
1050 offset
+= tree_to_shwi (op
->op1
);
1055 tree field
= op
->op0
;
1056 /* We do not have a complete COMPONENT_REF tree here so we
1057 cannot use component_ref_field_offset. Do the interesting
1061 || !tree_fits_uhwi_p (DECL_FIELD_OFFSET (field
)))
1065 offset
+= (tree_to_uhwi (DECL_FIELD_OFFSET (field
))
1067 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
1072 case ARRAY_RANGE_REF
:
1074 /* We recorded the lower bound and the element size. */
1075 if (!tree_fits_shwi_p (op
->op0
)
1076 || !tree_fits_shwi_p (op
->op1
)
1077 || !tree_fits_shwi_p (op
->op2
))
1081 HOST_WIDE_INT hindex
= tree_to_shwi (op
->op0
);
1082 hindex
-= tree_to_shwi (op
->op1
);
1083 hindex
*= tree_to_shwi (op
->op2
);
1084 hindex
*= BITS_PER_UNIT
;
1096 case VIEW_CONVERT_EXPR
:
1113 if (base
== NULL_TREE
)
1116 ref
->ref
= NULL_TREE
;
1118 ref
->offset
= offset
;
1120 ref
->max_size
= max_size
;
1121 ref
->ref_alias_set
= set
;
1122 if (base_alias_set
!= -1)
1123 ref
->base_alias_set
= base_alias_set
;
1125 ref
->base_alias_set
= get_alias_set (base
);
1126 /* We discount volatiles from value-numbering elsewhere. */
1127 ref
->volatile_p
= false;
1132 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1133 vn_reference_op_s's. */
1136 copy_reference_ops_from_call (gcall
*call
,
1137 vec
<vn_reference_op_s
> *result
)
1139 vn_reference_op_s temp
;
1141 tree lhs
= gimple_call_lhs (call
);
1144 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1145 different. By adding the lhs here in the vector, we ensure that the
1146 hashcode is different, guaranteeing a different value number. */
1147 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1149 memset (&temp
, 0, sizeof (temp
));
1150 temp
.opcode
= MODIFY_EXPR
;
1151 temp
.type
= TREE_TYPE (lhs
);
1154 result
->safe_push (temp
);
1157 /* Copy the type, opcode, function, static chain and EH region, if any. */
1158 memset (&temp
, 0, sizeof (temp
));
1159 temp
.type
= gimple_call_return_type (call
);
1160 temp
.opcode
= CALL_EXPR
;
1161 temp
.op0
= gimple_call_fn (call
);
1162 temp
.op1
= gimple_call_chain (call
);
1163 if (stmt_could_throw_p (call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1164 temp
.op2
= size_int (lr
);
1166 if (gimple_call_with_bounds_p (call
))
1167 temp
.with_bounds
= 1;
1168 result
->safe_push (temp
);
1170 /* Copy the call arguments. As they can be references as well,
1171 just chain them together. */
1172 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1174 tree callarg
= gimple_call_arg (call
, i
);
1175 copy_reference_ops_from_ref (callarg
, result
);
1179 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1180 *I_P to point to the last element of the replacement. */
1182 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1185 unsigned int i
= *i_p
;
1186 vn_reference_op_t op
= &(*ops
)[i
];
1187 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1189 HOST_WIDE_INT addr_offset
= 0;
1191 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1192 from .foo.bar to the preceding MEM_REF offset and replace the
1193 address with &OBJ. */
1194 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1196 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1197 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1199 offset_int off
= offset_int::from (mem_op
->op0
, SIGNED
);
1201 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1202 op
->op0
= build_fold_addr_expr (addr_base
);
1203 if (tree_fits_shwi_p (mem_op
->op0
))
1204 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1210 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1211 *I_P to point to the last element of the replacement. */
1213 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1216 unsigned int i
= *i_p
;
1217 vn_reference_op_t op
= &(*ops
)[i
];
1218 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1220 enum tree_code code
;
1223 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1224 if (!is_gimple_assign (def_stmt
))
1227 code
= gimple_assign_rhs_code (def_stmt
);
1228 if (code
!= ADDR_EXPR
1229 && code
!= POINTER_PLUS_EXPR
)
1232 off
= offset_int::from (mem_op
->op0
, SIGNED
);
1234 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1235 from .foo.bar to the preceding MEM_REF offset and replace the
1236 address with &OBJ. */
1237 if (code
== ADDR_EXPR
)
1239 tree addr
, addr_base
;
1240 HOST_WIDE_INT addr_offset
;
1242 addr
= gimple_assign_rhs1 (def_stmt
);
1243 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1246 || TREE_CODE (addr_base
) != MEM_REF
)
1250 off
+= mem_ref_offset (addr_base
);
1251 op
->op0
= TREE_OPERAND (addr_base
, 0);
1256 ptr
= gimple_assign_rhs1 (def_stmt
);
1257 ptroff
= gimple_assign_rhs2 (def_stmt
);
1258 if (TREE_CODE (ptr
) != SSA_NAME
1259 || TREE_CODE (ptroff
) != INTEGER_CST
)
1262 off
+= wi::to_offset (ptroff
);
1266 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1267 if (tree_fits_shwi_p (mem_op
->op0
))
1268 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1271 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1272 op
->op0
= SSA_VAL (op
->op0
);
1273 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1274 op
->opcode
= TREE_CODE (op
->op0
);
1277 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1278 vn_reference_maybe_forwprop_address (ops
, i_p
);
1279 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1280 vn_reference_fold_indirect (ops
, i_p
);
1283 /* Optimize the reference REF to a constant if possible or return
1284 NULL_TREE if not. */
1287 fully_constant_vn_reference_p (vn_reference_t ref
)
1289 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1290 vn_reference_op_t op
;
1292 /* Try to simplify the translated expression if it is
1293 a call to a builtin function with at most two arguments. */
1295 if (op
->opcode
== CALL_EXPR
1296 && TREE_CODE (op
->op0
) == ADDR_EXPR
1297 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1298 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1299 && operands
.length () >= 2
1300 && operands
.length () <= 3)
1302 vn_reference_op_t arg0
, arg1
= NULL
;
1303 bool anyconst
= false;
1304 arg0
= &operands
[1];
1305 if (operands
.length () > 2)
1306 arg1
= &operands
[2];
1307 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1308 || (arg0
->opcode
== ADDR_EXPR
1309 && is_gimple_min_invariant (arg0
->op0
)))
1312 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1313 || (arg1
->opcode
== ADDR_EXPR
1314 && is_gimple_min_invariant (arg1
->op0
))))
1318 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1321 arg1
? arg1
->op0
: NULL
);
1323 && TREE_CODE (folded
) == NOP_EXPR
)
1324 folded
= TREE_OPERAND (folded
, 0);
1326 && is_gimple_min_invariant (folded
))
1331 /* Simplify reads from constants or constant initializers. */
1332 else if (BITS_PER_UNIT
== 8
1333 && is_gimple_reg_type (ref
->type
)
1334 && (!INTEGRAL_TYPE_P (ref
->type
)
1335 || TYPE_PRECISION (ref
->type
) % BITS_PER_UNIT
== 0))
1337 HOST_WIDE_INT off
= 0;
1338 HOST_WIDE_INT size
= tree_to_shwi (TYPE_SIZE (ref
->type
));
1339 if (size
% BITS_PER_UNIT
!= 0
1340 || size
> MAX_BITSIZE_MODE_ANY_MODE
)
1342 size
/= BITS_PER_UNIT
;
1344 for (i
= 0; i
< operands
.length (); ++i
)
1346 if (operands
[i
].off
== -1)
1348 off
+= operands
[i
].off
;
1349 if (operands
[i
].opcode
== MEM_REF
)
1355 vn_reference_op_t base
= &operands
[--i
];
1356 tree ctor
= error_mark_node
;
1357 tree decl
= NULL_TREE
;
1358 if (TREE_CODE_CLASS (base
->opcode
) == tcc_constant
)
1360 else if (base
->opcode
== MEM_REF
1361 && base
[1].opcode
== ADDR_EXPR
1362 && (TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == VAR_DECL
1363 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == CONST_DECL
))
1365 decl
= TREE_OPERAND (base
[1].op0
, 0);
1366 ctor
= ctor_for_folding (decl
);
1368 if (ctor
== NULL_TREE
)
1369 return build_zero_cst (ref
->type
);
1370 else if (ctor
!= error_mark_node
)
1374 tree res
= fold_ctor_reference (ref
->type
, ctor
,
1375 off
* BITS_PER_UNIT
,
1376 size
* BITS_PER_UNIT
, decl
);
1379 STRIP_USELESS_TYPE_CONVERSION (res
);
1380 if (is_gimple_min_invariant (res
))
1386 unsigned char buf
[MAX_BITSIZE_MODE_ANY_MODE
/ BITS_PER_UNIT
];
1387 if (native_encode_expr (ctor
, buf
, size
, off
) > 0)
1388 return native_interpret_expr (ref
->type
, buf
, size
);
1396 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1397 structures into their value numbers. This is done in-place, and
1398 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1399 whether any operands were valueized. */
1401 static vec
<vn_reference_op_s
>
1402 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1404 vn_reference_op_t vro
;
1407 *valueized_anything
= false;
1409 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1411 if (vro
->opcode
== SSA_NAME
1412 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1414 tree tem
= SSA_VAL (vro
->op0
);
1415 if (tem
!= vro
->op0
)
1417 *valueized_anything
= true;
1420 /* If it transforms from an SSA_NAME to a constant, update
1422 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1423 vro
->opcode
= TREE_CODE (vro
->op0
);
1425 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1427 tree tem
= SSA_VAL (vro
->op1
);
1428 if (tem
!= vro
->op1
)
1430 *valueized_anything
= true;
1434 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1436 tree tem
= SSA_VAL (vro
->op2
);
1437 if (tem
!= vro
->op2
)
1439 *valueized_anything
= true;
1443 /* If it transforms from an SSA_NAME to an address, fold with
1444 a preceding indirect reference. */
1447 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1448 && orig
[i
- 1].opcode
== MEM_REF
)
1449 vn_reference_fold_indirect (&orig
, &i
);
1451 && vro
->opcode
== SSA_NAME
1452 && orig
[i
- 1].opcode
== MEM_REF
)
1453 vn_reference_maybe_forwprop_address (&orig
, &i
);
1454 /* If it transforms a non-constant ARRAY_REF into a constant
1455 one, adjust the constant offset. */
1456 else if (vro
->opcode
== ARRAY_REF
1458 && TREE_CODE (vro
->op0
) == INTEGER_CST
1459 && TREE_CODE (vro
->op1
) == INTEGER_CST
1460 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1462 offset_int off
= ((wi::to_offset (vro
->op0
)
1463 - wi::to_offset (vro
->op1
))
1464 * wi::to_offset (vro
->op2
));
1465 if (wi::fits_shwi_p (off
))
1466 vro
->off
= off
.to_shwi ();
1473 static vec
<vn_reference_op_s
>
1474 valueize_refs (vec
<vn_reference_op_s
> orig
)
1477 return valueize_refs_1 (orig
, &tem
);
1480 static vec
<vn_reference_op_s
> shared_lookup_references
;
1482 /* Create a vector of vn_reference_op_s structures from REF, a
1483 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1484 this function. *VALUEIZED_ANYTHING will specify whether any
1485 operands were valueized. */
1487 static vec
<vn_reference_op_s
>
1488 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1492 shared_lookup_references
.truncate (0);
1493 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1494 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1495 valueized_anything
);
1496 return shared_lookup_references
;
1499 /* Create a vector of vn_reference_op_s structures from CALL, a
1500 call statement. The vector is shared among all callers of
1503 static vec
<vn_reference_op_s
>
1504 valueize_shared_reference_ops_from_call (gcall
*call
)
1508 shared_lookup_references
.truncate (0);
1509 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1510 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1511 return shared_lookup_references
;
1514 /* Lookup a SCCVN reference operation VR in the current hash table.
1515 Returns the resulting value number if it exists in the hash table,
1516 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1517 vn_reference_t stored in the hashtable if something is found. */
1520 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1522 vn_reference_s
**slot
;
1525 hash
= vr
->hashcode
;
1526 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1527 if (!slot
&& current_info
== optimistic_info
)
1528 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1532 *vnresult
= (vn_reference_t
)*slot
;
1533 return ((vn_reference_t
)*slot
)->result
;
1539 static tree
*last_vuse_ptr
;
1540 static vn_lookup_kind vn_walk_kind
;
1541 static vn_lookup_kind default_vn_walk_kind
;
1543 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1544 with the current VUSE and performs the expression lookup. */
1547 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1548 unsigned int cnt
, void *vr_
)
1550 vn_reference_t vr
= (vn_reference_t
)vr_
;
1551 vn_reference_s
**slot
;
1554 /* This bounds the stmt walks we perform on reference lookups
1555 to O(1) instead of O(N) where N is the number of dominating
1557 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1561 *last_vuse_ptr
= vuse
;
1563 /* Fixup vuse and hash. */
1565 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1566 vr
->vuse
= vuse_ssa_val (vuse
);
1568 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1570 hash
= vr
->hashcode
;
1571 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1572 if (!slot
&& current_info
== optimistic_info
)
1573 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1580 /* Lookup an existing or insert a new vn_reference entry into the
1581 value table for the VUSE, SET, TYPE, OPERANDS reference which
1582 has the value VALUE which is either a constant or an SSA name. */
1584 static vn_reference_t
1585 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1588 vec
<vn_reference_op_s
,
1592 struct vn_reference_s vr1
;
1593 vn_reference_t result
;
1596 vr1
.operands
= operands
;
1599 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1600 if (vn_reference_lookup_1 (&vr1
, &result
))
1602 if (TREE_CODE (value
) == SSA_NAME
)
1603 value_id
= VN_INFO (value
)->value_id
;
1605 value_id
= get_or_alloc_constant_value_id (value
);
1606 return vn_reference_insert_pieces (vuse
, set
, type
,
1607 operands
.copy (), value
, value_id
);
1610 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1611 from the statement defining VUSE and if not successful tries to
1612 translate *REFP and VR_ through an aggregate copy at the definition
1616 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
,
1617 bool disambiguate_only
)
1619 vn_reference_t vr
= (vn_reference_t
)vr_
;
1620 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1622 HOST_WIDE_INT offset
, maxsize
;
1623 static vec
<vn_reference_op_s
>
1626 bool lhs_ref_ok
= false;
1628 /* First try to disambiguate after value-replacing in the definitions LHS. */
1629 if (is_gimple_assign (def_stmt
))
1631 vec
<vn_reference_op_s
> tem
;
1632 tree lhs
= gimple_assign_lhs (def_stmt
);
1633 bool valueized_anything
= false;
1634 /* Avoid re-allocation overhead. */
1635 lhs_ops
.truncate (0);
1636 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1638 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1639 gcc_assert (lhs_ops
== tem
);
1640 if (valueized_anything
)
1642 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1643 get_alias_set (lhs
),
1644 TREE_TYPE (lhs
), lhs_ops
);
1646 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1651 ao_ref_init (&lhs_ref
, lhs
);
1655 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
1656 && gimple_call_num_args (def_stmt
) <= 4)
1658 /* For builtin calls valueize its arguments and call the
1659 alias oracle again. Valueization may improve points-to
1660 info of pointers and constify size and position arguments.
1661 Originally this was motivated by PR61034 which has
1662 conditional calls to free falsely clobbering ref because
1663 of imprecise points-to info of the argument. */
1665 bool valueized_anything
= false;
1666 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1668 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
1669 if (TREE_CODE (oldargs
[i
]) == SSA_NAME
1670 && VN_INFO (oldargs
[i
])->valnum
!= oldargs
[i
])
1672 gimple_call_set_arg (def_stmt
, i
, VN_INFO (oldargs
[i
])->valnum
);
1673 valueized_anything
= true;
1676 if (valueized_anything
)
1678 bool res
= call_may_clobber_ref_p_1 (as_a
<gcall
*> (def_stmt
),
1680 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1681 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
1687 if (disambiguate_only
)
1690 base
= ao_ref_base (ref
);
1691 offset
= ref
->offset
;
1692 maxsize
= ref
->max_size
;
1694 /* If we cannot constrain the size of the reference we cannot
1695 test if anything kills it. */
1699 /* We can't deduce anything useful from clobbers. */
1700 if (gimple_clobber_p (def_stmt
))
1703 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1704 from that definition.
1706 if (is_gimple_reg_type (vr
->type
)
1707 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1708 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1709 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1710 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1712 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1714 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1715 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1716 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1717 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1718 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1720 && operand_equal_p (base
, base2
, 0)
1721 && offset2
<= offset
1722 && offset2
+ size2
>= offset
+ maxsize
)
1724 tree val
= build_zero_cst (vr
->type
);
1725 return vn_reference_lookup_or_insert_for_pieces
1726 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1730 /* 2) Assignment from an empty CONSTRUCTOR. */
1731 else if (is_gimple_reg_type (vr
->type
)
1732 && gimple_assign_single_p (def_stmt
)
1733 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1734 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1737 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1738 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1739 &offset2
, &size2
, &maxsize2
);
1741 && operand_equal_p (base
, base2
, 0)
1742 && offset2
<= offset
1743 && offset2
+ size2
>= offset
+ maxsize
)
1745 tree val
= build_zero_cst (vr
->type
);
1746 return vn_reference_lookup_or_insert_for_pieces
1747 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1751 /* 3) Assignment from a constant. We can use folds native encode/interpret
1752 routines to extract the assigned bits. */
1753 else if (vn_walk_kind
== VN_WALKREWRITE
1754 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1755 && ref
->size
== maxsize
1756 && maxsize
% BITS_PER_UNIT
== 0
1757 && offset
% BITS_PER_UNIT
== 0
1758 && is_gimple_reg_type (vr
->type
)
1759 && gimple_assign_single_p (def_stmt
)
1760 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1763 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1764 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1765 &offset2
, &size2
, &maxsize2
);
1767 && maxsize2
== size2
1768 && size2
% BITS_PER_UNIT
== 0
1769 && offset2
% BITS_PER_UNIT
== 0
1770 && operand_equal_p (base
, base2
, 0)
1771 && offset2
<= offset
1772 && offset2
+ size2
>= offset
+ maxsize
)
1774 /* We support up to 512-bit values (for V8DFmode). */
1775 unsigned char buffer
[64];
1778 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1779 buffer
, sizeof (buffer
));
1782 tree val
= native_interpret_expr (vr
->type
,
1784 + ((offset
- offset2
)
1786 ref
->size
/ BITS_PER_UNIT
);
1788 return vn_reference_lookup_or_insert_for_pieces
1789 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1794 /* 4) Assignment from an SSA name which definition we may be able
1795 to access pieces from. */
1796 else if (ref
->size
== maxsize
1797 && is_gimple_reg_type (vr
->type
)
1798 && gimple_assign_single_p (def_stmt
)
1799 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1801 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1802 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1803 if (is_gimple_assign (def_stmt2
)
1804 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1805 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1806 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1809 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1810 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1811 &offset2
, &size2
, &maxsize2
);
1812 off
= offset
- offset2
;
1814 && maxsize2
== size2
1815 && operand_equal_p (base
, base2
, 0)
1816 && offset2
<= offset
1817 && offset2
+ size2
>= offset
+ maxsize
)
1819 tree val
= NULL_TREE
;
1821 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1822 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1825 val
= gimple_assign_rhs1 (def_stmt2
);
1826 else if (off
== elsz
)
1827 val
= gimple_assign_rhs2 (def_stmt2
);
1829 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1832 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1833 unsigned i
= off
/ elsz
;
1834 if (i
< CONSTRUCTOR_NELTS (ctor
))
1836 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1837 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1839 if (TREE_CODE (TREE_TYPE (elt
->value
))
1846 return vn_reference_lookup_or_insert_for_pieces
1847 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1852 /* 5) For aggregate copies translate the reference through them if
1853 the copy kills ref. */
1854 else if (vn_walk_kind
== VN_WALKREWRITE
1855 && gimple_assign_single_p (def_stmt
)
1856 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1857 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1858 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1861 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1863 auto_vec
<vn_reference_op_s
> rhs
;
1864 vn_reference_op_t vro
;
1870 /* See if the assignment kills REF. */
1871 base2
= ao_ref_base (&lhs_ref
);
1872 offset2
= lhs_ref
.offset
;
1873 size2
= lhs_ref
.size
;
1874 maxsize2
= lhs_ref
.max_size
;
1876 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1878 || offset2
+ size2
< offset
+ maxsize
)
1881 /* Find the common base of ref and the lhs. lhs_ops already
1882 contains valueized operands for the lhs. */
1883 i
= vr
->operands
.length () - 1;
1884 j
= lhs_ops
.length () - 1;
1885 while (j
>= 0 && i
>= 0
1886 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1892 /* ??? The innermost op should always be a MEM_REF and we already
1893 checked that the assignment to the lhs kills vr. Thus for
1894 aggregate copies using char[] types the vn_reference_op_eq
1895 may fail when comparing types for compatibility. But we really
1896 don't care here - further lookups with the rewritten operands
1897 will simply fail if we messed up types too badly. */
1898 HOST_WIDE_INT extra_off
= 0;
1899 if (j
== 0 && i
>= 0
1900 && lhs_ops
[0].opcode
== MEM_REF
1901 && lhs_ops
[0].off
!= -1)
1903 if (lhs_ops
[0].off
== vr
->operands
[i
].off
)
1905 else if (vr
->operands
[i
].opcode
== MEM_REF
1906 && vr
->operands
[i
].off
!= -1)
1908 extra_off
= vr
->operands
[i
].off
- lhs_ops
[0].off
;
1913 /* i now points to the first additional op.
1914 ??? LHS may not be completely contained in VR, one or more
1915 VIEW_CONVERT_EXPRs could be in its way. We could at least
1916 try handling outermost VIEW_CONVERT_EXPRs. */
1920 /* Now re-write REF to be based on the rhs of the assignment. */
1921 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1923 /* Apply an extra offset to the inner MEM_REF of the RHS. */
1926 if (rhs
.length () < 2
1927 || rhs
[0].opcode
!= MEM_REF
1928 || rhs
[0].off
== -1)
1930 rhs
[0].off
+= extra_off
;
1931 rhs
[0].op0
= int_const_binop (PLUS_EXPR
, rhs
[0].op0
,
1932 build_int_cst (TREE_TYPE (rhs
[0].op0
),
1936 /* We need to pre-pend vr->operands[0..i] to rhs. */
1937 vec
<vn_reference_op_s
> old
= vr
->operands
;
1938 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1940 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1941 if (old
== shared_lookup_references
)
1942 shared_lookup_references
= vr
->operands
;
1945 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1946 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1947 vr
->operands
[i
+ 1 + j
] = *vro
;
1948 vr
->operands
= valueize_refs (vr
->operands
);
1949 if (old
== shared_lookup_references
)
1950 shared_lookup_references
= vr
->operands
;
1951 vr
->hashcode
= vn_reference_compute_hash (vr
);
1953 /* Try folding the new reference to a constant. */
1954 tree val
= fully_constant_vn_reference_p (vr
);
1956 return vn_reference_lookup_or_insert_for_pieces
1957 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1959 /* Adjust *ref from the new operands. */
1960 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1962 /* This can happen with bitfields. */
1963 if (ref
->size
!= r
.size
)
1967 /* Do not update last seen VUSE after translating. */
1968 last_vuse_ptr
= NULL
;
1970 /* Keep looking for the adjusted *REF / VR pair. */
1974 /* 6) For memcpy copies translate the reference through them if
1975 the copy kills ref. */
1976 else if (vn_walk_kind
== VN_WALKREWRITE
1977 && is_gimple_reg_type (vr
->type
)
1978 /* ??? Handle BCOPY as well. */
1979 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1980 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1981 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1982 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1983 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1984 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1985 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1986 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
1990 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1991 vn_reference_op_s op
;
1995 /* Only handle non-variable, addressable refs. */
1996 if (ref
->size
!= maxsize
1997 || offset
% BITS_PER_UNIT
!= 0
1998 || ref
->size
% BITS_PER_UNIT
!= 0)
2001 /* Extract a pointer base and an offset for the destination. */
2002 lhs
= gimple_call_arg (def_stmt
, 0);
2004 if (TREE_CODE (lhs
) == SSA_NAME
)
2005 lhs
= SSA_VAL (lhs
);
2006 if (TREE_CODE (lhs
) == ADDR_EXPR
)
2008 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
2012 if (TREE_CODE (tem
) == MEM_REF
2013 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
2015 lhs
= TREE_OPERAND (tem
, 0);
2016 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
2018 else if (DECL_P (tem
))
2019 lhs
= build_fold_addr_expr (tem
);
2023 if (TREE_CODE (lhs
) != SSA_NAME
2024 && TREE_CODE (lhs
) != ADDR_EXPR
)
2027 /* Extract a pointer base and an offset for the source. */
2028 rhs
= gimple_call_arg (def_stmt
, 1);
2030 if (TREE_CODE (rhs
) == SSA_NAME
)
2031 rhs
= SSA_VAL (rhs
);
2032 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2034 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
2038 if (TREE_CODE (tem
) == MEM_REF
2039 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
2041 rhs
= TREE_OPERAND (tem
, 0);
2042 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
2044 else if (DECL_P (tem
))
2045 rhs
= build_fold_addr_expr (tem
);
2049 if (TREE_CODE (rhs
) != SSA_NAME
2050 && TREE_CODE (rhs
) != ADDR_EXPR
)
2053 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
2055 /* The bases of the destination and the references have to agree. */
2056 if ((TREE_CODE (base
) != MEM_REF
2058 || (TREE_CODE (base
) == MEM_REF
2059 && (TREE_OPERAND (base
, 0) != lhs
2060 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
2062 && (TREE_CODE (lhs
) != ADDR_EXPR
2063 || TREE_OPERAND (lhs
, 0) != base
)))
2066 /* And the access has to be contained within the memcpy destination. */
2067 at
= offset
/ BITS_PER_UNIT
;
2068 if (TREE_CODE (base
) == MEM_REF
)
2069 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
2071 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
2074 /* Make room for 2 operands in the new reference. */
2075 if (vr
->operands
.length () < 2)
2077 vec
<vn_reference_op_s
> old
= vr
->operands
;
2078 vr
->operands
.safe_grow_cleared (2);
2079 if (old
== shared_lookup_references
2080 && vr
->operands
!= old
)
2081 shared_lookup_references
= vr
->operands
;
2084 vr
->operands
.truncate (2);
2086 /* The looked-through reference is a simple MEM_REF. */
2087 memset (&op
, 0, sizeof (op
));
2089 op
.opcode
= MEM_REF
;
2090 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
2091 op
.off
= at
- lhs_offset
+ rhs_offset
;
2092 vr
->operands
[0] = op
;
2093 op
.type
= TREE_TYPE (rhs
);
2094 op
.opcode
= TREE_CODE (rhs
);
2097 vr
->operands
[1] = op
;
2098 vr
->hashcode
= vn_reference_compute_hash (vr
);
2100 /* Adjust *ref from the new operands. */
2101 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2103 /* This can happen with bitfields. */
2104 if (ref
->size
!= r
.size
)
2108 /* Do not update last seen VUSE after translating. */
2109 last_vuse_ptr
= NULL
;
2111 /* Keep looking for the adjusted *REF / VR pair. */
2115 /* Bail out and stop walking. */
2119 /* Lookup a reference operation by it's parts, in the current hash table.
2120 Returns the resulting value number if it exists in the hash table,
2121 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2122 vn_reference_t stored in the hashtable if something is found. */
2125 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2126 vec
<vn_reference_op_s
> operands
,
2127 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2129 struct vn_reference_s vr1
;
2137 vr1
.vuse
= vuse_ssa_val (vuse
);
2138 shared_lookup_references
.truncate (0);
2139 shared_lookup_references
.safe_grow (operands
.length ());
2140 memcpy (shared_lookup_references
.address (),
2141 operands
.address (),
2142 sizeof (vn_reference_op_s
)
2143 * operands
.length ());
2144 vr1
.operands
= operands
= shared_lookup_references
2145 = valueize_refs (shared_lookup_references
);
2148 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2149 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2152 vn_reference_lookup_1 (&vr1
, vnresult
);
2154 && kind
!= VN_NOWALK
2158 vn_walk_kind
= kind
;
2159 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2161 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2162 vn_reference_lookup_2
,
2163 vn_reference_lookup_3
, &vr1
);
2164 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2168 return (*vnresult
)->result
;
2173 /* Lookup OP in the current hash table, and return the resulting value
2174 number if it exists in the hash table. Return NULL_TREE if it does
2175 not exist in the hash table or if the result field of the structure
2176 was NULL.. VNRESULT will be filled in with the vn_reference_t
2177 stored in the hashtable if one exists. */
2180 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2181 vn_reference_t
*vnresult
)
2183 vec
<vn_reference_op_s
> operands
;
2184 struct vn_reference_s vr1
;
2186 bool valuezied_anything
;
2191 vr1
.vuse
= vuse_ssa_val (vuse
);
2192 vr1
.operands
= operands
2193 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2194 vr1
.type
= TREE_TYPE (op
);
2195 vr1
.set
= get_alias_set (op
);
2196 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2197 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2200 if (kind
!= VN_NOWALK
2203 vn_reference_t wvnresult
;
2205 /* Make sure to use a valueized reference if we valueized anything.
2206 Otherwise preserve the full reference for advanced TBAA. */
2207 if (!valuezied_anything
2208 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2210 ao_ref_init (&r
, op
);
2211 vn_walk_kind
= kind
;
2213 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2214 vn_reference_lookup_2
,
2215 vn_reference_lookup_3
, &vr1
);
2216 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2220 *vnresult
= wvnresult
;
2221 return wvnresult
->result
;
2227 return vn_reference_lookup_1 (&vr1
, vnresult
);
2230 /* Lookup CALL in the current hash table and return the entry in
2231 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2234 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
2240 tree vuse
= gimple_vuse (call
);
2242 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2243 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
2244 vr
->type
= gimple_expr_type (call
);
2246 vr
->hashcode
= vn_reference_compute_hash (vr
);
2247 vn_reference_lookup_1 (vr
, vnresult
);
2250 /* Insert OP into the current hash table with a value number of
2251 RESULT, and return the resulting reference structure we created. */
2253 static vn_reference_t
2254 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2256 vn_reference_s
**slot
;
2260 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2261 if (TREE_CODE (result
) == SSA_NAME
)
2262 vr1
->value_id
= VN_INFO (result
)->value_id
;
2264 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2265 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2266 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2267 vr1
->type
= TREE_TYPE (op
);
2268 vr1
->set
= get_alias_set (op
);
2269 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2270 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2271 vr1
->result_vdef
= vdef
;
2273 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2276 /* Because we lookup stores using vuses, and value number failures
2277 using the vdefs (see visit_reference_op_store for how and why),
2278 it's possible that on failure we may try to insert an already
2279 inserted store. This is not wrong, there is no ssa name for a
2280 store that we could use as a differentiator anyway. Thus, unlike
2281 the other lookup functions, you cannot gcc_assert (!*slot)
2284 /* But free the old slot in case of a collision. */
2286 free_reference (*slot
);
2292 /* Insert a reference by it's pieces into the current hash table with
2293 a value number of RESULT. Return the resulting reference
2294 structure we created. */
2297 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2298 vec
<vn_reference_op_s
> operands
,
2299 tree result
, unsigned int value_id
)
2302 vn_reference_s
**slot
;
2305 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2306 vr1
->value_id
= value_id
;
2307 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2308 vr1
->operands
= valueize_refs (operands
);
2311 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2312 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2313 result
= SSA_VAL (result
);
2314 vr1
->result
= result
;
2316 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2319 /* At this point we should have all the things inserted that we have
2320 seen before, and we should never try inserting something that
2322 gcc_assert (!*slot
);
2324 free_reference (*slot
);
2330 /* Compute and return the hash value for nary operation VBO1. */
2333 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2335 inchash::hash hstate
;
2338 for (i
= 0; i
< vno1
->length
; ++i
)
2339 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2340 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2342 if (vno1
->length
== 2
2343 && commutative_tree_code (vno1
->opcode
)
2344 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2346 tree temp
= vno1
->op
[0];
2347 vno1
->op
[0] = vno1
->op
[1];
2351 hstate
.add_int (vno1
->opcode
);
2352 for (i
= 0; i
< vno1
->length
; ++i
)
2353 inchash::add_expr (vno1
->op
[i
], hstate
);
2355 return hstate
.end ();
2358 /* Compare nary operations VNO1 and VNO2 and return true if they are
2362 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2366 if (vno1
->hashcode
!= vno2
->hashcode
)
2369 if (vno1
->length
!= vno2
->length
)
2372 if (vno1
->opcode
!= vno2
->opcode
2373 || !types_compatible_p (vno1
->type
, vno2
->type
))
2376 for (i
= 0; i
< vno1
->length
; ++i
)
2377 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2383 /* Initialize VNO from the pieces provided. */
2386 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2387 enum tree_code code
, tree type
, tree
*ops
)
2390 vno
->length
= length
;
2392 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2395 /* Initialize VNO from OP. */
2398 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2402 vno
->opcode
= TREE_CODE (op
);
2403 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2404 vno
->type
= TREE_TYPE (op
);
2405 for (i
= 0; i
< vno
->length
; ++i
)
2406 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2409 /* Return the number of operands for a vn_nary ops structure from STMT. */
2412 vn_nary_length_from_stmt (gimple stmt
)
2414 switch (gimple_assign_rhs_code (stmt
))
2418 case VIEW_CONVERT_EXPR
:
2425 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2428 return gimple_num_ops (stmt
) - 1;
2432 /* Initialize VNO from STMT. */
2435 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2439 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2440 vno
->type
= gimple_expr_type (stmt
);
2441 switch (vno
->opcode
)
2445 case VIEW_CONVERT_EXPR
:
2447 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2452 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2453 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2454 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2458 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2459 for (i
= 0; i
< vno
->length
; ++i
)
2460 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2464 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2465 vno
->length
= gimple_num_ops (stmt
) - 1;
2466 for (i
= 0; i
< vno
->length
; ++i
)
2467 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2471 /* Compute the hashcode for VNO and look for it in the hash table;
2472 return the resulting value number if it exists in the hash table.
2473 Return NULL_TREE if it does not exist in the hash table or if the
2474 result field of the operation is NULL. VNRESULT will contain the
2475 vn_nary_op_t from the hashtable if it exists. */
2478 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2480 vn_nary_op_s
**slot
;
2485 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2486 slot
= current_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2488 if (!slot
&& current_info
== optimistic_info
)
2489 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2495 return (*slot
)->result
;
2498 /* Lookup a n-ary operation by its pieces and return the resulting value
2499 number if it exists in the hash table. Return NULL_TREE if it does
2500 not exist in the hash table or if the result field of the operation
2501 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2505 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2506 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2508 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2509 sizeof_vn_nary_op (length
));
2510 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2511 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2514 /* Lookup OP in the current hash table, and return the resulting value
2515 number if it exists in the hash table. Return NULL_TREE if it does
2516 not exist in the hash table or if the result field of the operation
2517 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2521 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2524 = XALLOCAVAR (struct vn_nary_op_s
,
2525 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2526 init_vn_nary_op_from_op (vno1
, op
);
2527 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2530 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2531 value number if it exists in the hash table. Return NULL_TREE if
2532 it does not exist in the hash table. VNRESULT will contain the
2533 vn_nary_op_t from the hashtable if it exists. */
2536 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2539 = XALLOCAVAR (struct vn_nary_op_s
,
2540 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2541 init_vn_nary_op_from_stmt (vno1
, stmt
);
2542 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2545 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2548 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2550 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2553 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2557 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2559 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2560 ¤t_info
->nary_obstack
);
2562 vno1
->value_id
= value_id
;
2563 vno1
->length
= length
;
2564 vno1
->result
= result
;
2569 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2570 VNO->HASHCODE first. */
2573 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
2576 vn_nary_op_s
**slot
;
2579 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2581 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2582 gcc_assert (!*slot
);
2588 /* Insert a n-ary operation into the current hash table using it's
2589 pieces. Return the vn_nary_op_t structure we created and put in
2593 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2594 tree type
, tree
*ops
,
2595 tree result
, unsigned int value_id
)
2597 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2598 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2599 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2602 /* Insert OP into the current hash table with a value number of
2603 RESULT. Return the vn_nary_op_t structure we created and put in
2607 vn_nary_op_insert (tree op
, tree result
)
2609 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2612 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2613 init_vn_nary_op_from_op (vno1
, op
);
2614 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2617 /* Insert the rhs of STMT into the current hash table with a value number of
2621 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2624 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2625 result
, VN_INFO (result
)->value_id
);
2626 init_vn_nary_op_from_stmt (vno1
, stmt
);
2627 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2630 /* Compute a hashcode for PHI operation VP1 and return it. */
2632 static inline hashval_t
2633 vn_phi_compute_hash (vn_phi_t vp1
)
2635 inchash::hash
hstate (vp1
->block
->index
);
2640 /* If all PHI arguments are constants we need to distinguish
2641 the PHI node via its type. */
2643 hstate
.merge_hash (vn_hash_type (type
));
2645 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2647 if (phi1op
== VN_TOP
)
2649 inchash::add_expr (phi1op
, hstate
);
2652 return hstate
.end ();
2655 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2658 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2660 if (vp1
->hashcode
!= vp2
->hashcode
)
2663 if (vp1
->block
== vp2
->block
)
2668 /* If the PHI nodes do not have compatible types
2669 they are not the same. */
2670 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2673 /* Any phi in the same block will have it's arguments in the
2674 same edge order, because of how we store phi nodes. */
2675 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2677 tree phi2op
= vp2
->phiargs
[i
];
2678 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2680 if (!expressions_equal_p (phi1op
, phi2op
))
2688 static vec
<tree
> shared_lookup_phiargs
;
2690 /* Lookup PHI in the current hash table, and return the resulting
2691 value number if it exists in the hash table. Return NULL_TREE if
2692 it does not exist in the hash table. */
2695 vn_phi_lookup (gimple phi
)
2698 struct vn_phi_s vp1
;
2701 shared_lookup_phiargs
.truncate (0);
2703 /* Canonicalize the SSA_NAME's to their value number. */
2704 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2706 tree def
= PHI_ARG_DEF (phi
, i
);
2707 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2708 shared_lookup_phiargs
.safe_push (def
);
2710 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2711 vp1
.phiargs
= shared_lookup_phiargs
;
2712 vp1
.block
= gimple_bb (phi
);
2713 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2714 slot
= current_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2716 if (!slot
&& current_info
== optimistic_info
)
2717 slot
= valid_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2721 return (*slot
)->result
;
2724 /* Insert PHI into the current hash table with a value number of
2728 vn_phi_insert (gimple phi
, tree result
)
2731 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2733 vec
<tree
> args
= vNULL
;
2735 /* Canonicalize the SSA_NAME's to their value number. */
2736 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2738 tree def
= PHI_ARG_DEF (phi
, i
);
2739 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2740 args
.safe_push (def
);
2742 vp1
->value_id
= VN_INFO (result
)->value_id
;
2743 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2744 vp1
->phiargs
= args
;
2745 vp1
->block
= gimple_bb (phi
);
2746 vp1
->result
= result
;
2747 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2749 slot
= current_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2751 /* Because we iterate over phi operations more than once, it's
2752 possible the slot might already exist here, hence no assert.*/
2758 /* Print set of components in strongly connected component SCC to OUT. */
2761 print_scc (FILE *out
, vec
<tree
> scc
)
2766 fprintf (out
, "SCC consists of:");
2767 FOR_EACH_VEC_ELT (scc
, i
, var
)
2770 print_generic_expr (out
, var
, 0);
2772 fprintf (out
, "\n");
2775 /* Set the value number of FROM to TO, return true if it has changed
2779 set_ssa_val_to (tree from
, tree to
)
2781 tree currval
= SSA_VAL (from
);
2782 HOST_WIDE_INT toff
, coff
;
2784 /* The only thing we allow as value numbers are ssa_names
2785 and invariants. So assert that here. We don't allow VN_TOP
2786 as visiting a stmt should produce a value-number other than
2788 ??? Still VN_TOP can happen for unreachable code, so force
2789 it to varying in that case. Not all code is prepared to
2790 get VN_TOP on valueization. */
2793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2794 fprintf (dump_file
, "Forcing value number to varying on "
2795 "receiving VN_TOP\n");
2799 gcc_assert (to
!= NULL_TREE
2800 && (TREE_CODE (to
) == SSA_NAME
2801 || is_gimple_min_invariant (to
)));
2805 if (currval
== from
)
2807 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2809 fprintf (dump_file
, "Not changing value number of ");
2810 print_generic_expr (dump_file
, from
, 0);
2811 fprintf (dump_file
, " from VARYING to ");
2812 print_generic_expr (dump_file
, to
, 0);
2813 fprintf (dump_file
, "\n");
2817 else if (TREE_CODE (to
) == SSA_NAME
2818 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2824 fprintf (dump_file
, "Setting value number of ");
2825 print_generic_expr (dump_file
, from
, 0);
2826 fprintf (dump_file
, " to ");
2827 print_generic_expr (dump_file
, to
, 0);
2831 && !operand_equal_p (currval
, to
, 0)
2832 /* ??? For addresses involving volatile objects or types operand_equal_p
2833 does not reliably detect ADDR_EXPRs as equal. We know we are only
2834 getting invariant gimple addresses here, so can use
2835 get_addr_base_and_unit_offset to do this comparison. */
2836 && !(TREE_CODE (currval
) == ADDR_EXPR
2837 && TREE_CODE (to
) == ADDR_EXPR
2838 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2839 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2842 VN_INFO (from
)->valnum
= to
;
2843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2844 fprintf (dump_file
, " (changed)\n");
2847 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2848 fprintf (dump_file
, "\n");
2852 /* Mark as processed all the definitions in the defining stmt of USE, or
2856 mark_use_processed (tree use
)
2860 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2862 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2864 VN_INFO (use
)->use_processed
= true;
2868 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2870 tree def
= DEF_FROM_PTR (defp
);
2872 VN_INFO (def
)->use_processed
= true;
2876 /* Set all definitions in STMT to value number to themselves.
2877 Return true if a value number changed. */
2880 defs_to_varying (gimple stmt
)
2882 bool changed
= false;
2886 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2888 tree def
= DEF_FROM_PTR (defp
);
2889 changed
|= set_ssa_val_to (def
, def
);
2894 static bool expr_has_constants (tree expr
);
2896 /* Visit a copy between LHS and RHS, return true if the value number
2900 visit_copy (tree lhs
, tree rhs
)
2902 /* The copy may have a more interesting constant filled expression
2903 (we don't, since we know our RHS is just an SSA name). */
2904 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2905 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2907 /* And finally valueize. */
2908 rhs
= SSA_VAL (rhs
);
2910 return set_ssa_val_to (lhs
, rhs
);
2913 /* Visit a nary operator RHS, value number it, and return true if the
2914 value number of LHS has changed as a result. */
2917 visit_nary_op (tree lhs
, gimple stmt
)
2919 bool changed
= false;
2920 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2923 changed
= set_ssa_val_to (lhs
, result
);
2926 changed
= set_ssa_val_to (lhs
, lhs
);
2927 vn_nary_op_insert_stmt (stmt
, lhs
);
2933 /* Visit a call STMT storing into LHS. Return true if the value number
2934 of the LHS has changed as a result. */
2937 visit_reference_op_call (tree lhs
, gcall
*stmt
)
2939 bool changed
= false;
2940 struct vn_reference_s vr1
;
2941 vn_reference_t vnresult
= NULL
;
2942 tree vdef
= gimple_vdef (stmt
);
2944 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2945 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2948 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
2951 if (vnresult
->result_vdef
&& vdef
)
2952 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2954 if (!vnresult
->result
&& lhs
)
2955 vnresult
->result
= lhs
;
2957 if (vnresult
->result
&& lhs
)
2959 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2961 if (VN_INFO (vnresult
->result
)->has_constants
)
2962 VN_INFO (lhs
)->has_constants
= true;
2968 vn_reference_s
**slot
;
2970 changed
|= set_ssa_val_to (vdef
, vdef
);
2972 changed
|= set_ssa_val_to (lhs
, lhs
);
2973 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2974 vr2
->vuse
= vr1
.vuse
;
2975 /* As we are not walking the virtual operand chain we know the
2976 shared_lookup_references are still original so we can re-use
2978 vr2
->operands
= vr1
.operands
.copy ();
2979 vr2
->type
= vr1
.type
;
2981 vr2
->hashcode
= vr1
.hashcode
;
2983 vr2
->result_vdef
= vdef
;
2984 slot
= current_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
2986 gcc_assert (!*slot
);
2993 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2994 and return true if the value number of the LHS has changed as a result. */
2997 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2999 bool changed
= false;
3003 last_vuse
= gimple_vuse (stmt
);
3004 last_vuse_ptr
= &last_vuse
;
3005 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
3006 default_vn_walk_kind
, NULL
);
3007 last_vuse_ptr
= NULL
;
3009 /* We handle type-punning through unions by value-numbering based
3010 on offset and size of the access. Be prepared to handle a
3011 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
3013 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
3015 /* We will be setting the value number of lhs to the value number
3016 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
3017 So first simplify and lookup this expression to see if it
3018 is already available. */
3019 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
3020 if ((CONVERT_EXPR_P (val
)
3021 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
3022 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
3024 tree tem
= vn_get_expr_for (TREE_OPERAND (val
, 0));
3025 if ((CONVERT_EXPR_P (tem
)
3026 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
3027 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
3028 TREE_TYPE (val
), tem
)))
3032 if (!is_gimple_min_invariant (val
)
3033 && TREE_CODE (val
) != SSA_NAME
)
3034 result
= vn_nary_op_lookup (val
, NULL
);
3035 /* If the expression is not yet available, value-number lhs to
3036 a new SSA_NAME we create. */
3039 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
3041 /* Initialize value-number information properly. */
3042 VN_INFO_GET (result
)->valnum
= result
;
3043 VN_INFO (result
)->value_id
= get_next_value_id ();
3044 VN_INFO (result
)->expr
= val
;
3045 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
3046 VN_INFO (result
)->needs_insertion
= true;
3047 /* As all "inserted" statements are singleton SCCs, insert
3048 to the valid table. This is strictly needed to
3049 avoid re-generating new value SSA_NAMEs for the same
3050 expression during SCC iteration over and over (the
3051 optimistic table gets cleared after each iteration).
3052 We do not need to insert into the optimistic table, as
3053 lookups there will fall back to the valid table. */
3054 if (current_info
== optimistic_info
)
3056 current_info
= valid_info
;
3057 vn_nary_op_insert (val
, result
);
3058 current_info
= optimistic_info
;
3061 vn_nary_op_insert (val
, result
);
3062 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3064 fprintf (dump_file
, "Inserting name ");
3065 print_generic_expr (dump_file
, result
, 0);
3066 fprintf (dump_file
, " for expression ");
3067 print_generic_expr (dump_file
, val
, 0);
3068 fprintf (dump_file
, "\n");
3075 changed
= set_ssa_val_to (lhs
, result
);
3076 if (TREE_CODE (result
) == SSA_NAME
3077 && VN_INFO (result
)->has_constants
)
3079 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
3080 VN_INFO (lhs
)->has_constants
= true;
3085 changed
= set_ssa_val_to (lhs
, lhs
);
3086 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
3093 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3094 and return true if the value number of the LHS has changed as a result. */
3097 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
3099 bool changed
= false;
3100 vn_reference_t vnresult
= NULL
;
3101 tree result
, assign
;
3102 bool resultsame
= false;
3103 tree vuse
= gimple_vuse (stmt
);
3104 tree vdef
= gimple_vdef (stmt
);
3106 /* First we want to lookup using the *vuses* from the store and see
3107 if there the last store to this location with the same address
3110 The vuses represent the memory state before the store. If the
3111 memory state, address, and value of the store is the same as the
3112 last store to this location, then this store will produce the
3113 same memory state as that store.
3115 In this case the vdef versions for this store are value numbered to those
3116 vuse versions, since they represent the same memory state after
3119 Otherwise, the vdefs for the store are used when inserting into
3120 the table, since the store generates a new memory state. */
3122 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
3126 if (TREE_CODE (result
) == SSA_NAME
)
3127 result
= SSA_VAL (result
);
3128 if (TREE_CODE (op
) == SSA_NAME
)
3130 resultsame
= expressions_equal_p (result
, op
);
3133 if ((!result
|| !resultsame
)
3134 /* Only perform the following when being called from PRE
3135 which embeds tail merging. */
3136 && default_vn_walk_kind
== VN_WALK
)
3138 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3139 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
3142 VN_INFO (vdef
)->use_processed
= true;
3143 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3147 if (!result
|| !resultsame
)
3149 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3151 fprintf (dump_file
, "No store match\n");
3152 fprintf (dump_file
, "Value numbering store ");
3153 print_generic_expr (dump_file
, lhs
, 0);
3154 fprintf (dump_file
, " to ");
3155 print_generic_expr (dump_file
, op
, 0);
3156 fprintf (dump_file
, "\n");
3158 /* Have to set value numbers before insert, since insert is
3159 going to valueize the references in-place. */
3162 changed
|= set_ssa_val_to (vdef
, vdef
);
3165 /* Do not insert structure copies into the tables. */
3166 if (is_gimple_min_invariant (op
)
3167 || is_gimple_reg (op
))
3168 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3170 /* Only perform the following when being called from PRE
3171 which embeds tail merging. */
3172 if (default_vn_walk_kind
== VN_WALK
)
3174 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3175 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3180 /* We had a match, so value number the vdef to have the value
3181 number of the vuse it came from. */
3183 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3184 fprintf (dump_file
, "Store matched earlier value,"
3185 "value numbering store vdefs to matching vuses.\n");
3187 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3193 /* Visit and value number PHI, return true if the value number
3197 visit_phi (gimple phi
)
3199 bool changed
= false;
3201 tree sameval
= VN_TOP
;
3202 bool allsame
= true;
3204 /* TODO: We could check for this in init_sccvn, and replace this
3205 with a gcc_assert. */
3206 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3207 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3209 /* See if all non-TOP arguments have the same value. TOP is
3210 equivalent to everything, so we can ignore it. */
3213 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3214 if (e
->flags
& EDGE_EXECUTABLE
)
3216 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3218 if (TREE_CODE (def
) == SSA_NAME
)
3219 def
= SSA_VAL (def
);
3222 if (sameval
== VN_TOP
)
3228 if (!expressions_equal_p (def
, sameval
))
3236 /* If all value numbered to the same value, the phi node has that
3239 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3241 /* Otherwise, see if it is equivalent to a phi node in this block. */
3242 result
= vn_phi_lookup (phi
);
3244 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3247 vn_phi_insert (phi
, PHI_RESULT (phi
));
3248 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3249 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3250 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3256 /* Return true if EXPR contains constants. */
3259 expr_has_constants (tree expr
)
3261 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3264 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3267 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3268 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3269 /* Constants inside reference ops are rarely interesting, but
3270 it can take a lot of looking to find them. */
3272 case tcc_declaration
:
3275 return is_gimple_min_invariant (expr
);
3280 /* Return true if STMT contains constants. */
3283 stmt_has_constants (gimple stmt
)
3287 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3290 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3292 case GIMPLE_TERNARY_RHS
:
3293 tem
= gimple_assign_rhs3 (stmt
);
3294 if (TREE_CODE (tem
) == SSA_NAME
)
3295 tem
= SSA_VAL (tem
);
3296 if (is_gimple_min_invariant (tem
))
3300 case GIMPLE_BINARY_RHS
:
3301 tem
= gimple_assign_rhs2 (stmt
);
3302 if (TREE_CODE (tem
) == SSA_NAME
)
3303 tem
= SSA_VAL (tem
);
3304 if (is_gimple_min_invariant (tem
))
3308 case GIMPLE_SINGLE_RHS
:
3309 /* Constants inside reference ops are rarely interesting, but
3310 it can take a lot of looking to find them. */
3311 case GIMPLE_UNARY_RHS
:
3312 tem
= gimple_assign_rhs1 (stmt
);
3313 if (TREE_CODE (tem
) == SSA_NAME
)
3314 tem
= SSA_VAL (tem
);
3315 return is_gimple_min_invariant (tem
);
3323 /* Simplify the binary expression RHS, and return the result if
3327 simplify_binary_expression (gimple stmt
)
3329 tree result
= NULL_TREE
;
3330 tree op0
= gimple_assign_rhs1 (stmt
);
3331 tree op1
= gimple_assign_rhs2 (stmt
);
3332 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3334 /* This will not catch every single case we could combine, but will
3335 catch those with constants. The goal here is to simultaneously
3336 combine constants between expressions, but avoid infinite
3337 expansion of expressions during simplification. */
3338 op0
= vn_valueize (op0
);
3339 if (TREE_CODE (op0
) == SSA_NAME
3340 && (VN_INFO (op0
)->has_constants
3341 || TREE_CODE_CLASS (code
) == tcc_comparison
3342 || code
== COMPLEX_EXPR
))
3343 op0
= vn_get_expr_for (op0
);
3345 op1
= vn_valueize (op1
);
3346 if (TREE_CODE (op1
) == SSA_NAME
3347 && (VN_INFO (op1
)->has_constants
3348 || code
== COMPLEX_EXPR
))
3349 op1
= vn_get_expr_for (op1
);
3351 /* Pointer plus constant can be represented as invariant address.
3352 Do so to allow further propatation, see also tree forwprop. */
3353 if (code
== POINTER_PLUS_EXPR
3354 && tree_fits_uhwi_p (op1
)
3355 && TREE_CODE (op0
) == ADDR_EXPR
3356 && is_gimple_min_invariant (op0
))
3357 return build_invariant_address (TREE_TYPE (op0
),
3358 TREE_OPERAND (op0
, 0),
3359 tree_to_uhwi (op1
));
3361 /* Avoid folding if nothing changed. */
3362 if (op0
== gimple_assign_rhs1 (stmt
)
3363 && op1
== gimple_assign_rhs2 (stmt
))
3366 fold_defer_overflow_warnings ();
3368 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3370 STRIP_USELESS_TYPE_CONVERSION (result
);
3372 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3375 /* Make sure result is not a complex expression consisting
3376 of operators of operators (IE (a + b) + (a + c))
3377 Otherwise, we will end up with unbounded expressions if
3378 fold does anything at all. */
3379 if (result
&& valid_gimple_rhs_p (result
))
3385 /* Simplify the unary expression RHS, and return the result if
3389 simplify_unary_expression (gassign
*stmt
)
3391 tree result
= NULL_TREE
;
3392 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3393 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3395 /* We handle some tcc_reference codes here that are all
3396 GIMPLE_ASSIGN_SINGLE codes. */
3397 if (code
== REALPART_EXPR
3398 || code
== IMAGPART_EXPR
3399 || code
== VIEW_CONVERT_EXPR
3400 || code
== BIT_FIELD_REF
)
3401 op0
= TREE_OPERAND (op0
, 0);
3404 op0
= vn_valueize (op0
);
3405 if (TREE_CODE (op0
) == SSA_NAME
)
3407 if (VN_INFO (op0
)->has_constants
)
3408 op0
= vn_get_expr_for (op0
);
3409 else if (CONVERT_EXPR_CODE_P (code
)
3410 || code
== REALPART_EXPR
3411 || code
== IMAGPART_EXPR
3412 || code
== VIEW_CONVERT_EXPR
3413 || code
== BIT_FIELD_REF
)
3415 /* We want to do tree-combining on conversion-like expressions.
3416 Make sure we feed only SSA_NAMEs or constants to fold though. */
3417 tree tem
= vn_get_expr_for (op0
);
3418 if (UNARY_CLASS_P (tem
)
3419 || BINARY_CLASS_P (tem
)
3420 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3421 || TREE_CODE (tem
) == SSA_NAME
3422 || TREE_CODE (tem
) == CONSTRUCTOR
3423 || is_gimple_min_invariant (tem
))
3428 /* Avoid folding if nothing changed, but remember the expression. */
3429 if (op0
== orig_op0
)
3432 if (code
== BIT_FIELD_REF
)
3434 tree rhs
= gimple_assign_rhs1 (stmt
);
3435 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3436 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3439 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3442 STRIP_USELESS_TYPE_CONVERSION (result
);
3443 if (valid_gimple_rhs_p (result
))
3450 /* Try to simplify RHS using equivalences and constant folding. */
3453 try_to_simplify (gassign
*stmt
)
3455 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3458 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3459 in this case, there is no point in doing extra work. */
3460 if (code
== SSA_NAME
)
3463 /* First try constant folding based on our current lattice. */
3464 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
, vn_valueize
);
3466 && (TREE_CODE (tem
) == SSA_NAME
3467 || is_gimple_min_invariant (tem
)))
3470 /* If that didn't work try combining multiple statements. */
3471 switch (TREE_CODE_CLASS (code
))
3474 /* Fallthrough for some unary codes that can operate on registers. */
3475 if (!(code
== REALPART_EXPR
3476 || code
== IMAGPART_EXPR
3477 || code
== VIEW_CONVERT_EXPR
3478 || code
== BIT_FIELD_REF
))
3480 /* We could do a little more with unary ops, if they expand
3481 into binary ops, but it's debatable whether it is worth it. */
3483 return simplify_unary_expression (stmt
);
3485 case tcc_comparison
:
3487 return simplify_binary_expression (stmt
);
3496 /* Visit and value number USE, return true if the value number
3500 visit_use (tree use
)
3502 bool changed
= false;
3503 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3505 mark_use_processed (use
);
3507 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3508 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3509 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3511 fprintf (dump_file
, "Value numbering ");
3512 print_generic_expr (dump_file
, use
, 0);
3513 fprintf (dump_file
, " stmt = ");
3514 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3517 /* Handle uninitialized uses. */
3518 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3519 changed
= set_ssa_val_to (use
, use
);
3522 if (gimple_code (stmt
) == GIMPLE_PHI
)
3523 changed
= visit_phi (stmt
);
3524 else if (gimple_has_volatile_ops (stmt
))
3525 changed
= defs_to_varying (stmt
);
3526 else if (is_gimple_assign (stmt
))
3528 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3529 tree lhs
= gimple_assign_lhs (stmt
);
3530 tree rhs1
= gimple_assign_rhs1 (stmt
);
3533 /* Shortcut for copies. Simplifying copies is pointless,
3534 since we copy the expression and value they represent. */
3535 if (code
== SSA_NAME
3536 && TREE_CODE (lhs
) == SSA_NAME
)
3538 changed
= visit_copy (lhs
, rhs1
);
3541 simplified
= try_to_simplify (as_a
<gassign
*> (stmt
));
3544 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3546 fprintf (dump_file
, "RHS ");
3547 print_gimple_expr (dump_file
, stmt
, 0, 0);
3548 fprintf (dump_file
, " simplified to ");
3549 print_generic_expr (dump_file
, simplified
, 0);
3550 if (TREE_CODE (lhs
) == SSA_NAME
)
3551 fprintf (dump_file
, " has constants %d\n",
3552 expr_has_constants (simplified
));
3554 fprintf (dump_file
, "\n");
3557 /* Setting value numbers to constants will occasionally
3558 screw up phi congruence because constants are not
3559 uniquely associated with a single ssa name that can be
3562 && is_gimple_min_invariant (simplified
)
3563 && TREE_CODE (lhs
) == SSA_NAME
)
3565 VN_INFO (lhs
)->expr
= simplified
;
3566 VN_INFO (lhs
)->has_constants
= true;
3567 changed
= set_ssa_val_to (lhs
, simplified
);
3571 && TREE_CODE (simplified
) == SSA_NAME
3572 && TREE_CODE (lhs
) == SSA_NAME
)
3574 changed
= visit_copy (lhs
, simplified
);
3577 else if (simplified
)
3579 if (TREE_CODE (lhs
) == SSA_NAME
)
3581 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3582 /* We have to unshare the expression or else
3583 valuizing may change the IL stream. */
3584 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3587 else if (stmt_has_constants (stmt
)
3588 && TREE_CODE (lhs
) == SSA_NAME
)
3589 VN_INFO (lhs
)->has_constants
= true;
3590 else if (TREE_CODE (lhs
) == SSA_NAME
)
3592 /* We reset expr and constantness here because we may
3593 have been value numbering optimistically, and
3594 iterating. They may become non-constant in this case,
3595 even if they were optimistically constant. */
3597 VN_INFO (lhs
)->has_constants
= false;
3598 VN_INFO (lhs
)->expr
= NULL_TREE
;
3601 if ((TREE_CODE (lhs
) == SSA_NAME
3602 /* We can substitute SSA_NAMEs that are live over
3603 abnormal edges with their constant value. */
3604 && !(gimple_assign_copy_p (stmt
)
3605 && is_gimple_min_invariant (rhs1
))
3607 && is_gimple_min_invariant (simplified
))
3608 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3609 /* Stores or copies from SSA_NAMEs that are live over
3610 abnormal edges are a problem. */
3611 || (code
== SSA_NAME
3612 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3613 changed
= defs_to_varying (stmt
);
3614 else if (REFERENCE_CLASS_P (lhs
)
3616 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3617 else if (TREE_CODE (lhs
) == SSA_NAME
)
3619 if ((gimple_assign_copy_p (stmt
)
3620 && is_gimple_min_invariant (rhs1
))
3622 && is_gimple_min_invariant (simplified
)))
3624 VN_INFO (lhs
)->has_constants
= true;
3626 changed
= set_ssa_val_to (lhs
, simplified
);
3628 changed
= set_ssa_val_to (lhs
, rhs1
);
3632 /* First try to lookup the simplified expression. */
3635 enum gimple_rhs_class rhs_class
;
3638 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3639 if ((rhs_class
== GIMPLE_UNARY_RHS
3640 || rhs_class
== GIMPLE_BINARY_RHS
3641 || rhs_class
== GIMPLE_TERNARY_RHS
)
3642 && valid_gimple_rhs_p (simplified
))
3644 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3647 changed
= set_ssa_val_to (lhs
, result
);
3653 /* Otherwise visit the original statement. */
3654 switch (vn_get_stmt_kind (stmt
))
3657 changed
= visit_nary_op (lhs
, stmt
);
3660 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3663 changed
= defs_to_varying (stmt
);
3669 changed
= defs_to_varying (stmt
);
3671 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
3673 tree lhs
= gimple_call_lhs (stmt
);
3674 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3676 /* Try constant folding based on our current lattice. */
3677 tree simplified
= gimple_fold_stmt_to_constant_1 (stmt
,
3681 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3683 fprintf (dump_file
, "call ");
3684 print_gimple_expr (dump_file
, stmt
, 0, 0);
3685 fprintf (dump_file
, " simplified to ");
3686 print_generic_expr (dump_file
, simplified
, 0);
3687 if (TREE_CODE (lhs
) == SSA_NAME
)
3688 fprintf (dump_file
, " has constants %d\n",
3689 expr_has_constants (simplified
));
3691 fprintf (dump_file
, "\n");
3694 /* Setting value numbers to constants will occasionally
3695 screw up phi congruence because constants are not
3696 uniquely associated with a single ssa name that can be
3699 && is_gimple_min_invariant (simplified
))
3701 VN_INFO (lhs
)->expr
= simplified
;
3702 VN_INFO (lhs
)->has_constants
= true;
3703 changed
= set_ssa_val_to (lhs
, simplified
);
3704 if (gimple_vdef (stmt
))
3705 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3706 gimple_vuse (stmt
));
3710 && TREE_CODE (simplified
) == SSA_NAME
)
3712 changed
= visit_copy (lhs
, simplified
);
3713 if (gimple_vdef (stmt
))
3714 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3715 gimple_vuse (stmt
));
3720 if (stmt_has_constants (stmt
))
3721 VN_INFO (lhs
)->has_constants
= true;
3724 /* We reset expr and constantness here because we may
3725 have been value numbering optimistically, and
3726 iterating. They may become non-constant in this case,
3727 even if they were optimistically constant. */
3728 VN_INFO (lhs
)->has_constants
= false;
3729 VN_INFO (lhs
)->expr
= NULL_TREE
;
3732 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3734 changed
= defs_to_varying (stmt
);
3740 if (!gimple_call_internal_p (stmt
)
3741 && (/* Calls to the same function with the same vuse
3742 and the same operands do not necessarily return the same
3743 value, unless they're pure or const. */
3744 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3745 /* If calls have a vdef, subsequent calls won't have
3746 the same incoming vuse. So, if 2 calls with vdef have the
3747 same vuse, we know they're not subsequent.
3748 We can value number 2 calls to the same function with the
3749 same vuse and the same operands which are not subsequent
3750 the same, because there is no code in the program that can
3751 compare the 2 values... */
3752 || (gimple_vdef (stmt
)
3753 /* ... unless the call returns a pointer which does
3754 not alias with anything else. In which case the
3755 information that the values are distinct are encoded
3757 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
3758 /* Only perform the following when being called from PRE
3759 which embeds tail merging. */
3760 && default_vn_walk_kind
== VN_WALK
)))
3761 changed
= visit_reference_op_call (lhs
, call_stmt
);
3763 changed
= defs_to_varying (stmt
);
3766 changed
= defs_to_varying (stmt
);
3772 /* Compare two operands by reverse postorder index */
3775 compare_ops (const void *pa
, const void *pb
)
3777 const tree opa
= *((const tree
*)pa
);
3778 const tree opb
= *((const tree
*)pb
);
3779 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3780 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3784 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3785 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3786 else if (gimple_nop_p (opstmta
))
3788 else if (gimple_nop_p (opstmtb
))
3791 bba
= gimple_bb (opstmta
);
3792 bbb
= gimple_bb (opstmtb
);
3795 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3803 if (gimple_code (opstmta
) == GIMPLE_PHI
3804 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3805 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3806 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3808 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3810 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3811 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3813 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3815 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3818 /* Sort an array containing members of a strongly connected component
3819 SCC so that the members are ordered by RPO number.
3820 This means that when the sort is complete, iterating through the
3821 array will give you the members in RPO order. */
3824 sort_scc (vec
<tree
> scc
)
3826 scc
.qsort (compare_ops
);
3829 /* Insert the no longer used nary ONARY to the hash INFO. */
3832 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3834 size_t size
= sizeof_vn_nary_op (onary
->length
);
3835 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3836 &info
->nary_obstack
);
3837 memcpy (nary
, onary
, size
);
3838 vn_nary_op_insert_into (nary
, info
->nary
, false);
3841 /* Insert the no longer used phi OPHI to the hash INFO. */
3844 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3846 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3848 memcpy (phi
, ophi
, sizeof (*phi
));
3849 ophi
->phiargs
.create (0);
3850 slot
= info
->phis
->find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3851 gcc_assert (!*slot
);
3855 /* Insert the no longer used reference OREF to the hash INFO. */
3858 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3861 vn_reference_s
**slot
;
3862 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3863 memcpy (ref
, oref
, sizeof (*ref
));
3864 oref
->operands
.create (0);
3865 slot
= info
->references
->find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3867 free_reference (*slot
);
3871 /* Process a strongly connected component in the SSA graph. */
3874 process_scc (vec
<tree
> scc
)
3878 unsigned int iterations
= 0;
3879 bool changed
= true;
3880 vn_nary_op_iterator_type hin
;
3881 vn_phi_iterator_type hip
;
3882 vn_reference_iterator_type hir
;
3887 /* If the SCC has a single member, just visit it. */
3888 if (scc
.length () == 1)
3891 if (VN_INFO (use
)->use_processed
)
3893 /* We need to make sure it doesn't form a cycle itself, which can
3894 happen for self-referential PHI nodes. In that case we would
3895 end up inserting an expression with VN_TOP operands into the
3896 valid table which makes us derive bogus equivalences later.
3897 The cheapest way to check this is to assume it for all PHI nodes. */
3898 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3899 /* Fallthru to iteration. */ ;
3907 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3908 print_scc (dump_file
, scc
);
3910 /* Iterate over the SCC with the optimistic table until it stops
3912 current_info
= optimistic_info
;
3917 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3918 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3919 /* As we are value-numbering optimistically we have to
3920 clear the expression tables and the simplified expressions
3921 in each iteration until we converge. */
3922 optimistic_info
->nary
->empty ();
3923 optimistic_info
->phis
->empty ();
3924 optimistic_info
->references
->empty ();
3925 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3926 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3927 empty_alloc_pool (optimistic_info
->phis_pool
);
3928 empty_alloc_pool (optimistic_info
->references_pool
);
3929 FOR_EACH_VEC_ELT (scc
, i
, var
)
3930 VN_INFO (var
)->expr
= NULL_TREE
;
3931 FOR_EACH_VEC_ELT (scc
, i
, var
)
3932 changed
|= visit_use (var
);
3935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3936 fprintf (dump_file
, "Processing SCC needed %d iterations\n", iterations
);
3937 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3939 /* Finally, copy the contents of the no longer used optimistic
3940 table to the valid table. */
3941 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3942 copy_nary (nary
, valid_info
);
3943 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3944 copy_phi (phi
, valid_info
);
3945 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->references
,
3946 ref
, vn_reference_t
, hir
)
3947 copy_reference (ref
, valid_info
);
3949 current_info
= valid_info
;
3953 /* Pop the components of the found SCC for NAME off the SCC stack
3954 and process them. Returns true if all went well, false if
3955 we run into resource limits. */
3958 extract_and_process_scc_for_name (tree name
)
3963 /* Found an SCC, pop the components off the SCC stack and
3967 x
= sccstack
.pop ();
3969 VN_INFO (x
)->on_sccstack
= false;
3971 } while (x
!= name
);
3973 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3975 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3978 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3979 "SCC size %u exceeding %u\n", scc
.length (),
3980 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3985 if (scc
.length () > 1)
3993 /* Depth first search on NAME to discover and process SCC's in the SSA
3995 Execution of this algorithm relies on the fact that the SCC's are
3996 popped off the stack in topological order.
3997 Returns true if successful, false if we stopped processing SCC's due
3998 to resource constraints. */
4003 vec
<ssa_op_iter
> itervec
= vNULL
;
4004 vec
<tree
> namevec
= vNULL
;
4005 use_operand_p usep
= NULL
;
4012 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
4013 VN_INFO (name
)->visited
= true;
4014 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
4016 sccstack
.safe_push (name
);
4017 VN_INFO (name
)->on_sccstack
= true;
4018 defstmt
= SSA_NAME_DEF_STMT (name
);
4020 /* Recursively DFS on our operands, looking for SCC's. */
4021 if (!gimple_nop_p (defstmt
))
4023 /* Push a new iterator. */
4024 if (gphi
*phi
= dyn_cast
<gphi
*> (defstmt
))
4025 usep
= op_iter_init_phiuse (&iter
, phi
, SSA_OP_ALL_USES
);
4027 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
4030 clear_and_done_ssa_iter (&iter
);
4034 /* If we are done processing uses of a name, go up the stack
4035 of iterators and process SCCs as we found them. */
4036 if (op_iter_done (&iter
))
4038 /* See if we found an SCC. */
4039 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
4040 if (!extract_and_process_scc_for_name (name
))
4047 /* Check if we are done. */
4048 if (namevec
.is_empty ())
4055 /* Restore the last use walker and continue walking there. */
4057 name
= namevec
.pop ();
4058 memcpy (&iter
, &itervec
.last (),
4059 sizeof (ssa_op_iter
));
4061 goto continue_walking
;
4064 use
= USE_FROM_PTR (usep
);
4066 /* Since we handle phi nodes, we will sometimes get
4067 invariants in the use expression. */
4068 if (TREE_CODE (use
) == SSA_NAME
)
4070 if (! (VN_INFO (use
)->visited
))
4072 /* Recurse by pushing the current use walking state on
4073 the stack and starting over. */
4074 itervec
.safe_push (iter
);
4075 namevec
.safe_push (name
);
4080 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
4081 VN_INFO (use
)->low
);
4083 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
4084 && VN_INFO (use
)->on_sccstack
)
4086 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
4087 VN_INFO (name
)->low
);
4091 usep
= op_iter_next_use (&iter
);
4095 /* Allocate a value number table. */
4098 allocate_vn_table (vn_tables_t table
)
4100 table
->phis
= new vn_phi_table_type (23);
4101 table
->nary
= new vn_nary_op_table_type (23);
4102 table
->references
= new vn_reference_table_type (23);
4104 gcc_obstack_init (&table
->nary_obstack
);
4105 table
->phis_pool
= create_alloc_pool ("VN phis",
4106 sizeof (struct vn_phi_s
),
4108 table
->references_pool
= create_alloc_pool ("VN references",
4109 sizeof (struct vn_reference_s
),
4113 /* Free a value number table. */
4116 free_vn_table (vn_tables_t table
)
4122 delete table
->references
;
4123 table
->references
= NULL
;
4124 obstack_free (&table
->nary_obstack
, NULL
);
4125 free_alloc_pool (table
->phis_pool
);
4126 free_alloc_pool (table
->references_pool
);
4134 int *rpo_numbers_temp
;
4136 calculate_dominance_info (CDI_DOMINATORS
);
4137 sccstack
.create (0);
4138 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
4140 constant_value_ids
= BITMAP_ALLOC (NULL
);
4145 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
4146 /* VEC_alloc doesn't actually grow it to the right size, it just
4147 preallocates the space to do so. */
4148 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
4149 gcc_obstack_init (&vn_ssa_aux_obstack
);
4151 shared_lookup_phiargs
.create (0);
4152 shared_lookup_references
.create (0);
4153 rpo_numbers
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
4155 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
4156 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
4158 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4159 the i'th block in RPO order is bb. We want to map bb's to RPO
4160 numbers, so we need to rearrange this array. */
4161 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
4162 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
4164 XDELETE (rpo_numbers_temp
);
4166 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
4168 /* Create the VN_INFO structures, and initialize value numbers to
4170 for (i
= 0; i
< num_ssa_names
; i
++)
4172 tree name
= ssa_name (i
);
4175 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4176 VN_INFO (name
)->expr
= NULL_TREE
;
4177 VN_INFO (name
)->value_id
= 0;
4181 renumber_gimple_stmt_uids ();
4183 /* Create the valid and optimistic value numbering tables. */
4184 valid_info
= XCNEW (struct vn_tables_s
);
4185 allocate_vn_table (valid_info
);
4186 optimistic_info
= XCNEW (struct vn_tables_s
);
4187 allocate_vn_table (optimistic_info
);
4195 delete constant_to_value_id
;
4196 constant_to_value_id
= NULL
;
4197 BITMAP_FREE (constant_value_ids
);
4198 shared_lookup_phiargs
.release ();
4199 shared_lookup_references
.release ();
4200 XDELETEVEC (rpo_numbers
);
4202 for (i
= 0; i
< num_ssa_names
; i
++)
4204 tree name
= ssa_name (i
);
4206 && VN_INFO (name
)->needs_insertion
)
4207 release_ssa_name (name
);
4209 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4210 vn_ssa_aux_table
.release ();
4212 sccstack
.release ();
4213 free_vn_table (valid_info
);
4214 XDELETE (valid_info
);
4215 free_vn_table (optimistic_info
);
4216 XDELETE (optimistic_info
);
4219 /* Set *ID according to RESULT. */
4222 set_value_id_for_result (tree result
, unsigned int *id
)
4224 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4225 *id
= VN_INFO (result
)->value_id
;
4226 else if (result
&& is_gimple_min_invariant (result
))
4227 *id
= get_or_alloc_constant_value_id (result
);
4229 *id
= get_next_value_id ();
4232 /* Set the value ids in the valid hash tables. */
4235 set_hashtable_value_ids (void)
4237 vn_nary_op_iterator_type hin
;
4238 vn_phi_iterator_type hip
;
4239 vn_reference_iterator_type hir
;
4244 /* Now set the value ids of the things we had put in the hash
4247 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4248 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4250 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4251 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4253 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4255 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4258 class cond_dom_walker
: public dom_walker
4261 cond_dom_walker () : dom_walker (CDI_DOMINATORS
), fail (false) {}
4263 virtual void before_dom_children (basic_block
);
4269 cond_dom_walker::before_dom_children (basic_block bb
)
4277 /* If any of the predecessor edges that do not come from blocks dominated
4278 by us are still marked as possibly executable consider this block
4280 bool reachable
= bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
);
4281 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4282 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
4283 reachable
|= (e
->flags
& EDGE_EXECUTABLE
);
4285 /* If the block is not reachable all outgoing edges are not
4289 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4290 fprintf (dump_file
, "Marking all outgoing edges of unreachable "
4291 "BB %d as not executable\n", bb
->index
);
4293 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4294 e
->flags
&= ~EDGE_EXECUTABLE
;
4298 gimple stmt
= last_stmt (bb
);
4302 enum gimple_code code
= gimple_code (stmt
);
4303 if (code
!= GIMPLE_COND
4304 && code
!= GIMPLE_SWITCH
4305 && code
!= GIMPLE_GOTO
)
4308 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4310 fprintf (dump_file
, "Value-numbering operands of stmt ending BB %d: ",
4312 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4315 /* Value-number the last stmts SSA uses. */
4318 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
4319 if (VN_INFO (op
)->visited
== false
4326 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4327 if value-numbering can prove they are not reachable. Handling
4328 computed gotos is also possible. */
4334 tree lhs
= gimple_cond_lhs (stmt
);
4335 tree rhs
= gimple_cond_rhs (stmt
);
4336 /* Work hard in computing the condition and take into account
4337 the valueization of the defining stmt. */
4338 if (TREE_CODE (lhs
) == SSA_NAME
)
4339 lhs
= vn_get_expr_for (lhs
);
4340 if (TREE_CODE (rhs
) == SSA_NAME
)
4341 rhs
= vn_get_expr_for (rhs
);
4342 val
= fold_binary (gimple_cond_code (stmt
),
4343 boolean_type_node
, lhs
, rhs
);
4347 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
4350 val
= gimple_goto_dest (stmt
);
4358 edge taken
= find_taken_edge (bb
, vn_valueize (val
));
4362 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4363 fprintf (dump_file
, "Marking all edges out of BB %d but (%d -> %d) as "
4364 "not executable\n", bb
->index
, bb
->index
, taken
->dest
->index
);
4366 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4368 e
->flags
&= ~EDGE_EXECUTABLE
;
4371 /* Do SCCVN. Returns true if it finished, false if we bailed out
4372 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4373 how we use the alias oracle walking during the VN process. */
4376 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4382 default_vn_walk_kind
= default_vn_walk_kind_
;
4385 current_info
= valid_info
;
4387 for (param
= DECL_ARGUMENTS (current_function_decl
);
4389 param
= DECL_CHAIN (param
))
4391 tree def
= ssa_default_def (cfun
, param
);
4394 VN_INFO (def
)->visited
= true;
4395 VN_INFO (def
)->valnum
= def
;
4399 /* Mark all edges as possibly executable. */
4400 FOR_ALL_BB_FN (bb
, cfun
)
4404 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4405 e
->flags
|= EDGE_EXECUTABLE
;
4408 /* Walk all blocks in dominator order, value-numbering the last stmts
4409 SSA uses and decide whether outgoing edges are not executable. */
4410 cond_dom_walker walker
;
4411 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4418 /* Value-number remaining SSA names. */
4419 for (i
= 1; i
< num_ssa_names
; ++i
)
4421 tree name
= ssa_name (i
);
4423 && VN_INFO (name
)->visited
== false
4424 && !has_zero_uses (name
))
4432 /* Initialize the value ids. */
4434 for (i
= 1; i
< num_ssa_names
; ++i
)
4436 tree name
= ssa_name (i
);
4440 info
= VN_INFO (name
);
4441 if (info
->valnum
== name
4442 || info
->valnum
== VN_TOP
)
4443 info
->value_id
= get_next_value_id ();
4444 else if (is_gimple_min_invariant (info
->valnum
))
4445 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4449 for (i
= 1; i
< num_ssa_names
; ++i
)
4451 tree name
= ssa_name (i
);
4455 info
= VN_INFO (name
);
4456 if (TREE_CODE (info
->valnum
) == SSA_NAME
4457 && info
->valnum
!= name
4458 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4459 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4462 set_hashtable_value_ids ();
4464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4466 fprintf (dump_file
, "Value numbers:\n");
4467 for (i
= 0; i
< num_ssa_names
; i
++)
4469 tree name
= ssa_name (i
);
4471 && VN_INFO (name
)->visited
4472 && SSA_VAL (name
) != name
)
4474 print_generic_expr (dump_file
, name
, 0);
4475 fprintf (dump_file
, " = ");
4476 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4477 fprintf (dump_file
, "\n");
4485 /* Return the maximum value id we have ever seen. */
4488 get_max_value_id (void)
4490 return next_value_id
;
4493 /* Return the next unique value id. */
4496 get_next_value_id (void)
4498 return next_value_id
++;
4502 /* Compare two expressions E1 and E2 and return true if they are equal. */
4505 expressions_equal_p (tree e1
, tree e2
)
4507 /* The obvious case. */
4511 /* If only one of them is null, they cannot be equal. */
4515 /* Now perform the actual comparison. */
4516 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4517 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4524 /* Return true if the nary operation NARY may trap. This is a copy
4525 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4528 vn_nary_may_trap (vn_nary_op_t nary
)
4531 tree rhs2
= NULL_TREE
;
4532 bool honor_nans
= false;
4533 bool honor_snans
= false;
4534 bool fp_operation
= false;
4535 bool honor_trapv
= false;
4539 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4540 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4541 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4544 fp_operation
= FLOAT_TYPE_P (type
);
4547 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4548 honor_snans
= flag_signaling_nans
!= 0;
4550 else if (INTEGRAL_TYPE_P (type
)
4551 && TYPE_OVERFLOW_TRAPS (type
))
4554 if (nary
->length
>= 2)
4556 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4558 honor_nans
, honor_snans
, rhs2
,
4564 for (i
= 0; i
< nary
->length
; ++i
)
4565 if (tree_could_trap_p (nary
->op
[i
]))