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"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "tree-inline.h"
30 #include "hash-table.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
34 #include "gimple-fold.h"
36 #include "gimple-expr.h"
40 #include "gimple-ssa.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
49 #include "alloc-pool.h"
53 #include "tree-ssa-propagate.h"
54 #include "tree-ssa-sccvn.h"
58 /* This algorithm is based on the SCC algorithm presented by Keith
59 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
60 (http://citeseer.ist.psu.edu/41805.html). In
61 straight line code, it is equivalent to a regular hash based value
62 numbering that is performed in reverse postorder.
64 For code with cycles, there are two alternatives, both of which
65 require keeping the hashtables separate from the actual list of
66 value numbers for SSA names.
68 1. Iterate value numbering in an RPO walk of the blocks, removing
69 all the entries from the hashtable after each iteration (but
70 keeping the SSA name->value number mapping between iterations).
71 Iterate until it does not change.
73 2. Perform value numbering as part of an SCC walk on the SSA graph,
74 iterating only the cycles in the SSA graph until they do not change
75 (using a separate, optimistic hashtable for value numbering the SCC
78 The second is not just faster in practice (because most SSA graph
79 cycles do not involve all the variables in the graph), it also has
82 One of these nice properties is that when we pop an SCC off the
83 stack, we are guaranteed to have processed all the operands coming from
84 *outside of that SCC*, so we do not need to do anything special to
85 ensure they have value numbers.
87 Another nice property is that the SCC walk is done as part of a DFS
88 of the SSA graph, which makes it easy to perform combining and
89 simplifying operations at the same time.
91 The code below is deliberately written in a way that makes it easy
92 to separate the SCC walk from the other work it does.
94 In order to propagate constants through the code, we track which
95 expressions contain constants, and use those while folding. In
96 theory, we could also track expressions whose value numbers are
97 replaced, in case we end up folding based on expression
100 In order to value number memory, we assign value numbers to vuses.
101 This enables us to note that, for example, stores to the same
102 address of the same value from the same starting memory states are
106 1. We can iterate only the changing portions of the SCC's, but
107 I have not seen an SCC big enough for this to be a win.
108 2. If you differentiate between phi nodes for loops and phi nodes
109 for if-then-else, you can properly consider phi nodes in different
110 blocks for equivalence.
111 3. We could value number vuses in more cases, particularly, whole
116 /* vn_nary_op hashtable helpers. */
118 struct vn_nary_op_hasher
: typed_noop_remove
<vn_nary_op_s
>
120 typedef vn_nary_op_s value_type
;
121 typedef vn_nary_op_s compare_type
;
122 static inline hashval_t
hash (const value_type
*);
123 static inline bool equal (const value_type
*, const compare_type
*);
126 /* Return the computed hashcode for nary operation P1. */
129 vn_nary_op_hasher::hash (const value_type
*vno1
)
131 return vno1
->hashcode
;
134 /* Compare nary operations P1 and P2 and return true if they are
138 vn_nary_op_hasher::equal (const value_type
*vno1
, const compare_type
*vno2
)
140 return vn_nary_op_eq (vno1
, vno2
);
143 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
144 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
147 /* vn_phi hashtable helpers. */
150 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
154 typedef vn_phi_s value_type
;
155 typedef vn_phi_s compare_type
;
156 static inline hashval_t
hash (const value_type
*);
157 static inline bool equal (const value_type
*, const compare_type
*);
158 static inline void remove (value_type
*);
161 /* Return the computed hashcode for phi operation P1. */
164 vn_phi_hasher::hash (const value_type
*vp1
)
166 return vp1
->hashcode
;
169 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
172 vn_phi_hasher::equal (const value_type
*vp1
, const compare_type
*vp2
)
174 return vn_phi_eq (vp1
, vp2
);
177 /* Free a phi operation structure VP. */
180 vn_phi_hasher::remove (value_type
*phi
)
182 phi
->phiargs
.release ();
185 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
186 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
189 /* Compare two reference operands P1 and P2 for equality. Return true if
190 they are equal, and false otherwise. */
193 vn_reference_op_eq (const void *p1
, const void *p2
)
195 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
196 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
198 return (vro1
->opcode
== vro2
->opcode
199 /* We do not care for differences in type qualification. */
200 && (vro1
->type
== vro2
->type
201 || (vro1
->type
&& vro2
->type
202 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
203 TYPE_MAIN_VARIANT (vro2
->type
))))
204 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
205 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
206 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
209 /* Free a reference operation structure VP. */
212 free_reference (vn_reference_s
*vr
)
214 vr
->operands
.release ();
218 /* vn_reference hashtable helpers. */
220 struct vn_reference_hasher
222 typedef vn_reference_s value_type
;
223 typedef vn_reference_s compare_type
;
224 static inline hashval_t
hash (const value_type
*);
225 static inline bool equal (const value_type
*, const compare_type
*);
226 static inline void remove (value_type
*);
229 /* Return the hashcode for a given reference operation P1. */
232 vn_reference_hasher::hash (const value_type
*vr1
)
234 return vr1
->hashcode
;
238 vn_reference_hasher::equal (const value_type
*v
, const compare_type
*c
)
240 return vn_reference_eq (v
, c
);
244 vn_reference_hasher::remove (value_type
*v
)
249 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
250 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
253 /* The set of hashtables and alloc_pool's for their items. */
255 typedef struct vn_tables_s
257 vn_nary_op_table_type
*nary
;
258 vn_phi_table_type
*phis
;
259 vn_reference_table_type
*references
;
260 struct obstack nary_obstack
;
261 alloc_pool phis_pool
;
262 alloc_pool references_pool
;
266 /* vn_constant hashtable helpers. */
268 struct vn_constant_hasher
: typed_free_remove
<vn_constant_s
>
270 typedef vn_constant_s value_type
;
271 typedef vn_constant_s compare_type
;
272 static inline hashval_t
hash (const value_type
*);
273 static inline bool equal (const value_type
*, const compare_type
*);
276 /* Hash table hash function for vn_constant_t. */
279 vn_constant_hasher::hash (const value_type
*vc1
)
281 return vc1
->hashcode
;
284 /* Hash table equality function for vn_constant_t. */
287 vn_constant_hasher::equal (const value_type
*vc1
, const compare_type
*vc2
)
289 if (vc1
->hashcode
!= vc2
->hashcode
)
292 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
295 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
296 static bitmap constant_value_ids
;
299 /* Valid hashtables storing information we have proven to be
302 static vn_tables_t valid_info
;
304 /* Optimistic hashtables storing information we are making assumptions about
305 during iterations. */
307 static vn_tables_t optimistic_info
;
309 /* Pointer to the set of hashtables that is currently being used.
310 Should always point to either the optimistic_info, or the
313 static vn_tables_t current_info
;
316 /* Reverse post order index for each basic block. */
318 static int *rpo_numbers
;
320 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
322 /* Return the SSA value of the VUSE x, supporting released VDEFs
323 during elimination which will value-number the VDEF to the
324 associated VUSE (but not substitute in the whole lattice). */
327 vuse_ssa_val (tree x
)
336 while (SSA_NAME_IN_FREE_LIST (x
));
341 /* This represents the top of the VN lattice, which is the universal
346 /* Unique counter for our value ids. */
348 static unsigned int next_value_id
;
350 /* Next DFS number and the stack for strongly connected component
353 static unsigned int next_dfs_num
;
354 static vec
<tree
> sccstack
;
358 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
359 are allocated on an obstack for locality reasons, and to free them
360 without looping over the vec. */
362 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
363 static struct obstack vn_ssa_aux_obstack
;
365 /* Return the value numbering information for a given SSA name. */
370 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
371 gcc_checking_assert (res
);
375 /* Set the value numbering info for a given SSA name to a given
379 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
381 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
384 /* Initialize the value numbering info for a given SSA name.
385 This should be called just once for every SSA name. */
388 VN_INFO_GET (tree name
)
390 vn_ssa_aux_t newinfo
;
392 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
393 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
394 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
395 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
396 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
401 /* Get the representative expression for the SSA_NAME NAME. Returns
402 the representative SSA_NAME if there is no expression associated with it. */
405 vn_get_expr_for (tree name
)
407 vn_ssa_aux_t vn
= VN_INFO (name
);
409 tree expr
= NULL_TREE
;
412 if (vn
->valnum
== VN_TOP
)
415 /* If the value-number is a constant it is the representative
417 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
420 /* Get to the information of the value of this SSA_NAME. */
421 vn
= VN_INFO (vn
->valnum
);
423 /* If the value-number is a constant it is the representative
425 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
428 /* Else if we have an expression, return it. */
429 if (vn
->expr
!= NULL_TREE
)
432 /* Otherwise use the defining statement to build the expression. */
433 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
435 /* If the value number is not an assignment use it directly. */
436 if (!is_gimple_assign (def_stmt
))
439 /* Note that we can valueize here because we clear the cached
440 simplified expressions after each optimistic iteration. */
441 code
= gimple_assign_rhs_code (def_stmt
);
442 switch (TREE_CODE_CLASS (code
))
445 if ((code
== REALPART_EXPR
446 || code
== IMAGPART_EXPR
447 || code
== VIEW_CONVERT_EXPR
)
448 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
450 expr
= fold_build1 (code
,
451 gimple_expr_type (def_stmt
),
452 vn_valueize (TREE_OPERAND
453 (gimple_assign_rhs1 (def_stmt
), 0)));
457 expr
= fold_build1 (code
,
458 gimple_expr_type (def_stmt
),
459 vn_valueize (gimple_assign_rhs1 (def_stmt
)));
463 expr
= fold_build2 (code
,
464 gimple_expr_type (def_stmt
),
465 vn_valueize (gimple_assign_rhs1 (def_stmt
)),
466 vn_valueize (gimple_assign_rhs2 (def_stmt
)));
469 case tcc_exceptional
:
470 if (code
== CONSTRUCTOR
472 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
473 expr
= gimple_assign_rhs1 (def_stmt
);
478 if (expr
== NULL_TREE
)
481 /* Cache the expression. */
487 /* Return the vn_kind the expression computed by the stmt should be
491 vn_get_stmt_kind (gimple stmt
)
493 switch (gimple_code (stmt
))
501 enum tree_code code
= gimple_assign_rhs_code (stmt
);
502 tree rhs1
= gimple_assign_rhs1 (stmt
);
503 switch (get_gimple_rhs_class (code
))
505 case GIMPLE_UNARY_RHS
:
506 case GIMPLE_BINARY_RHS
:
507 case GIMPLE_TERNARY_RHS
:
509 case GIMPLE_SINGLE_RHS
:
510 switch (TREE_CODE_CLASS (code
))
513 /* VOP-less references can go through unary case. */
514 if ((code
== REALPART_EXPR
515 || code
== IMAGPART_EXPR
516 || code
== VIEW_CONVERT_EXPR
517 || code
== BIT_FIELD_REF
)
518 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
522 case tcc_declaration
:
529 if (code
== ADDR_EXPR
)
530 return (is_gimple_min_invariant (rhs1
)
531 ? VN_CONSTANT
: VN_REFERENCE
);
532 else if (code
== CONSTRUCTOR
)
545 /* Lookup a value id for CONSTANT and return it. If it does not
549 get_constant_value_id (tree constant
)
551 vn_constant_s
**slot
;
552 struct vn_constant_s vc
;
554 vc
.hashcode
= vn_hash_constant_with_type (constant
);
555 vc
.constant
= constant
;
556 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
558 return (*slot
)->value_id
;
562 /* Lookup a value id for CONSTANT, and if it does not exist, create a
563 new one and return it. If it does exist, return it. */
566 get_or_alloc_constant_value_id (tree constant
)
568 vn_constant_s
**slot
;
569 struct vn_constant_s vc
;
572 vc
.hashcode
= vn_hash_constant_with_type (constant
);
573 vc
.constant
= constant
;
574 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
576 return (*slot
)->value_id
;
578 vcp
= XNEW (struct vn_constant_s
);
579 vcp
->hashcode
= vc
.hashcode
;
580 vcp
->constant
= constant
;
581 vcp
->value_id
= get_next_value_id ();
583 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
584 return vcp
->value_id
;
587 /* Return true if V is a value id for a constant. */
590 value_id_constant_p (unsigned int v
)
592 return bitmap_bit_p (constant_value_ids
, v
);
595 /* Compute the hash for a reference operand VRO1. */
598 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
600 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
602 result
= iterative_hash_expr (vro1
->op0
, result
);
604 result
= iterative_hash_expr (vro1
->op1
, result
);
606 result
= iterative_hash_expr (vro1
->op2
, result
);
610 /* Compute a hash for the reference operation VR1 and return it. */
613 vn_reference_compute_hash (const vn_reference_t vr1
)
615 hashval_t result
= 0;
617 vn_reference_op_t vro
;
618 HOST_WIDE_INT off
= -1;
621 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
623 if (vro
->opcode
== MEM_REF
)
625 else if (vro
->opcode
!= ADDR_EXPR
)
637 result
= iterative_hash_hashval_t (off
, result
);
640 && vro
->opcode
== ADDR_EXPR
)
644 tree op
= TREE_OPERAND (vro
->op0
, 0);
645 result
= iterative_hash_hashval_t (TREE_CODE (op
), result
);
646 result
= iterative_hash_expr (op
, result
);
650 result
= vn_reference_op_compute_hash (vro
, result
);
654 result
+= SSA_NAME_VERSION (vr1
->vuse
);
659 /* Return true if reference operations VR1 and VR2 are equivalent. This
660 means they have the same set of operands and vuses. */
663 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
667 /* Early out if this is not a hash collision. */
668 if (vr1
->hashcode
!= vr2
->hashcode
)
671 /* The VOP needs to be the same. */
672 if (vr1
->vuse
!= vr2
->vuse
)
675 /* If the operands are the same we are done. */
676 if (vr1
->operands
== vr2
->operands
)
679 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
682 if (INTEGRAL_TYPE_P (vr1
->type
)
683 && INTEGRAL_TYPE_P (vr2
->type
))
685 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
688 else if (INTEGRAL_TYPE_P (vr1
->type
)
689 && (TYPE_PRECISION (vr1
->type
)
690 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
692 else if (INTEGRAL_TYPE_P (vr2
->type
)
693 && (TYPE_PRECISION (vr2
->type
)
694 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
701 HOST_WIDE_INT off1
= 0, off2
= 0;
702 vn_reference_op_t vro1
, vro2
;
703 vn_reference_op_s tem1
, tem2
;
704 bool deref1
= false, deref2
= false;
705 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
707 if (vro1
->opcode
== MEM_REF
)
713 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
715 if (vro2
->opcode
== MEM_REF
)
723 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
725 memset (&tem1
, 0, sizeof (tem1
));
726 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
727 tem1
.type
= TREE_TYPE (tem1
.op0
);
728 tem1
.opcode
= TREE_CODE (tem1
.op0
);
732 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
734 memset (&tem2
, 0, sizeof (tem2
));
735 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
736 tem2
.type
= TREE_TYPE (tem2
.op0
);
737 tem2
.opcode
= TREE_CODE (tem2
.op0
);
741 if (deref1
!= deref2
)
743 if (!vn_reference_op_eq (vro1
, vro2
))
748 while (vr1
->operands
.length () != i
749 || vr2
->operands
.length () != j
);
754 /* Copy the operations present in load/store REF into RESULT, a vector of
755 vn_reference_op_s's. */
758 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
760 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
762 vn_reference_op_s temp
;
766 memset (&temp
, 0, sizeof (temp
));
767 temp
.type
= TREE_TYPE (ref
);
768 temp
.opcode
= TREE_CODE (ref
);
769 temp
.op0
= TMR_INDEX (ref
);
770 temp
.op1
= TMR_STEP (ref
);
771 temp
.op2
= TMR_OFFSET (ref
);
773 result
->quick_push (temp
);
775 memset (&temp
, 0, sizeof (temp
));
776 temp
.type
= NULL_TREE
;
777 temp
.opcode
= ERROR_MARK
;
778 temp
.op0
= TMR_INDEX2 (ref
);
780 result
->quick_push (temp
);
782 memset (&temp
, 0, sizeof (temp
));
783 temp
.type
= NULL_TREE
;
784 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
785 temp
.op0
= TMR_BASE (ref
);
787 result
->quick_push (temp
);
791 /* For non-calls, store the information that makes up the address. */
795 vn_reference_op_s temp
;
797 memset (&temp
, 0, sizeof (temp
));
798 temp
.type
= TREE_TYPE (ref
);
799 temp
.opcode
= TREE_CODE (ref
);
805 temp
.op0
= TREE_OPERAND (ref
, 1);
808 temp
.op0
= TREE_OPERAND (ref
, 1);
812 /* The base address gets its own vn_reference_op_s structure. */
813 temp
.op0
= TREE_OPERAND (ref
, 1);
814 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 1)))
815 temp
.off
= tree_to_shwi (TREE_OPERAND (ref
, 1));
818 /* Record bits and position. */
819 temp
.op0
= TREE_OPERAND (ref
, 1);
820 temp
.op1
= TREE_OPERAND (ref
, 2);
823 /* The field decl is enough to unambiguously specify the field,
824 a matching type is not necessary and a mismatching type
825 is always a spurious difference. */
826 temp
.type
= NULL_TREE
;
827 temp
.op0
= TREE_OPERAND (ref
, 1);
828 temp
.op1
= TREE_OPERAND (ref
, 2);
830 tree this_offset
= component_ref_field_offset (ref
);
832 && TREE_CODE (this_offset
) == INTEGER_CST
)
834 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
835 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
838 = (wi::to_offset (this_offset
)
839 + wi::lrshift (wi::to_offset (bit_offset
),
840 LOG2_BITS_PER_UNIT
));
841 if (wi::fits_shwi_p (off
)
842 /* Probibit value-numbering zero offset components
843 of addresses the same before the pass folding
844 __builtin_object_size had a chance to run
845 (checking cfun->after_inlining does the
847 && (TREE_CODE (orig
) != ADDR_EXPR
849 || cfun
->after_inlining
))
850 temp
.off
= off
.to_shwi ();
855 case ARRAY_RANGE_REF
:
857 /* Record index as operand. */
858 temp
.op0
= TREE_OPERAND (ref
, 1);
859 /* Always record lower bounds and element size. */
860 temp
.op1
= array_ref_low_bound (ref
);
861 temp
.op2
= array_ref_element_size (ref
);
862 if (TREE_CODE (temp
.op0
) == INTEGER_CST
863 && TREE_CODE (temp
.op1
) == INTEGER_CST
864 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
866 offset_int off
= ((wi::to_offset (temp
.op0
)
867 - wi::to_offset (temp
.op1
))
868 * wi::to_offset (temp
.op2
));
869 if (wi::fits_shwi_p (off
))
870 temp
.off
= off
.to_shwi();
874 if (DECL_HARD_REGISTER (ref
))
883 /* Canonicalize decls to MEM[&decl] which is what we end up with
884 when valueizing MEM[ptr] with ptr = &decl. */
885 temp
.opcode
= MEM_REF
;
886 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
888 result
->safe_push (temp
);
889 temp
.opcode
= ADDR_EXPR
;
890 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
891 temp
.type
= TREE_TYPE (temp
.op0
);
905 if (is_gimple_min_invariant (ref
))
911 /* These are only interesting for their operands, their
912 existence, and their type. They will never be the last
913 ref in the chain of references (IE they require an
914 operand), so we don't have to put anything
915 for op* as it will be handled by the iteration */
917 case VIEW_CONVERT_EXPR
:
921 /* This is only interesting for its constant offset. */
922 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
927 result
->safe_push (temp
);
929 if (REFERENCE_CLASS_P (ref
)
930 || TREE_CODE (ref
) == MODIFY_EXPR
931 || TREE_CODE (ref
) == WITH_SIZE_EXPR
932 || (TREE_CODE (ref
) == ADDR_EXPR
933 && !is_gimple_min_invariant (ref
)))
934 ref
= TREE_OPERAND (ref
, 0);
940 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
941 operands in *OPS, the reference alias set SET and the reference type TYPE.
942 Return true if something useful was produced. */
945 ao_ref_init_from_vn_reference (ao_ref
*ref
,
946 alias_set_type set
, tree type
,
947 vec
<vn_reference_op_s
> ops
)
949 vn_reference_op_t op
;
951 tree base
= NULL_TREE
;
953 HOST_WIDE_INT offset
= 0;
954 HOST_WIDE_INT max_size
;
955 HOST_WIDE_INT size
= -1;
956 tree size_tree
= NULL_TREE
;
957 alias_set_type base_alias_set
= -1;
959 /* First get the final access size from just the outermost expression. */
961 if (op
->opcode
== COMPONENT_REF
)
962 size_tree
= DECL_SIZE (op
->op0
);
963 else if (op
->opcode
== BIT_FIELD_REF
)
967 enum machine_mode mode
= TYPE_MODE (type
);
969 size_tree
= TYPE_SIZE (type
);
971 size
= GET_MODE_BITSIZE (mode
);
973 if (size_tree
!= NULL_TREE
)
975 if (!tree_fits_uhwi_p (size_tree
))
978 size
= tree_to_uhwi (size_tree
);
981 /* Initially, maxsize is the same as the accessed element size.
982 In the following it will only grow (or become -1). */
985 /* Compute cumulative bit-offset for nested component-refs and array-refs,
986 and find the ultimate containing object. */
987 FOR_EACH_VEC_ELT (ops
, i
, op
)
991 /* These may be in the reference ops, but we cannot do anything
992 sensible with them here. */
994 /* Apart from ADDR_EXPR arguments to MEM_REF. */
995 if (base
!= NULL_TREE
996 && TREE_CODE (base
) == MEM_REF
998 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
1000 vn_reference_op_t pop
= &ops
[i
-1];
1001 base
= TREE_OPERAND (op
->op0
, 0);
1008 offset
+= pop
->off
* BITS_PER_UNIT
;
1016 /* Record the base objects. */
1018 base_alias_set
= get_deref_alias_set (op
->op0
);
1019 *op0_p
= build2 (MEM_REF
, op
->type
,
1020 NULL_TREE
, op
->op0
);
1021 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1032 /* And now the usual component-reference style ops. */
1034 offset
+= tree_to_shwi (op
->op1
);
1039 tree field
= op
->op0
;
1040 /* We do not have a complete COMPONENT_REF tree here so we
1041 cannot use component_ref_field_offset. Do the interesting
1045 || !tree_fits_uhwi_p (DECL_FIELD_OFFSET (field
)))
1049 offset
+= (tree_to_uhwi (DECL_FIELD_OFFSET (field
))
1051 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
1056 case ARRAY_RANGE_REF
:
1058 /* We recorded the lower bound and the element size. */
1059 if (!tree_fits_shwi_p (op
->op0
)
1060 || !tree_fits_shwi_p (op
->op1
)
1061 || !tree_fits_shwi_p (op
->op2
))
1065 HOST_WIDE_INT hindex
= tree_to_shwi (op
->op0
);
1066 hindex
-= tree_to_shwi (op
->op1
);
1067 hindex
*= tree_to_shwi (op
->op2
);
1068 hindex
*= BITS_PER_UNIT
;
1080 case VIEW_CONVERT_EXPR
:
1097 if (base
== NULL_TREE
)
1100 ref
->ref
= NULL_TREE
;
1102 ref
->offset
= offset
;
1104 ref
->max_size
= max_size
;
1105 ref
->ref_alias_set
= set
;
1106 if (base_alias_set
!= -1)
1107 ref
->base_alias_set
= base_alias_set
;
1109 ref
->base_alias_set
= get_alias_set (base
);
1110 /* We discount volatiles from value-numbering elsewhere. */
1111 ref
->volatile_p
= false;
1116 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1117 vn_reference_op_s's. */
1120 copy_reference_ops_from_call (gimple call
,
1121 vec
<vn_reference_op_s
> *result
)
1123 vn_reference_op_s temp
;
1125 tree lhs
= gimple_call_lhs (call
);
1128 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1129 different. By adding the lhs here in the vector, we ensure that the
1130 hashcode is different, guaranteeing a different value number. */
1131 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1133 memset (&temp
, 0, sizeof (temp
));
1134 temp
.opcode
= MODIFY_EXPR
;
1135 temp
.type
= TREE_TYPE (lhs
);
1138 result
->safe_push (temp
);
1141 /* Copy the type, opcode, function, static chain and EH region, if any. */
1142 memset (&temp
, 0, sizeof (temp
));
1143 temp
.type
= gimple_call_return_type (call
);
1144 temp
.opcode
= CALL_EXPR
;
1145 temp
.op0
= gimple_call_fn (call
);
1146 temp
.op1
= gimple_call_chain (call
);
1147 if (stmt_could_throw_p (call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1148 temp
.op2
= size_int (lr
);
1150 result
->safe_push (temp
);
1152 /* Copy the call arguments. As they can be references as well,
1153 just chain them together. */
1154 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1156 tree callarg
= gimple_call_arg (call
, i
);
1157 copy_reference_ops_from_ref (callarg
, result
);
1161 /* Create a vector of vn_reference_op_s structures from CALL, a
1162 call statement. The vector is not shared. */
1164 static vec
<vn_reference_op_s
>
1165 create_reference_ops_from_call (gimple call
)
1167 vec
<vn_reference_op_s
> result
= vNULL
;
1169 copy_reference_ops_from_call (call
, &result
);
1173 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1174 *I_P to point to the last element of the replacement. */
1176 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1179 unsigned int i
= *i_p
;
1180 vn_reference_op_t op
= &(*ops
)[i
];
1181 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1183 HOST_WIDE_INT addr_offset
= 0;
1185 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1186 from .foo.bar to the preceding MEM_REF offset and replace the
1187 address with &OBJ. */
1188 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1190 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1191 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1193 offset_int off
= offset_int::from (mem_op
->op0
, SIGNED
);
1195 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1196 op
->op0
= build_fold_addr_expr (addr_base
);
1197 if (tree_fits_shwi_p (mem_op
->op0
))
1198 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1204 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1205 *I_P to point to the last element of the replacement. */
1207 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1210 unsigned int i
= *i_p
;
1211 vn_reference_op_t op
= &(*ops
)[i
];
1212 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1214 enum tree_code code
;
1217 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1218 if (!is_gimple_assign (def_stmt
))
1221 code
= gimple_assign_rhs_code (def_stmt
);
1222 if (code
!= ADDR_EXPR
1223 && code
!= POINTER_PLUS_EXPR
)
1226 off
= offset_int::from (mem_op
->op0
, SIGNED
);
1228 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1229 from .foo.bar to the preceding MEM_REF offset and replace the
1230 address with &OBJ. */
1231 if (code
== ADDR_EXPR
)
1233 tree addr
, addr_base
;
1234 HOST_WIDE_INT addr_offset
;
1236 addr
= gimple_assign_rhs1 (def_stmt
);
1237 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1240 || TREE_CODE (addr_base
) != MEM_REF
)
1244 off
+= mem_ref_offset (addr_base
);
1245 op
->op0
= TREE_OPERAND (addr_base
, 0);
1250 ptr
= gimple_assign_rhs1 (def_stmt
);
1251 ptroff
= gimple_assign_rhs2 (def_stmt
);
1252 if (TREE_CODE (ptr
) != SSA_NAME
1253 || TREE_CODE (ptroff
) != INTEGER_CST
)
1256 off
+= wi::to_offset (ptroff
);
1260 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1261 if (tree_fits_shwi_p (mem_op
->op0
))
1262 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1265 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1266 op
->op0
= SSA_VAL (op
->op0
);
1267 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1268 op
->opcode
= TREE_CODE (op
->op0
);
1271 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1272 vn_reference_maybe_forwprop_address (ops
, i_p
);
1273 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1274 vn_reference_fold_indirect (ops
, i_p
);
1277 /* Optimize the reference REF to a constant if possible or return
1278 NULL_TREE if not. */
1281 fully_constant_vn_reference_p (vn_reference_t ref
)
1283 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1284 vn_reference_op_t op
;
1286 /* Try to simplify the translated expression if it is
1287 a call to a builtin function with at most two arguments. */
1289 if (op
->opcode
== CALL_EXPR
1290 && TREE_CODE (op
->op0
) == ADDR_EXPR
1291 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1292 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1293 && operands
.length () >= 2
1294 && operands
.length () <= 3)
1296 vn_reference_op_t arg0
, arg1
= NULL
;
1297 bool anyconst
= false;
1298 arg0
= &operands
[1];
1299 if (operands
.length () > 2)
1300 arg1
= &operands
[2];
1301 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1302 || (arg0
->opcode
== ADDR_EXPR
1303 && is_gimple_min_invariant (arg0
->op0
)))
1306 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1307 || (arg1
->opcode
== ADDR_EXPR
1308 && is_gimple_min_invariant (arg1
->op0
))))
1312 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1315 arg1
? arg1
->op0
: NULL
);
1317 && TREE_CODE (folded
) == NOP_EXPR
)
1318 folded
= TREE_OPERAND (folded
, 0);
1320 && is_gimple_min_invariant (folded
))
1325 /* Simplify reads from constant strings. */
1326 else if (op
->opcode
== ARRAY_REF
1327 && TREE_CODE (op
->op0
) == INTEGER_CST
1328 && integer_zerop (op
->op1
)
1329 && operands
.length () == 2)
1331 vn_reference_op_t arg0
;
1332 arg0
= &operands
[1];
1333 if (arg0
->opcode
== STRING_CST
1334 && (TYPE_MODE (op
->type
)
1335 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1336 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1337 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1338 && tree_int_cst_sgn (op
->op0
) >= 0
1339 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1340 return build_int_cst_type (op
->type
,
1341 (TREE_STRING_POINTER (arg0
->op0
)
1342 [TREE_INT_CST_LOW (op
->op0
)]));
1348 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1349 structures into their value numbers. This is done in-place, and
1350 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1351 whether any operands were valueized. */
1353 static vec
<vn_reference_op_s
>
1354 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1356 vn_reference_op_t vro
;
1359 *valueized_anything
= false;
1361 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1363 if (vro
->opcode
== SSA_NAME
1364 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1366 tree tem
= SSA_VAL (vro
->op0
);
1367 if (tem
!= vro
->op0
)
1369 *valueized_anything
= true;
1372 /* If it transforms from an SSA_NAME to a constant, update
1374 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1375 vro
->opcode
= TREE_CODE (vro
->op0
);
1377 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1379 tree tem
= SSA_VAL (vro
->op1
);
1380 if (tem
!= vro
->op1
)
1382 *valueized_anything
= true;
1386 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1388 tree tem
= SSA_VAL (vro
->op2
);
1389 if (tem
!= vro
->op2
)
1391 *valueized_anything
= true;
1395 /* If it transforms from an SSA_NAME to an address, fold with
1396 a preceding indirect reference. */
1399 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1400 && orig
[i
- 1].opcode
== MEM_REF
)
1401 vn_reference_fold_indirect (&orig
, &i
);
1403 && vro
->opcode
== SSA_NAME
1404 && orig
[i
- 1].opcode
== MEM_REF
)
1405 vn_reference_maybe_forwprop_address (&orig
, &i
);
1406 /* If it transforms a non-constant ARRAY_REF into a constant
1407 one, adjust the constant offset. */
1408 else if (vro
->opcode
== ARRAY_REF
1410 && TREE_CODE (vro
->op0
) == INTEGER_CST
1411 && TREE_CODE (vro
->op1
) == INTEGER_CST
1412 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1414 offset_int off
= ((wi::to_offset (vro
->op0
)
1415 - wi::to_offset (vro
->op1
))
1416 * wi::to_offset (vro
->op2
));
1417 if (wi::fits_shwi_p (off
))
1418 vro
->off
= off
.to_shwi ();
1425 static vec
<vn_reference_op_s
>
1426 valueize_refs (vec
<vn_reference_op_s
> orig
)
1429 return valueize_refs_1 (orig
, &tem
);
1432 static vec
<vn_reference_op_s
> shared_lookup_references
;
1434 /* Create a vector of vn_reference_op_s structures from REF, a
1435 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1436 this function. *VALUEIZED_ANYTHING will specify whether any
1437 operands were valueized. */
1439 static vec
<vn_reference_op_s
>
1440 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1444 shared_lookup_references
.truncate (0);
1445 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1446 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1447 valueized_anything
);
1448 return shared_lookup_references
;
1451 /* Create a vector of vn_reference_op_s structures from CALL, a
1452 call statement. The vector is shared among all callers of
1455 static vec
<vn_reference_op_s
>
1456 valueize_shared_reference_ops_from_call (gimple call
)
1460 shared_lookup_references
.truncate (0);
1461 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1462 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1463 return shared_lookup_references
;
1466 /* Lookup a SCCVN reference operation VR in the current hash table.
1467 Returns the resulting value number if it exists in the hash table,
1468 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1469 vn_reference_t stored in the hashtable if something is found. */
1472 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1474 vn_reference_s
**slot
;
1477 hash
= vr
->hashcode
;
1478 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1479 if (!slot
&& current_info
== optimistic_info
)
1480 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1484 *vnresult
= (vn_reference_t
)*slot
;
1485 return ((vn_reference_t
)*slot
)->result
;
1491 static tree
*last_vuse_ptr
;
1492 static vn_lookup_kind vn_walk_kind
;
1493 static vn_lookup_kind default_vn_walk_kind
;
1495 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1496 with the current VUSE and performs the expression lookup. */
1499 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1500 unsigned int cnt
, void *vr_
)
1502 vn_reference_t vr
= (vn_reference_t
)vr_
;
1503 vn_reference_s
**slot
;
1506 /* This bounds the stmt walks we perform on reference lookups
1507 to O(1) instead of O(N) where N is the number of dominating
1509 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1513 *last_vuse_ptr
= vuse
;
1515 /* Fixup vuse and hash. */
1517 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1518 vr
->vuse
= vuse_ssa_val (vuse
);
1520 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1522 hash
= vr
->hashcode
;
1523 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1524 if (!slot
&& current_info
== optimistic_info
)
1525 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1532 /* Lookup an existing or insert a new vn_reference entry into the
1533 value table for the VUSE, SET, TYPE, OPERANDS reference which
1534 has the value VALUE which is either a constant or an SSA name. */
1536 static vn_reference_t
1537 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1540 vec
<vn_reference_op_s
,
1544 struct vn_reference_s vr1
;
1545 vn_reference_t result
;
1548 vr1
.operands
= operands
;
1551 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1552 if (vn_reference_lookup_1 (&vr1
, &result
))
1554 if (TREE_CODE (value
) == SSA_NAME
)
1555 value_id
= VN_INFO (value
)->value_id
;
1557 value_id
= get_or_alloc_constant_value_id (value
);
1558 return vn_reference_insert_pieces (vuse
, set
, type
,
1559 operands
.copy (), value
, value_id
);
1562 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1563 from the statement defining VUSE and if not successful tries to
1564 translate *REFP and VR_ through an aggregate copy at the definition
1568 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
,
1569 bool disambiguate_only
)
1571 vn_reference_t vr
= (vn_reference_t
)vr_
;
1572 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1574 HOST_WIDE_INT offset
, maxsize
;
1575 static vec
<vn_reference_op_s
>
1578 bool lhs_ref_ok
= false;
1580 /* First try to disambiguate after value-replacing in the definitions LHS. */
1581 if (is_gimple_assign (def_stmt
))
1583 vec
<vn_reference_op_s
> tem
;
1584 tree lhs
= gimple_assign_lhs (def_stmt
);
1585 bool valueized_anything
= false;
1586 /* Avoid re-allocation overhead. */
1587 lhs_ops
.truncate (0);
1588 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1590 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1591 gcc_assert (lhs_ops
== tem
);
1592 if (valueized_anything
)
1594 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1595 get_alias_set (lhs
),
1596 TREE_TYPE (lhs
), lhs_ops
);
1598 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1603 ao_ref_init (&lhs_ref
, lhs
);
1607 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
1608 && gimple_call_num_args (def_stmt
) <= 4)
1610 /* For builtin calls valueize its arguments and call the
1611 alias oracle again. Valueization may improve points-to
1612 info of pointers and constify size and position arguments.
1613 Originally this was motivated by PR61034 which has
1614 conditional calls to free falsely clobbering ref because
1615 of imprecise points-to info of the argument. */
1617 bool valueized_anything
= false;
1618 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1620 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
1621 if (TREE_CODE (oldargs
[i
]) == SSA_NAME
1622 && VN_INFO (oldargs
[i
])->valnum
!= oldargs
[i
])
1624 gimple_call_set_arg (def_stmt
, i
, VN_INFO (oldargs
[i
])->valnum
);
1625 valueized_anything
= true;
1628 if (valueized_anything
)
1630 bool res
= call_may_clobber_ref_p_1 (def_stmt
, ref
);
1631 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1632 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
1638 if (disambiguate_only
)
1641 base
= ao_ref_base (ref
);
1642 offset
= ref
->offset
;
1643 maxsize
= ref
->max_size
;
1645 /* If we cannot constrain the size of the reference we cannot
1646 test if anything kills it. */
1650 /* We can't deduce anything useful from clobbers. */
1651 if (gimple_clobber_p (def_stmt
))
1654 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1655 from that definition.
1657 if (is_gimple_reg_type (vr
->type
)
1658 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1659 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1660 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1661 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1663 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1665 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1666 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1667 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1668 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1669 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1671 && operand_equal_p (base
, base2
, 0)
1672 && offset2
<= offset
1673 && offset2
+ size2
>= offset
+ maxsize
)
1675 tree val
= build_zero_cst (vr
->type
);
1676 return vn_reference_lookup_or_insert_for_pieces
1677 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1681 /* 2) Assignment from an empty CONSTRUCTOR. */
1682 else if (is_gimple_reg_type (vr
->type
)
1683 && gimple_assign_single_p (def_stmt
)
1684 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1685 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1688 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1689 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1690 &offset2
, &size2
, &maxsize2
);
1692 && operand_equal_p (base
, base2
, 0)
1693 && offset2
<= offset
1694 && offset2
+ size2
>= offset
+ maxsize
)
1696 tree val
= build_zero_cst (vr
->type
);
1697 return vn_reference_lookup_or_insert_for_pieces
1698 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1702 /* 3) Assignment from a constant. We can use folds native encode/interpret
1703 routines to extract the assigned bits. */
1704 else if (vn_walk_kind
== VN_WALKREWRITE
1705 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1706 && ref
->size
== maxsize
1707 && maxsize
% BITS_PER_UNIT
== 0
1708 && offset
% BITS_PER_UNIT
== 0
1709 && is_gimple_reg_type (vr
->type
)
1710 && gimple_assign_single_p (def_stmt
)
1711 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1714 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1715 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1716 &offset2
, &size2
, &maxsize2
);
1718 && maxsize2
== size2
1719 && size2
% BITS_PER_UNIT
== 0
1720 && offset2
% BITS_PER_UNIT
== 0
1721 && operand_equal_p (base
, base2
, 0)
1722 && offset2
<= offset
1723 && offset2
+ size2
>= offset
+ maxsize
)
1725 /* We support up to 512-bit values (for V8DFmode). */
1726 unsigned char buffer
[64];
1729 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1730 buffer
, sizeof (buffer
));
1733 tree val
= native_interpret_expr (vr
->type
,
1735 + ((offset
- offset2
)
1737 ref
->size
/ BITS_PER_UNIT
);
1739 return vn_reference_lookup_or_insert_for_pieces
1740 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1745 /* 4) Assignment from an SSA name which definition we may be able
1746 to access pieces from. */
1747 else if (ref
->size
== maxsize
1748 && is_gimple_reg_type (vr
->type
)
1749 && gimple_assign_single_p (def_stmt
)
1750 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1752 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1753 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1754 if (is_gimple_assign (def_stmt2
)
1755 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1756 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1757 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1760 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1761 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1762 &offset2
, &size2
, &maxsize2
);
1763 off
= offset
- offset2
;
1765 && maxsize2
== size2
1766 && operand_equal_p (base
, base2
, 0)
1767 && offset2
<= offset
1768 && offset2
+ size2
>= offset
+ maxsize
)
1770 tree val
= NULL_TREE
;
1772 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1773 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1776 val
= gimple_assign_rhs1 (def_stmt2
);
1777 else if (off
== elsz
)
1778 val
= gimple_assign_rhs2 (def_stmt2
);
1780 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1783 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1784 unsigned i
= off
/ elsz
;
1785 if (i
< CONSTRUCTOR_NELTS (ctor
))
1787 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1788 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1790 if (TREE_CODE (TREE_TYPE (elt
->value
))
1797 return vn_reference_lookup_or_insert_for_pieces
1798 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1803 /* 5) For aggregate copies translate the reference through them if
1804 the copy kills ref. */
1805 else if (vn_walk_kind
== VN_WALKREWRITE
1806 && gimple_assign_single_p (def_stmt
)
1807 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1808 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1809 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1812 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1814 auto_vec
<vn_reference_op_s
> rhs
;
1815 vn_reference_op_t vro
;
1821 /* See if the assignment kills REF. */
1822 base2
= ao_ref_base (&lhs_ref
);
1823 offset2
= lhs_ref
.offset
;
1824 size2
= lhs_ref
.size
;
1825 maxsize2
= lhs_ref
.max_size
;
1827 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1829 || offset2
+ size2
< offset
+ maxsize
)
1832 /* Find the common base of ref and the lhs. lhs_ops already
1833 contains valueized operands for the lhs. */
1834 i
= vr
->operands
.length () - 1;
1835 j
= lhs_ops
.length () - 1;
1836 while (j
>= 0 && i
>= 0
1837 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1843 /* ??? The innermost op should always be a MEM_REF and we already
1844 checked that the assignment to the lhs kills vr. Thus for
1845 aggregate copies using char[] types the vn_reference_op_eq
1846 may fail when comparing types for compatibility. But we really
1847 don't care here - further lookups with the rewritten operands
1848 will simply fail if we messed up types too badly. */
1849 if (j
== 0 && i
>= 0
1850 && lhs_ops
[0].opcode
== MEM_REF
1851 && lhs_ops
[0].off
!= -1
1852 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1855 /* i now points to the first additional op.
1856 ??? LHS may not be completely contained in VR, one or more
1857 VIEW_CONVERT_EXPRs could be in its way. We could at least
1858 try handling outermost VIEW_CONVERT_EXPRs. */
1862 /* Now re-write REF to be based on the rhs of the assignment. */
1863 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1864 /* We need to pre-pend vr->operands[0..i] to rhs. */
1865 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1867 vec
<vn_reference_op_s
> old
= vr
->operands
;
1868 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1869 if (old
== shared_lookup_references
1870 && vr
->operands
!= old
)
1871 shared_lookup_references
= vNULL
;
1874 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1875 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1876 vr
->operands
[i
+ 1 + j
] = *vro
;
1877 vr
->operands
= valueize_refs (vr
->operands
);
1878 vr
->hashcode
= vn_reference_compute_hash (vr
);
1880 /* Adjust *ref from the new operands. */
1881 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1883 /* This can happen with bitfields. */
1884 if (ref
->size
!= r
.size
)
1888 /* Do not update last seen VUSE after translating. */
1889 last_vuse_ptr
= NULL
;
1891 /* Keep looking for the adjusted *REF / VR pair. */
1895 /* 6) For memcpy copies translate the reference through them if
1896 the copy kills ref. */
1897 else if (vn_walk_kind
== VN_WALKREWRITE
1898 && is_gimple_reg_type (vr
->type
)
1899 /* ??? Handle BCOPY as well. */
1900 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1901 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1902 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1903 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1904 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1905 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1906 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1907 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
1911 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1912 vn_reference_op_s op
;
1916 /* Only handle non-variable, addressable refs. */
1917 if (ref
->size
!= maxsize
1918 || offset
% BITS_PER_UNIT
!= 0
1919 || ref
->size
% BITS_PER_UNIT
!= 0)
1922 /* Extract a pointer base and an offset for the destination. */
1923 lhs
= gimple_call_arg (def_stmt
, 0);
1925 if (TREE_CODE (lhs
) == SSA_NAME
)
1926 lhs
= SSA_VAL (lhs
);
1927 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1929 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1933 if (TREE_CODE (tem
) == MEM_REF
1934 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1936 lhs
= TREE_OPERAND (tem
, 0);
1937 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1939 else if (DECL_P (tem
))
1940 lhs
= build_fold_addr_expr (tem
);
1944 if (TREE_CODE (lhs
) != SSA_NAME
1945 && TREE_CODE (lhs
) != ADDR_EXPR
)
1948 /* Extract a pointer base and an offset for the source. */
1949 rhs
= gimple_call_arg (def_stmt
, 1);
1951 if (TREE_CODE (rhs
) == SSA_NAME
)
1952 rhs
= SSA_VAL (rhs
);
1953 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1955 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1959 if (TREE_CODE (tem
) == MEM_REF
1960 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1962 rhs
= TREE_OPERAND (tem
, 0);
1963 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1965 else if (DECL_P (tem
))
1966 rhs
= build_fold_addr_expr (tem
);
1970 if (TREE_CODE (rhs
) != SSA_NAME
1971 && TREE_CODE (rhs
) != ADDR_EXPR
)
1974 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
1976 /* The bases of the destination and the references have to agree. */
1977 if ((TREE_CODE (base
) != MEM_REF
1979 || (TREE_CODE (base
) == MEM_REF
1980 && (TREE_OPERAND (base
, 0) != lhs
1981 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
1983 && (TREE_CODE (lhs
) != ADDR_EXPR
1984 || TREE_OPERAND (lhs
, 0) != base
)))
1987 /* And the access has to be contained within the memcpy destination. */
1988 at
= offset
/ BITS_PER_UNIT
;
1989 if (TREE_CODE (base
) == MEM_REF
)
1990 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
1992 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1995 /* Make room for 2 operands in the new reference. */
1996 if (vr
->operands
.length () < 2)
1998 vec
<vn_reference_op_s
> old
= vr
->operands
;
1999 vr
->operands
.safe_grow_cleared (2);
2000 if (old
== shared_lookup_references
2001 && vr
->operands
!= old
)
2002 shared_lookup_references
.create (0);
2005 vr
->operands
.truncate (2);
2007 /* The looked-through reference is a simple MEM_REF. */
2008 memset (&op
, 0, sizeof (op
));
2010 op
.opcode
= MEM_REF
;
2011 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
2012 op
.off
= at
- lhs_offset
+ rhs_offset
;
2013 vr
->operands
[0] = op
;
2014 op
.type
= TREE_TYPE (rhs
);
2015 op
.opcode
= TREE_CODE (rhs
);
2018 vr
->operands
[1] = op
;
2019 vr
->hashcode
= vn_reference_compute_hash (vr
);
2021 /* Adjust *ref from the new operands. */
2022 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2024 /* This can happen with bitfields. */
2025 if (ref
->size
!= r
.size
)
2029 /* Do not update last seen VUSE after translating. */
2030 last_vuse_ptr
= NULL
;
2032 /* Keep looking for the adjusted *REF / VR pair. */
2036 /* Bail out and stop walking. */
2040 /* Lookup a reference operation by it's parts, in the current hash table.
2041 Returns the resulting value number if it exists in the hash table,
2042 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2043 vn_reference_t stored in the hashtable if something is found. */
2046 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2047 vec
<vn_reference_op_s
> operands
,
2048 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2050 struct vn_reference_s vr1
;
2058 vr1
.vuse
= vuse_ssa_val (vuse
);
2059 shared_lookup_references
.truncate (0);
2060 shared_lookup_references
.safe_grow (operands
.length ());
2061 memcpy (shared_lookup_references
.address (),
2062 operands
.address (),
2063 sizeof (vn_reference_op_s
)
2064 * operands
.length ());
2065 vr1
.operands
= operands
= shared_lookup_references
2066 = valueize_refs (shared_lookup_references
);
2069 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2070 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2073 vn_reference_lookup_1 (&vr1
, vnresult
);
2075 && kind
!= VN_NOWALK
2079 vn_walk_kind
= kind
;
2080 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2082 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2083 vn_reference_lookup_2
,
2084 vn_reference_lookup_3
, &vr1
);
2085 if (vr1
.operands
!= operands
)
2086 vr1
.operands
.release ();
2090 return (*vnresult
)->result
;
2095 /* Lookup OP in the current hash table, and return the resulting value
2096 number if it exists in the hash table. Return NULL_TREE if it does
2097 not exist in the hash table or if the result field of the structure
2098 was NULL.. VNRESULT will be filled in with the vn_reference_t
2099 stored in the hashtable if one exists. */
2102 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2103 vn_reference_t
*vnresult
)
2105 vec
<vn_reference_op_s
> operands
;
2106 struct vn_reference_s vr1
;
2108 bool valuezied_anything
;
2113 vr1
.vuse
= vuse_ssa_val (vuse
);
2114 vr1
.operands
= operands
2115 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2116 vr1
.type
= TREE_TYPE (op
);
2117 vr1
.set
= get_alias_set (op
);
2118 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2119 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2122 if (kind
!= VN_NOWALK
2125 vn_reference_t wvnresult
;
2127 /* Make sure to use a valueized reference if we valueized anything.
2128 Otherwise preserve the full reference for advanced TBAA. */
2129 if (!valuezied_anything
2130 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2132 ao_ref_init (&r
, op
);
2133 vn_walk_kind
= kind
;
2135 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2136 vn_reference_lookup_2
,
2137 vn_reference_lookup_3
, &vr1
);
2138 if (vr1
.operands
!= operands
)
2139 vr1
.operands
.release ();
2143 *vnresult
= wvnresult
;
2144 return wvnresult
->result
;
2150 return vn_reference_lookup_1 (&vr1
, vnresult
);
2154 /* Insert OP into the current hash table with a value number of
2155 RESULT, and return the resulting reference structure we created. */
2158 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2160 vn_reference_s
**slot
;
2164 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2165 if (TREE_CODE (result
) == SSA_NAME
)
2166 vr1
->value_id
= VN_INFO (result
)->value_id
;
2168 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2169 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2170 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2171 vr1
->type
= TREE_TYPE (op
);
2172 vr1
->set
= get_alias_set (op
);
2173 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2174 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2175 vr1
->result_vdef
= vdef
;
2177 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2180 /* Because we lookup stores using vuses, and value number failures
2181 using the vdefs (see visit_reference_op_store for how and why),
2182 it's possible that on failure we may try to insert an already
2183 inserted store. This is not wrong, there is no ssa name for a
2184 store that we could use as a differentiator anyway. Thus, unlike
2185 the other lookup functions, you cannot gcc_assert (!*slot)
2188 /* But free the old slot in case of a collision. */
2190 free_reference (*slot
);
2196 /* Insert a reference by it's pieces into the current hash table with
2197 a value number of RESULT. Return the resulting reference
2198 structure we created. */
2201 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2202 vec
<vn_reference_op_s
> operands
,
2203 tree result
, unsigned int value_id
)
2206 vn_reference_s
**slot
;
2209 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2210 vr1
->value_id
= value_id
;
2211 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2212 vr1
->operands
= valueize_refs (operands
);
2215 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2216 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2217 result
= SSA_VAL (result
);
2218 vr1
->result
= result
;
2220 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2223 /* At this point we should have all the things inserted that we have
2224 seen before, and we should never try inserting something that
2226 gcc_assert (!*slot
);
2228 free_reference (*slot
);
2234 /* Compute and return the hash value for nary operation VBO1. */
2237 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2242 for (i
= 0; i
< vno1
->length
; ++i
)
2243 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2244 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2246 if (vno1
->length
== 2
2247 && commutative_tree_code (vno1
->opcode
)
2248 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2250 tree temp
= vno1
->op
[0];
2251 vno1
->op
[0] = vno1
->op
[1];
2255 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2256 for (i
= 0; i
< vno1
->length
; ++i
)
2257 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2262 /* Compare nary operations VNO1 and VNO2 and return true if they are
2266 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2270 if (vno1
->hashcode
!= vno2
->hashcode
)
2273 if (vno1
->length
!= vno2
->length
)
2276 if (vno1
->opcode
!= vno2
->opcode
2277 || !types_compatible_p (vno1
->type
, vno2
->type
))
2280 for (i
= 0; i
< vno1
->length
; ++i
)
2281 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2287 /* Initialize VNO from the pieces provided. */
2290 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2291 enum tree_code code
, tree type
, tree
*ops
)
2294 vno
->length
= length
;
2296 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2299 /* Initialize VNO from OP. */
2302 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2306 vno
->opcode
= TREE_CODE (op
);
2307 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2308 vno
->type
= TREE_TYPE (op
);
2309 for (i
= 0; i
< vno
->length
; ++i
)
2310 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2313 /* Return the number of operands for a vn_nary ops structure from STMT. */
2316 vn_nary_length_from_stmt (gimple stmt
)
2318 switch (gimple_assign_rhs_code (stmt
))
2322 case VIEW_CONVERT_EXPR
:
2329 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2332 return gimple_num_ops (stmt
) - 1;
2336 /* Initialize VNO from STMT. */
2339 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2343 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2344 vno
->type
= gimple_expr_type (stmt
);
2345 switch (vno
->opcode
)
2349 case VIEW_CONVERT_EXPR
:
2351 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2356 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2357 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2358 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2362 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2363 for (i
= 0; i
< vno
->length
; ++i
)
2364 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2368 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2369 vno
->length
= gimple_num_ops (stmt
) - 1;
2370 for (i
= 0; i
< vno
->length
; ++i
)
2371 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2375 /* Compute the hashcode for VNO and look for it in the hash table;
2376 return the resulting value number if it exists in the hash table.
2377 Return NULL_TREE if it does not exist in the hash table or if the
2378 result field of the operation is NULL. VNRESULT will contain the
2379 vn_nary_op_t from the hashtable if it exists. */
2382 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2384 vn_nary_op_s
**slot
;
2389 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2390 slot
= current_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2392 if (!slot
&& current_info
== optimistic_info
)
2393 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2399 return (*slot
)->result
;
2402 /* Lookup a n-ary operation by its pieces and return the resulting value
2403 number if it exists in the hash table. Return NULL_TREE if it does
2404 not exist in the hash table or if the result field of the operation
2405 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2409 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2410 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2412 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2413 sizeof_vn_nary_op (length
));
2414 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2415 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2418 /* Lookup OP in the current hash table, and return the resulting value
2419 number if it exists in the hash table. Return NULL_TREE if it does
2420 not exist in the hash table or if the result field of the operation
2421 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2425 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2428 = XALLOCAVAR (struct vn_nary_op_s
,
2429 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2430 init_vn_nary_op_from_op (vno1
, op
);
2431 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2434 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2435 value number if it exists in the hash table. Return NULL_TREE if
2436 it does not exist in the hash table. VNRESULT will contain the
2437 vn_nary_op_t from the hashtable if it exists. */
2440 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2443 = XALLOCAVAR (struct vn_nary_op_s
,
2444 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2445 init_vn_nary_op_from_stmt (vno1
, stmt
);
2446 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2449 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2452 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2454 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2457 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2461 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2463 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2464 ¤t_info
->nary_obstack
);
2466 vno1
->value_id
= value_id
;
2467 vno1
->length
= length
;
2468 vno1
->result
= result
;
2473 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2474 VNO->HASHCODE first. */
2477 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
2480 vn_nary_op_s
**slot
;
2483 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2485 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2486 gcc_assert (!*slot
);
2492 /* Insert a n-ary operation into the current hash table using it's
2493 pieces. Return the vn_nary_op_t structure we created and put in
2497 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2498 tree type
, tree
*ops
,
2499 tree result
, unsigned int value_id
)
2501 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2502 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2503 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2506 /* Insert OP into the current hash table with a value number of
2507 RESULT. Return the vn_nary_op_t structure we created and put in
2511 vn_nary_op_insert (tree op
, tree result
)
2513 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2516 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2517 init_vn_nary_op_from_op (vno1
, op
);
2518 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2521 /* Insert the rhs of STMT into the current hash table with a value number of
2525 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2528 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2529 result
, VN_INFO (result
)->value_id
);
2530 init_vn_nary_op_from_stmt (vno1
, stmt
);
2531 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2534 /* Compute a hashcode for PHI operation VP1 and return it. */
2536 static inline hashval_t
2537 vn_phi_compute_hash (vn_phi_t vp1
)
2544 result
= vp1
->block
->index
;
2546 /* If all PHI arguments are constants we need to distinguish
2547 the PHI node via its type. */
2549 result
+= vn_hash_type (type
);
2551 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2553 if (phi1op
== VN_TOP
)
2555 result
= iterative_hash_expr (phi1op
, result
);
2561 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2564 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2566 if (vp1
->hashcode
!= vp2
->hashcode
)
2569 if (vp1
->block
== vp2
->block
)
2574 /* If the PHI nodes do not have compatible types
2575 they are not the same. */
2576 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2579 /* Any phi in the same block will have it's arguments in the
2580 same edge order, because of how we store phi nodes. */
2581 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2583 tree phi2op
= vp2
->phiargs
[i
];
2584 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2586 if (!expressions_equal_p (phi1op
, phi2op
))
2594 static vec
<tree
> shared_lookup_phiargs
;
2596 /* Lookup PHI in the current hash table, and return the resulting
2597 value number if it exists in the hash table. Return NULL_TREE if
2598 it does not exist in the hash table. */
2601 vn_phi_lookup (gimple phi
)
2604 struct vn_phi_s vp1
;
2607 shared_lookup_phiargs
.truncate (0);
2609 /* Canonicalize the SSA_NAME's to their value number. */
2610 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2612 tree def
= PHI_ARG_DEF (phi
, i
);
2613 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2614 shared_lookup_phiargs
.safe_push (def
);
2616 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2617 vp1
.phiargs
= shared_lookup_phiargs
;
2618 vp1
.block
= gimple_bb (phi
);
2619 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2620 slot
= current_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2622 if (!slot
&& current_info
== optimistic_info
)
2623 slot
= valid_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2627 return (*slot
)->result
;
2630 /* Insert PHI into the current hash table with a value number of
2634 vn_phi_insert (gimple phi
, tree result
)
2637 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2639 vec
<tree
> args
= vNULL
;
2641 /* Canonicalize the SSA_NAME's to their value number. */
2642 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2644 tree def
= PHI_ARG_DEF (phi
, i
);
2645 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2646 args
.safe_push (def
);
2648 vp1
->value_id
= VN_INFO (result
)->value_id
;
2649 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2650 vp1
->phiargs
= args
;
2651 vp1
->block
= gimple_bb (phi
);
2652 vp1
->result
= result
;
2653 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2655 slot
= current_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2657 /* Because we iterate over phi operations more than once, it's
2658 possible the slot might already exist here, hence no assert.*/
2664 /* Print set of components in strongly connected component SCC to OUT. */
2667 print_scc (FILE *out
, vec
<tree
> scc
)
2672 fprintf (out
, "SCC consists of:");
2673 FOR_EACH_VEC_ELT (scc
, i
, var
)
2676 print_generic_expr (out
, var
, 0);
2678 fprintf (out
, "\n");
2681 /* Set the value number of FROM to TO, return true if it has changed
2685 set_ssa_val_to (tree from
, tree to
)
2687 tree currval
= SSA_VAL (from
);
2688 HOST_WIDE_INT toff
, coff
;
2690 /* The only thing we allow as value numbers are ssa_names
2691 and invariants. So assert that here. We don't allow VN_TOP
2692 as visiting a stmt should produce a value-number other than
2694 ??? Still VN_TOP can happen for unreachable code, so force
2695 it to varying in that case. Not all code is prepared to
2696 get VN_TOP on valueization. */
2699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2700 fprintf (dump_file
, "Forcing value number to varying on "
2701 "receiving VN_TOP\n");
2705 gcc_assert (to
!= NULL_TREE
2706 && (TREE_CODE (to
) == SSA_NAME
2707 || is_gimple_min_invariant (to
)));
2711 if (currval
== from
)
2713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2715 fprintf (dump_file
, "Not changing value number of ");
2716 print_generic_expr (dump_file
, from
, 0);
2717 fprintf (dump_file
, " from VARYING to ");
2718 print_generic_expr (dump_file
, to
, 0);
2719 fprintf (dump_file
, "\n");
2723 else if (TREE_CODE (to
) == SSA_NAME
2724 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2728 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2730 fprintf (dump_file
, "Setting value number of ");
2731 print_generic_expr (dump_file
, from
, 0);
2732 fprintf (dump_file
, " to ");
2733 print_generic_expr (dump_file
, to
, 0);
2737 && !operand_equal_p (currval
, to
, 0)
2738 /* ??? For addresses involving volatile objects or types operand_equal_p
2739 does not reliably detect ADDR_EXPRs as equal. We know we are only
2740 getting invariant gimple addresses here, so can use
2741 get_addr_base_and_unit_offset to do this comparison. */
2742 && !(TREE_CODE (currval
) == ADDR_EXPR
2743 && TREE_CODE (to
) == ADDR_EXPR
2744 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2745 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2748 VN_INFO (from
)->valnum
= to
;
2749 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2750 fprintf (dump_file
, " (changed)\n");
2753 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2754 fprintf (dump_file
, "\n");
2758 /* Mark as processed all the definitions in the defining stmt of USE, or
2762 mark_use_processed (tree use
)
2766 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2768 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2770 VN_INFO (use
)->use_processed
= true;
2774 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2776 tree def
= DEF_FROM_PTR (defp
);
2778 VN_INFO (def
)->use_processed
= true;
2782 /* Set all definitions in STMT to value number to themselves.
2783 Return true if a value number changed. */
2786 defs_to_varying (gimple stmt
)
2788 bool changed
= false;
2792 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2794 tree def
= DEF_FROM_PTR (defp
);
2795 changed
|= set_ssa_val_to (def
, def
);
2800 static bool expr_has_constants (tree expr
);
2802 /* Visit a copy between LHS and RHS, return true if the value number
2806 visit_copy (tree lhs
, tree rhs
)
2808 /* The copy may have a more interesting constant filled expression
2809 (we don't, since we know our RHS is just an SSA name). */
2810 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2811 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2813 /* And finally valueize. */
2814 rhs
= SSA_VAL (rhs
);
2816 return set_ssa_val_to (lhs
, rhs
);
2819 /* Visit a nary operator RHS, value number it, and return true if the
2820 value number of LHS has changed as a result. */
2823 visit_nary_op (tree lhs
, gimple stmt
)
2825 bool changed
= false;
2826 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2829 changed
= set_ssa_val_to (lhs
, result
);
2832 changed
= set_ssa_val_to (lhs
, lhs
);
2833 vn_nary_op_insert_stmt (stmt
, lhs
);
2839 /* Visit a call STMT storing into LHS. Return true if the value number
2840 of the LHS has changed as a result. */
2843 visit_reference_op_call (tree lhs
, gimple stmt
)
2845 bool changed
= false;
2846 struct vn_reference_s vr1
;
2847 vn_reference_t vnresult
= NULL
;
2848 tree vuse
= gimple_vuse (stmt
);
2849 tree vdef
= gimple_vdef (stmt
);
2851 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2852 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2855 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2856 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2857 vr1
.type
= gimple_expr_type (stmt
);
2859 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2860 vn_reference_lookup_1 (&vr1
, &vnresult
);
2864 if (vnresult
->result_vdef
&& vdef
)
2865 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2867 if (!vnresult
->result
&& lhs
)
2868 vnresult
->result
= lhs
;
2870 if (vnresult
->result
&& lhs
)
2872 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2874 if (VN_INFO (vnresult
->result
)->has_constants
)
2875 VN_INFO (lhs
)->has_constants
= true;
2880 vn_reference_s
**slot
;
2883 changed
|= set_ssa_val_to (vdef
, vdef
);
2885 changed
|= set_ssa_val_to (lhs
, lhs
);
2886 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2887 vr2
->vuse
= vr1
.vuse
;
2888 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2889 vr2
->type
= vr1
.type
;
2891 vr2
->hashcode
= vr1
.hashcode
;
2893 vr2
->result_vdef
= vdef
;
2894 slot
= current_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
2897 free_reference (*slot
);
2904 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2905 and return true if the value number of the LHS has changed as a result. */
2908 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2910 bool changed
= false;
2914 last_vuse
= gimple_vuse (stmt
);
2915 last_vuse_ptr
= &last_vuse
;
2916 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2917 default_vn_walk_kind
, NULL
);
2918 last_vuse_ptr
= NULL
;
2920 /* If we have a VCE, try looking up its operand as it might be stored in
2921 a different type. */
2922 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2923 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2924 default_vn_walk_kind
, NULL
);
2926 /* We handle type-punning through unions by value-numbering based
2927 on offset and size of the access. Be prepared to handle a
2928 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2930 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2932 /* We will be setting the value number of lhs to the value number
2933 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2934 So first simplify and lookup this expression to see if it
2935 is already available. */
2936 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2937 if ((CONVERT_EXPR_P (val
)
2938 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2939 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2941 tree tem
= vn_get_expr_for (TREE_OPERAND (val
, 0));
2942 if ((CONVERT_EXPR_P (tem
)
2943 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2944 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2945 TREE_TYPE (val
), tem
)))
2949 if (!is_gimple_min_invariant (val
)
2950 && TREE_CODE (val
) != SSA_NAME
)
2951 result
= vn_nary_op_lookup (val
, NULL
);
2952 /* If the expression is not yet available, value-number lhs to
2953 a new SSA_NAME we create. */
2956 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2958 /* Initialize value-number information properly. */
2959 VN_INFO_GET (result
)->valnum
= result
;
2960 VN_INFO (result
)->value_id
= get_next_value_id ();
2961 VN_INFO (result
)->expr
= val
;
2962 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2963 VN_INFO (result
)->needs_insertion
= true;
2964 /* As all "inserted" statements are singleton SCCs, insert
2965 to the valid table. This is strictly needed to
2966 avoid re-generating new value SSA_NAMEs for the same
2967 expression during SCC iteration over and over (the
2968 optimistic table gets cleared after each iteration).
2969 We do not need to insert into the optimistic table, as
2970 lookups there will fall back to the valid table. */
2971 if (current_info
== optimistic_info
)
2973 current_info
= valid_info
;
2974 vn_nary_op_insert (val
, result
);
2975 current_info
= optimistic_info
;
2978 vn_nary_op_insert (val
, result
);
2979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2981 fprintf (dump_file
, "Inserting name ");
2982 print_generic_expr (dump_file
, result
, 0);
2983 fprintf (dump_file
, " for expression ");
2984 print_generic_expr (dump_file
, val
, 0);
2985 fprintf (dump_file
, "\n");
2992 changed
= set_ssa_val_to (lhs
, result
);
2993 if (TREE_CODE (result
) == SSA_NAME
2994 && VN_INFO (result
)->has_constants
)
2996 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2997 VN_INFO (lhs
)->has_constants
= true;
3002 changed
= set_ssa_val_to (lhs
, lhs
);
3003 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
3010 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3011 and return true if the value number of the LHS has changed as a result. */
3014 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
3016 bool changed
= false;
3017 vn_reference_t vnresult
= NULL
;
3018 tree result
, assign
;
3019 bool resultsame
= false;
3020 tree vuse
= gimple_vuse (stmt
);
3021 tree vdef
= gimple_vdef (stmt
);
3023 /* First we want to lookup using the *vuses* from the store and see
3024 if there the last store to this location with the same address
3027 The vuses represent the memory state before the store. If the
3028 memory state, address, and value of the store is the same as the
3029 last store to this location, then this store will produce the
3030 same memory state as that store.
3032 In this case the vdef versions for this store are value numbered to those
3033 vuse versions, since they represent the same memory state after
3036 Otherwise, the vdefs for the store are used when inserting into
3037 the table, since the store generates a new memory state. */
3039 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
3043 if (TREE_CODE (result
) == SSA_NAME
)
3044 result
= SSA_VAL (result
);
3045 if (TREE_CODE (op
) == SSA_NAME
)
3047 resultsame
= expressions_equal_p (result
, op
);
3050 if (!result
|| !resultsame
)
3052 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3053 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
3056 VN_INFO (vdef
)->use_processed
= true;
3057 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3061 if (!result
|| !resultsame
)
3063 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3065 fprintf (dump_file
, "No store match\n");
3066 fprintf (dump_file
, "Value numbering store ");
3067 print_generic_expr (dump_file
, lhs
, 0);
3068 fprintf (dump_file
, " to ");
3069 print_generic_expr (dump_file
, op
, 0);
3070 fprintf (dump_file
, "\n");
3072 /* Have to set value numbers before insert, since insert is
3073 going to valueize the references in-place. */
3076 changed
|= set_ssa_val_to (vdef
, vdef
);
3079 /* Do not insert structure copies into the tables. */
3080 if (is_gimple_min_invariant (op
)
3081 || is_gimple_reg (op
))
3082 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3084 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3085 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3089 /* We had a match, so value number the vdef to have the value
3090 number of the vuse it came from. */
3092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3093 fprintf (dump_file
, "Store matched earlier value,"
3094 "value numbering store vdefs to matching vuses.\n");
3096 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3102 /* Visit and value number PHI, return true if the value number
3106 visit_phi (gimple phi
)
3108 bool changed
= false;
3110 tree sameval
= VN_TOP
;
3111 bool allsame
= true;
3113 /* TODO: We could check for this in init_sccvn, and replace this
3114 with a gcc_assert. */
3115 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3116 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3118 /* See if all non-TOP arguments have the same value. TOP is
3119 equivalent to everything, so we can ignore it. */
3122 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3123 if (e
->flags
& EDGE_EXECUTABLE
)
3125 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3127 if (TREE_CODE (def
) == SSA_NAME
)
3128 def
= SSA_VAL (def
);
3131 if (sameval
== VN_TOP
)
3137 if (!expressions_equal_p (def
, sameval
))
3145 /* If all value numbered to the same value, the phi node has that
3148 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3150 /* Otherwise, see if it is equivalent to a phi node in this block. */
3151 result
= vn_phi_lookup (phi
);
3153 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3156 vn_phi_insert (phi
, PHI_RESULT (phi
));
3157 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3158 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3159 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3165 /* Return true if EXPR contains constants. */
3168 expr_has_constants (tree expr
)
3170 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3173 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3176 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3177 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3178 /* Constants inside reference ops are rarely interesting, but
3179 it can take a lot of looking to find them. */
3181 case tcc_declaration
:
3184 return is_gimple_min_invariant (expr
);
3189 /* Return true if STMT contains constants. */
3192 stmt_has_constants (gimple stmt
)
3196 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3199 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3201 case GIMPLE_TERNARY_RHS
:
3202 tem
= gimple_assign_rhs3 (stmt
);
3203 if (TREE_CODE (tem
) == SSA_NAME
)
3204 tem
= SSA_VAL (tem
);
3205 if (is_gimple_min_invariant (tem
))
3209 case GIMPLE_BINARY_RHS
:
3210 tem
= gimple_assign_rhs2 (stmt
);
3211 if (TREE_CODE (tem
) == SSA_NAME
)
3212 tem
= SSA_VAL (tem
);
3213 if (is_gimple_min_invariant (tem
))
3217 case GIMPLE_SINGLE_RHS
:
3218 /* Constants inside reference ops are rarely interesting, but
3219 it can take a lot of looking to find them. */
3220 case GIMPLE_UNARY_RHS
:
3221 tem
= gimple_assign_rhs1 (stmt
);
3222 if (TREE_CODE (tem
) == SSA_NAME
)
3223 tem
= SSA_VAL (tem
);
3224 return is_gimple_min_invariant (tem
);
3232 /* Simplify the binary expression RHS, and return the result if
3236 simplify_binary_expression (gimple stmt
)
3238 tree result
= NULL_TREE
;
3239 tree op0
= gimple_assign_rhs1 (stmt
);
3240 tree op1
= gimple_assign_rhs2 (stmt
);
3241 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3243 /* This will not catch every single case we could combine, but will
3244 catch those with constants. The goal here is to simultaneously
3245 combine constants between expressions, but avoid infinite
3246 expansion of expressions during simplification. */
3247 op0
= vn_valueize (op0
);
3248 if (TREE_CODE (op0
) == SSA_NAME
3249 && (VN_INFO (op0
)->has_constants
3250 || TREE_CODE_CLASS (code
) == tcc_comparison
3251 || code
== COMPLEX_EXPR
))
3252 op0
= vn_get_expr_for (op0
);
3254 op1
= vn_valueize (op1
);
3255 if (TREE_CODE (op1
) == SSA_NAME
3256 && (VN_INFO (op1
)->has_constants
3257 || code
== COMPLEX_EXPR
))
3258 op1
= vn_get_expr_for (op1
);
3260 /* Pointer plus constant can be represented as invariant address.
3261 Do so to allow further propatation, see also tree forwprop. */
3262 if (code
== POINTER_PLUS_EXPR
3263 && tree_fits_uhwi_p (op1
)
3264 && TREE_CODE (op0
) == ADDR_EXPR
3265 && is_gimple_min_invariant (op0
))
3266 return build_invariant_address (TREE_TYPE (op0
),
3267 TREE_OPERAND (op0
, 0),
3268 tree_to_uhwi (op1
));
3270 /* Avoid folding if nothing changed. */
3271 if (op0
== gimple_assign_rhs1 (stmt
)
3272 && op1
== gimple_assign_rhs2 (stmt
))
3275 fold_defer_overflow_warnings ();
3277 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3279 STRIP_USELESS_TYPE_CONVERSION (result
);
3281 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3284 /* Make sure result is not a complex expression consisting
3285 of operators of operators (IE (a + b) + (a + c))
3286 Otherwise, we will end up with unbounded expressions if
3287 fold does anything at all. */
3288 if (result
&& valid_gimple_rhs_p (result
))
3294 /* Simplify the unary expression RHS, and return the result if
3298 simplify_unary_expression (gimple stmt
)
3300 tree result
= NULL_TREE
;
3301 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3302 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3304 /* We handle some tcc_reference codes here that are all
3305 GIMPLE_ASSIGN_SINGLE codes. */
3306 if (code
== REALPART_EXPR
3307 || code
== IMAGPART_EXPR
3308 || code
== VIEW_CONVERT_EXPR
3309 || code
== BIT_FIELD_REF
)
3310 op0
= TREE_OPERAND (op0
, 0);
3313 op0
= vn_valueize (op0
);
3314 if (TREE_CODE (op0
) == SSA_NAME
)
3316 if (VN_INFO (op0
)->has_constants
)
3317 op0
= vn_get_expr_for (op0
);
3318 else if (CONVERT_EXPR_CODE_P (code
)
3319 || code
== REALPART_EXPR
3320 || code
== IMAGPART_EXPR
3321 || code
== VIEW_CONVERT_EXPR
3322 || code
== BIT_FIELD_REF
)
3324 /* We want to do tree-combining on conversion-like expressions.
3325 Make sure we feed only SSA_NAMEs or constants to fold though. */
3326 tree tem
= vn_get_expr_for (op0
);
3327 if (UNARY_CLASS_P (tem
)
3328 || BINARY_CLASS_P (tem
)
3329 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3330 || TREE_CODE (tem
) == SSA_NAME
3331 || TREE_CODE (tem
) == CONSTRUCTOR
3332 || is_gimple_min_invariant (tem
))
3337 /* Avoid folding if nothing changed, but remember the expression. */
3338 if (op0
== orig_op0
)
3341 if (code
== BIT_FIELD_REF
)
3343 tree rhs
= gimple_assign_rhs1 (stmt
);
3344 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3345 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3348 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3351 STRIP_USELESS_TYPE_CONVERSION (result
);
3352 if (valid_gimple_rhs_p (result
))
3359 /* Try to simplify RHS using equivalences and constant folding. */
3362 try_to_simplify (gimple stmt
)
3364 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3367 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3368 in this case, there is no point in doing extra work. */
3369 if (code
== SSA_NAME
)
3372 /* First try constant folding based on our current lattice. */
3373 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3375 && (TREE_CODE (tem
) == SSA_NAME
3376 || is_gimple_min_invariant (tem
)))
3379 /* If that didn't work try combining multiple statements. */
3380 switch (TREE_CODE_CLASS (code
))
3383 /* Fallthrough for some unary codes that can operate on registers. */
3384 if (!(code
== REALPART_EXPR
3385 || code
== IMAGPART_EXPR
3386 || code
== VIEW_CONVERT_EXPR
3387 || code
== BIT_FIELD_REF
))
3389 /* We could do a little more with unary ops, if they expand
3390 into binary ops, but it's debatable whether it is worth it. */
3392 return simplify_unary_expression (stmt
);
3394 case tcc_comparison
:
3396 return simplify_binary_expression (stmt
);
3405 /* Visit and value number USE, return true if the value number
3409 visit_use (tree use
)
3411 bool changed
= false;
3412 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3414 mark_use_processed (use
);
3416 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3417 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3418 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3420 fprintf (dump_file
, "Value numbering ");
3421 print_generic_expr (dump_file
, use
, 0);
3422 fprintf (dump_file
, " stmt = ");
3423 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3426 /* Handle uninitialized uses. */
3427 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3428 changed
= set_ssa_val_to (use
, use
);
3431 if (gimple_code (stmt
) == GIMPLE_PHI
)
3432 changed
= visit_phi (stmt
);
3433 else if (gimple_has_volatile_ops (stmt
))
3434 changed
= defs_to_varying (stmt
);
3435 else if (is_gimple_assign (stmt
))
3437 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3438 tree lhs
= gimple_assign_lhs (stmt
);
3439 tree rhs1
= gimple_assign_rhs1 (stmt
);
3442 /* Shortcut for copies. Simplifying copies is pointless,
3443 since we copy the expression and value they represent. */
3444 if (code
== SSA_NAME
3445 && TREE_CODE (lhs
) == SSA_NAME
)
3447 changed
= visit_copy (lhs
, rhs1
);
3450 simplified
= try_to_simplify (stmt
);
3453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3455 fprintf (dump_file
, "RHS ");
3456 print_gimple_expr (dump_file
, stmt
, 0, 0);
3457 fprintf (dump_file
, " simplified to ");
3458 print_generic_expr (dump_file
, simplified
, 0);
3459 if (TREE_CODE (lhs
) == SSA_NAME
)
3460 fprintf (dump_file
, " has constants %d\n",
3461 expr_has_constants (simplified
));
3463 fprintf (dump_file
, "\n");
3466 /* Setting value numbers to constants will occasionally
3467 screw up phi congruence because constants are not
3468 uniquely associated with a single ssa name that can be
3471 && is_gimple_min_invariant (simplified
)
3472 && TREE_CODE (lhs
) == SSA_NAME
)
3474 VN_INFO (lhs
)->expr
= simplified
;
3475 VN_INFO (lhs
)->has_constants
= true;
3476 changed
= set_ssa_val_to (lhs
, simplified
);
3480 && TREE_CODE (simplified
) == SSA_NAME
3481 && TREE_CODE (lhs
) == SSA_NAME
)
3483 changed
= visit_copy (lhs
, simplified
);
3486 else if (simplified
)
3488 if (TREE_CODE (lhs
) == SSA_NAME
)
3490 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3491 /* We have to unshare the expression or else
3492 valuizing may change the IL stream. */
3493 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3496 else if (stmt_has_constants (stmt
)
3497 && TREE_CODE (lhs
) == SSA_NAME
)
3498 VN_INFO (lhs
)->has_constants
= true;
3499 else if (TREE_CODE (lhs
) == SSA_NAME
)
3501 /* We reset expr and constantness here because we may
3502 have been value numbering optimistically, and
3503 iterating. They may become non-constant in this case,
3504 even if they were optimistically constant. */
3506 VN_INFO (lhs
)->has_constants
= false;
3507 VN_INFO (lhs
)->expr
= NULL_TREE
;
3510 if ((TREE_CODE (lhs
) == SSA_NAME
3511 /* We can substitute SSA_NAMEs that are live over
3512 abnormal edges with their constant value. */
3513 && !(gimple_assign_copy_p (stmt
)
3514 && is_gimple_min_invariant (rhs1
))
3516 && is_gimple_min_invariant (simplified
))
3517 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3518 /* Stores or copies from SSA_NAMEs that are live over
3519 abnormal edges are a problem. */
3520 || (code
== SSA_NAME
3521 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3522 changed
= defs_to_varying (stmt
);
3523 else if (REFERENCE_CLASS_P (lhs
)
3525 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3526 else if (TREE_CODE (lhs
) == SSA_NAME
)
3528 if ((gimple_assign_copy_p (stmt
)
3529 && is_gimple_min_invariant (rhs1
))
3531 && is_gimple_min_invariant (simplified
)))
3533 VN_INFO (lhs
)->has_constants
= true;
3535 changed
= set_ssa_val_to (lhs
, simplified
);
3537 changed
= set_ssa_val_to (lhs
, rhs1
);
3541 /* First try to lookup the simplified expression. */
3544 enum gimple_rhs_class rhs_class
;
3547 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3548 if ((rhs_class
== GIMPLE_UNARY_RHS
3549 || rhs_class
== GIMPLE_BINARY_RHS
3550 || rhs_class
== GIMPLE_TERNARY_RHS
)
3551 && valid_gimple_rhs_p (simplified
))
3553 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3556 changed
= set_ssa_val_to (lhs
, result
);
3562 /* Otherwise visit the original statement. */
3563 switch (vn_get_stmt_kind (stmt
))
3566 changed
= visit_nary_op (lhs
, stmt
);
3569 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3572 changed
= defs_to_varying (stmt
);
3578 changed
= defs_to_varying (stmt
);
3580 else if (is_gimple_call (stmt
))
3582 tree lhs
= gimple_call_lhs (stmt
);
3583 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3585 /* Try constant folding based on our current lattice. */
3586 tree simplified
= gimple_fold_stmt_to_constant_1 (stmt
,
3590 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3592 fprintf (dump_file
, "call ");
3593 print_gimple_expr (dump_file
, stmt
, 0, 0);
3594 fprintf (dump_file
, " simplified to ");
3595 print_generic_expr (dump_file
, simplified
, 0);
3596 if (TREE_CODE (lhs
) == SSA_NAME
)
3597 fprintf (dump_file
, " has constants %d\n",
3598 expr_has_constants (simplified
));
3600 fprintf (dump_file
, "\n");
3603 /* Setting value numbers to constants will occasionally
3604 screw up phi congruence because constants are not
3605 uniquely associated with a single ssa name that can be
3608 && is_gimple_min_invariant (simplified
))
3610 VN_INFO (lhs
)->expr
= simplified
;
3611 VN_INFO (lhs
)->has_constants
= true;
3612 changed
= set_ssa_val_to (lhs
, simplified
);
3613 if (gimple_vdef (stmt
))
3614 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3615 gimple_vuse (stmt
));
3619 && TREE_CODE (simplified
) == SSA_NAME
)
3621 changed
= visit_copy (lhs
, simplified
);
3622 if (gimple_vdef (stmt
))
3623 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3624 gimple_vuse (stmt
));
3629 if (stmt_has_constants (stmt
))
3630 VN_INFO (lhs
)->has_constants
= true;
3633 /* We reset expr and constantness here because we may
3634 have been value numbering optimistically, and
3635 iterating. They may become non-constant in this case,
3636 even if they were optimistically constant. */
3637 VN_INFO (lhs
)->has_constants
= false;
3638 VN_INFO (lhs
)->expr
= NULL_TREE
;
3641 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3643 changed
= defs_to_varying (stmt
);
3649 if (!gimple_call_internal_p (stmt
)
3650 && (/* Calls to the same function with the same vuse
3651 and the same operands do not necessarily return the same
3652 value, unless they're pure or const. */
3653 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3654 /* If calls have a vdef, subsequent calls won't have
3655 the same incoming vuse. So, if 2 calls with vdef have the
3656 same vuse, we know they're not subsequent.
3657 We can value number 2 calls to the same function with the
3658 same vuse and the same operands which are not subsequent
3659 the same, because there is no code in the program that can
3660 compare the 2 values... */
3661 || (gimple_vdef (stmt
)
3662 /* ... unless the call returns a pointer which does
3663 not alias with anything else. In which case the
3664 information that the values are distinct are encoded
3666 && !(gimple_call_return_flags (stmt
) & ERF_NOALIAS
))))
3667 changed
= visit_reference_op_call (lhs
, stmt
);
3669 changed
= defs_to_varying (stmt
);
3672 changed
= defs_to_varying (stmt
);
3678 /* Compare two operands by reverse postorder index */
3681 compare_ops (const void *pa
, const void *pb
)
3683 const tree opa
= *((const tree
*)pa
);
3684 const tree opb
= *((const tree
*)pb
);
3685 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3686 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3690 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3691 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3692 else if (gimple_nop_p (opstmta
))
3694 else if (gimple_nop_p (opstmtb
))
3697 bba
= gimple_bb (opstmta
);
3698 bbb
= gimple_bb (opstmtb
);
3701 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3709 if (gimple_code (opstmta
) == GIMPLE_PHI
3710 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3711 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3712 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3714 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3716 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3717 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3719 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3721 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3724 /* Sort an array containing members of a strongly connected component
3725 SCC so that the members are ordered by RPO number.
3726 This means that when the sort is complete, iterating through the
3727 array will give you the members in RPO order. */
3730 sort_scc (vec
<tree
> scc
)
3732 scc
.qsort (compare_ops
);
3735 /* Insert the no longer used nary ONARY to the hash INFO. */
3738 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3740 size_t size
= sizeof_vn_nary_op (onary
->length
);
3741 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3742 &info
->nary_obstack
);
3743 memcpy (nary
, onary
, size
);
3744 vn_nary_op_insert_into (nary
, info
->nary
, false);
3747 /* Insert the no longer used phi OPHI to the hash INFO. */
3750 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3752 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3754 memcpy (phi
, ophi
, sizeof (*phi
));
3755 ophi
->phiargs
.create (0);
3756 slot
= info
->phis
->find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3757 gcc_assert (!*slot
);
3761 /* Insert the no longer used reference OREF to the hash INFO. */
3764 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3767 vn_reference_s
**slot
;
3768 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3769 memcpy (ref
, oref
, sizeof (*ref
));
3770 oref
->operands
.create (0);
3771 slot
= info
->references
->find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3773 free_reference (*slot
);
3777 /* Process a strongly connected component in the SSA graph. */
3780 process_scc (vec
<tree
> scc
)
3784 unsigned int iterations
= 0;
3785 bool changed
= true;
3786 vn_nary_op_iterator_type hin
;
3787 vn_phi_iterator_type hip
;
3788 vn_reference_iterator_type hir
;
3793 /* If the SCC has a single member, just visit it. */
3794 if (scc
.length () == 1)
3797 if (VN_INFO (use
)->use_processed
)
3799 /* We need to make sure it doesn't form a cycle itself, which can
3800 happen for self-referential PHI nodes. In that case we would
3801 end up inserting an expression with VN_TOP operands into the
3802 valid table which makes us derive bogus equivalences later.
3803 The cheapest way to check this is to assume it for all PHI nodes. */
3804 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3805 /* Fallthru to iteration. */ ;
3813 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3814 print_scc (dump_file
, scc
);
3816 /* Iterate over the SCC with the optimistic table until it stops
3818 current_info
= optimistic_info
;
3823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3824 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3825 /* As we are value-numbering optimistically we have to
3826 clear the expression tables and the simplified expressions
3827 in each iteration until we converge. */
3828 optimistic_info
->nary
->empty ();
3829 optimistic_info
->phis
->empty ();
3830 optimistic_info
->references
->empty ();
3831 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3832 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3833 empty_alloc_pool (optimistic_info
->phis_pool
);
3834 empty_alloc_pool (optimistic_info
->references_pool
);
3835 FOR_EACH_VEC_ELT (scc
, i
, var
)
3836 VN_INFO (var
)->expr
= NULL_TREE
;
3837 FOR_EACH_VEC_ELT (scc
, i
, var
)
3838 changed
|= visit_use (var
);
3841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3842 fprintf (dump_file
, "Processing SCC needed %d iterations\n", iterations
);
3843 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3845 /* Finally, copy the contents of the no longer used optimistic
3846 table to the valid table. */
3847 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3848 copy_nary (nary
, valid_info
);
3849 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3850 copy_phi (phi
, valid_info
);
3851 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->references
,
3852 ref
, vn_reference_t
, hir
)
3853 copy_reference (ref
, valid_info
);
3855 current_info
= valid_info
;
3859 /* Pop the components of the found SCC for NAME off the SCC stack
3860 and process them. Returns true if all went well, false if
3861 we run into resource limits. */
3864 extract_and_process_scc_for_name (tree name
)
3869 /* Found an SCC, pop the components off the SCC stack and
3873 x
= sccstack
.pop ();
3875 VN_INFO (x
)->on_sccstack
= false;
3877 } while (x
!= name
);
3879 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3881 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3884 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3885 "SCC size %u exceeding %u\n", scc
.length (),
3886 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3891 if (scc
.length () > 1)
3899 /* Depth first search on NAME to discover and process SCC's in the SSA
3901 Execution of this algorithm relies on the fact that the SCC's are
3902 popped off the stack in topological order.
3903 Returns true if successful, false if we stopped processing SCC's due
3904 to resource constraints. */
3909 vec
<ssa_op_iter
> itervec
= vNULL
;
3910 vec
<tree
> namevec
= vNULL
;
3911 use_operand_p usep
= NULL
;
3918 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3919 VN_INFO (name
)->visited
= true;
3920 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3922 sccstack
.safe_push (name
);
3923 VN_INFO (name
)->on_sccstack
= true;
3924 defstmt
= SSA_NAME_DEF_STMT (name
);
3926 /* Recursively DFS on our operands, looking for SCC's. */
3927 if (!gimple_nop_p (defstmt
))
3929 /* Push a new iterator. */
3930 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3931 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3933 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3936 clear_and_done_ssa_iter (&iter
);
3940 /* If we are done processing uses of a name, go up the stack
3941 of iterators and process SCCs as we found them. */
3942 if (op_iter_done (&iter
))
3944 /* See if we found an SCC. */
3945 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3946 if (!extract_and_process_scc_for_name (name
))
3953 /* Check if we are done. */
3954 if (namevec
.is_empty ())
3961 /* Restore the last use walker and continue walking there. */
3963 name
= namevec
.pop ();
3964 memcpy (&iter
, &itervec
.last (),
3965 sizeof (ssa_op_iter
));
3967 goto continue_walking
;
3970 use
= USE_FROM_PTR (usep
);
3972 /* Since we handle phi nodes, we will sometimes get
3973 invariants in the use expression. */
3974 if (TREE_CODE (use
) == SSA_NAME
)
3976 if (! (VN_INFO (use
)->visited
))
3978 /* Recurse by pushing the current use walking state on
3979 the stack and starting over. */
3980 itervec
.safe_push (iter
);
3981 namevec
.safe_push (name
);
3986 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3987 VN_INFO (use
)->low
);
3989 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3990 && VN_INFO (use
)->on_sccstack
)
3992 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3993 VN_INFO (name
)->low
);
3997 usep
= op_iter_next_use (&iter
);
4001 /* Allocate a value number table. */
4004 allocate_vn_table (vn_tables_t table
)
4006 table
->phis
= new vn_phi_table_type (23);
4007 table
->nary
= new vn_nary_op_table_type (23);
4008 table
->references
= new vn_reference_table_type (23);
4010 gcc_obstack_init (&table
->nary_obstack
);
4011 table
->phis_pool
= create_alloc_pool ("VN phis",
4012 sizeof (struct vn_phi_s
),
4014 table
->references_pool
= create_alloc_pool ("VN references",
4015 sizeof (struct vn_reference_s
),
4019 /* Free a value number table. */
4022 free_vn_table (vn_tables_t table
)
4028 delete table
->references
;
4029 table
->references
= NULL
;
4030 obstack_free (&table
->nary_obstack
, NULL
);
4031 free_alloc_pool (table
->phis_pool
);
4032 free_alloc_pool (table
->references_pool
);
4040 int *rpo_numbers_temp
;
4042 calculate_dominance_info (CDI_DOMINATORS
);
4043 sccstack
.create (0);
4044 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
4046 constant_value_ids
= BITMAP_ALLOC (NULL
);
4051 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
4052 /* VEC_alloc doesn't actually grow it to the right size, it just
4053 preallocates the space to do so. */
4054 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
4055 gcc_obstack_init (&vn_ssa_aux_obstack
);
4057 shared_lookup_phiargs
.create (0);
4058 shared_lookup_references
.create (0);
4059 rpo_numbers
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
4061 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
4062 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
4064 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4065 the i'th block in RPO order is bb. We want to map bb's to RPO
4066 numbers, so we need to rearrange this array. */
4067 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
4068 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
4070 XDELETE (rpo_numbers_temp
);
4072 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
4074 /* Create the VN_INFO structures, and initialize value numbers to
4076 for (i
= 0; i
< num_ssa_names
; i
++)
4078 tree name
= ssa_name (i
);
4081 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4082 VN_INFO (name
)->expr
= NULL_TREE
;
4083 VN_INFO (name
)->value_id
= 0;
4087 renumber_gimple_stmt_uids ();
4089 /* Create the valid and optimistic value numbering tables. */
4090 valid_info
= XCNEW (struct vn_tables_s
);
4091 allocate_vn_table (valid_info
);
4092 optimistic_info
= XCNEW (struct vn_tables_s
);
4093 allocate_vn_table (optimistic_info
);
4101 delete constant_to_value_id
;
4102 constant_to_value_id
= NULL
;
4103 BITMAP_FREE (constant_value_ids
);
4104 shared_lookup_phiargs
.release ();
4105 shared_lookup_references
.release ();
4106 XDELETEVEC (rpo_numbers
);
4108 for (i
= 0; i
< num_ssa_names
; i
++)
4110 tree name
= ssa_name (i
);
4112 && VN_INFO (name
)->needs_insertion
)
4113 release_ssa_name (name
);
4115 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4116 vn_ssa_aux_table
.release ();
4118 sccstack
.release ();
4119 free_vn_table (valid_info
);
4120 XDELETE (valid_info
);
4121 free_vn_table (optimistic_info
);
4122 XDELETE (optimistic_info
);
4125 /* Set *ID according to RESULT. */
4128 set_value_id_for_result (tree result
, unsigned int *id
)
4130 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4131 *id
= VN_INFO (result
)->value_id
;
4132 else if (result
&& is_gimple_min_invariant (result
))
4133 *id
= get_or_alloc_constant_value_id (result
);
4135 *id
= get_next_value_id ();
4138 /* Set the value ids in the valid hash tables. */
4141 set_hashtable_value_ids (void)
4143 vn_nary_op_iterator_type hin
;
4144 vn_phi_iterator_type hip
;
4145 vn_reference_iterator_type hir
;
4150 /* Now set the value ids of the things we had put in the hash
4153 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4154 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4156 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4157 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4159 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4161 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4164 class cond_dom_walker
: public dom_walker
4167 cond_dom_walker () : dom_walker (CDI_DOMINATORS
), fail (false) {}
4169 virtual void before_dom_children (basic_block
);
4175 cond_dom_walker::before_dom_children (basic_block bb
)
4183 /* If any of the predecessor edges that do not come from blocks dominated
4184 by us are still marked as possibly executable consider this block
4186 bool reachable
= bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
);
4187 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4188 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
4189 reachable
|= (e
->flags
& EDGE_EXECUTABLE
);
4191 /* If the block is not reachable all outgoing edges are not
4195 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4196 fprintf (dump_file
, "Marking all outgoing edges of unreachable "
4197 "BB %d as not executable\n", bb
->index
);
4199 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4200 e
->flags
&= ~EDGE_EXECUTABLE
;
4204 gimple stmt
= last_stmt (bb
);
4208 enum gimple_code code
= gimple_code (stmt
);
4209 if (code
!= GIMPLE_COND
4210 && code
!= GIMPLE_SWITCH
4211 && code
!= GIMPLE_GOTO
)
4214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4216 fprintf (dump_file
, "Value-numbering operands of stmt ending BB %d: ",
4218 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4221 /* Value-number the last stmts SSA uses. */
4224 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
4225 if (VN_INFO (op
)->visited
== false
4232 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4233 if value-numbering can prove they are not reachable. Handling
4234 computed gotos is also possible. */
4240 tree lhs
= gimple_cond_lhs (stmt
);
4241 tree rhs
= gimple_cond_rhs (stmt
);
4242 /* Work hard in computing the condition and take into account
4243 the valueization of the defining stmt. */
4244 if (TREE_CODE (lhs
) == SSA_NAME
)
4245 lhs
= vn_get_expr_for (lhs
);
4246 if (TREE_CODE (rhs
) == SSA_NAME
)
4247 rhs
= vn_get_expr_for (rhs
);
4248 val
= fold_binary (gimple_cond_code (stmt
),
4249 boolean_type_node
, lhs
, rhs
);
4253 val
= gimple_switch_index (stmt
);
4256 val
= gimple_goto_dest (stmt
);
4264 edge taken
= find_taken_edge (bb
, vn_valueize (val
));
4268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4269 fprintf (dump_file
, "Marking all edges out of BB %d but (%d -> %d) as "
4270 "not executable\n", bb
->index
, bb
->index
, taken
->dest
->index
);
4272 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4274 e
->flags
&= ~EDGE_EXECUTABLE
;
4277 /* Do SCCVN. Returns true if it finished, false if we bailed out
4278 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4279 how we use the alias oracle walking during the VN process. */
4282 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4288 default_vn_walk_kind
= default_vn_walk_kind_
;
4291 current_info
= valid_info
;
4293 for (param
= DECL_ARGUMENTS (current_function_decl
);
4295 param
= DECL_CHAIN (param
))
4297 tree def
= ssa_default_def (cfun
, param
);
4300 VN_INFO (def
)->visited
= true;
4301 VN_INFO (def
)->valnum
= def
;
4305 /* Mark all edges as possibly executable. */
4306 FOR_ALL_BB_FN (bb
, cfun
)
4310 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4311 e
->flags
|= EDGE_EXECUTABLE
;
4314 /* Walk all blocks in dominator order, value-numbering the last stmts
4315 SSA uses and decide whether outgoing edges are not executable. */
4316 cond_dom_walker walker
;
4317 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4324 /* Value-number remaining SSA names. */
4325 for (i
= 1; i
< num_ssa_names
; ++i
)
4327 tree name
= ssa_name (i
);
4329 && VN_INFO (name
)->visited
== false
4330 && !has_zero_uses (name
))
4338 /* Initialize the value ids. */
4340 for (i
= 1; i
< num_ssa_names
; ++i
)
4342 tree name
= ssa_name (i
);
4346 info
= VN_INFO (name
);
4347 if (info
->valnum
== name
4348 || info
->valnum
== VN_TOP
)
4349 info
->value_id
= get_next_value_id ();
4350 else if (is_gimple_min_invariant (info
->valnum
))
4351 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4355 for (i
= 1; i
< num_ssa_names
; ++i
)
4357 tree name
= ssa_name (i
);
4361 info
= VN_INFO (name
);
4362 if (TREE_CODE (info
->valnum
) == SSA_NAME
4363 && info
->valnum
!= name
4364 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4365 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4368 set_hashtable_value_ids ();
4370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4372 fprintf (dump_file
, "Value numbers:\n");
4373 for (i
= 0; i
< num_ssa_names
; i
++)
4375 tree name
= ssa_name (i
);
4377 && VN_INFO (name
)->visited
4378 && SSA_VAL (name
) != name
)
4380 print_generic_expr (dump_file
, name
, 0);
4381 fprintf (dump_file
, " = ");
4382 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4383 fprintf (dump_file
, "\n");
4391 /* Return the maximum value id we have ever seen. */
4394 get_max_value_id (void)
4396 return next_value_id
;
4399 /* Return the next unique value id. */
4402 get_next_value_id (void)
4404 return next_value_id
++;
4408 /* Compare two expressions E1 and E2 and return true if they are equal. */
4411 expressions_equal_p (tree e1
, tree e2
)
4413 /* The obvious case. */
4417 /* If only one of them is null, they cannot be equal. */
4421 /* Now perform the actual comparison. */
4422 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4423 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4430 /* Return true if the nary operation NARY may trap. This is a copy
4431 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4434 vn_nary_may_trap (vn_nary_op_t nary
)
4437 tree rhs2
= NULL_TREE
;
4438 bool honor_nans
= false;
4439 bool honor_snans
= false;
4440 bool fp_operation
= false;
4441 bool honor_trapv
= false;
4445 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4446 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4447 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4450 fp_operation
= FLOAT_TYPE_P (type
);
4453 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4454 honor_snans
= flag_signaling_nans
!= 0;
4456 else if (INTEGRAL_TYPE_P (type
)
4457 && TYPE_OVERFLOW_TRAPS (type
))
4460 if (nary
->length
>= 2)
4462 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4464 honor_nans
, honor_snans
, rhs2
,
4470 for (i
= 0; i
< nary
->length
; ++i
)
4471 if (tree_could_trap_p (nary
->op
[i
]))