1 /* SCC value numbering for trees
2 Copyright (C) 2006-2017 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"
28 #include "alloc-pool.h"
31 #include "insn-config.h"
35 #include "gimple-pretty-print.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
40 #include "tree-inline.h"
41 #include "internal-fn.h"
42 #include "gimple-fold.h"
57 #include "tree-ssa-propagate.h"
58 #include "tree-ssa-sccvn.h"
61 #include "gimple-iterator.h"
62 #include "gimple-match.h"
64 /* This algorithm is based on the SCC algorithm presented by Keith
65 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
66 (http://citeseer.ist.psu.edu/41805.html). In
67 straight line code, it is equivalent to a regular hash based value
68 numbering that is performed in reverse postorder.
70 For code with cycles, there are two alternatives, both of which
71 require keeping the hashtables separate from the actual list of
72 value numbers for SSA names.
74 1. Iterate value numbering in an RPO walk of the blocks, removing
75 all the entries from the hashtable after each iteration (but
76 keeping the SSA name->value number mapping between iterations).
77 Iterate until it does not change.
79 2. Perform value numbering as part of an SCC walk on the SSA graph,
80 iterating only the cycles in the SSA graph until they do not change
81 (using a separate, optimistic hashtable for value numbering the SCC
84 The second is not just faster in practice (because most SSA graph
85 cycles do not involve all the variables in the graph), it also has
88 One of these nice properties is that when we pop an SCC off the
89 stack, we are guaranteed to have processed all the operands coming from
90 *outside of that SCC*, so we do not need to do anything special to
91 ensure they have value numbers.
93 Another nice property is that the SCC walk is done as part of a DFS
94 of the SSA graph, which makes it easy to perform combining and
95 simplifying operations at the same time.
97 The code below is deliberately written in a way that makes it easy
98 to separate the SCC walk from the other work it does.
100 In order to propagate constants through the code, we track which
101 expressions contain constants, and use those while folding. In
102 theory, we could also track expressions whose value numbers are
103 replaced, in case we end up folding based on expression
106 In order to value number memory, we assign value numbers to vuses.
107 This enables us to note that, for example, stores to the same
108 address of the same value from the same starting memory states are
112 1. We can iterate only the changing portions of the SCC's, but
113 I have not seen an SCC big enough for this to be a win.
114 2. If you differentiate between phi nodes for loops and phi nodes
115 for if-then-else, you can properly consider phi nodes in different
116 blocks for equivalence.
117 3. We could value number vuses in more cases, particularly, whole
122 static tree
*last_vuse_ptr
;
123 static vn_lookup_kind vn_walk_kind
;
124 static vn_lookup_kind default_vn_walk_kind
;
127 /* vn_nary_op hashtable helpers. */
129 struct vn_nary_op_hasher
: nofree_ptr_hash
<vn_nary_op_s
>
131 typedef vn_nary_op_s
*compare_type
;
132 static inline hashval_t
hash (const vn_nary_op_s
*);
133 static inline bool equal (const vn_nary_op_s
*, const vn_nary_op_s
*);
136 /* Return the computed hashcode for nary operation P1. */
139 vn_nary_op_hasher::hash (const vn_nary_op_s
*vno1
)
141 return vno1
->hashcode
;
144 /* Compare nary operations P1 and P2 and return true if they are
148 vn_nary_op_hasher::equal (const vn_nary_op_s
*vno1
, const vn_nary_op_s
*vno2
)
150 return vn_nary_op_eq (vno1
, vno2
);
153 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
154 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
157 /* vn_phi hashtable helpers. */
160 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
162 struct vn_phi_hasher
: pointer_hash
<vn_phi_s
>
164 static inline hashval_t
hash (const vn_phi_s
*);
165 static inline bool equal (const vn_phi_s
*, const vn_phi_s
*);
166 static inline void remove (vn_phi_s
*);
169 /* Return the computed hashcode for phi operation P1. */
172 vn_phi_hasher::hash (const vn_phi_s
*vp1
)
174 return vp1
->hashcode
;
177 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
180 vn_phi_hasher::equal (const vn_phi_s
*vp1
, const vn_phi_s
*vp2
)
182 return vn_phi_eq (vp1
, vp2
);
185 /* Free a phi operation structure VP. */
188 vn_phi_hasher::remove (vn_phi_s
*phi
)
190 phi
->phiargs
.release ();
193 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
194 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
197 /* Compare two reference operands P1 and P2 for equality. Return true if
198 they are equal, and false otherwise. */
201 vn_reference_op_eq (const void *p1
, const void *p2
)
203 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
204 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
206 return (vro1
->opcode
== vro2
->opcode
207 /* We do not care for differences in type qualification. */
208 && (vro1
->type
== vro2
->type
209 || (vro1
->type
&& vro2
->type
210 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
211 TYPE_MAIN_VARIANT (vro2
->type
))))
212 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
213 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
214 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
217 /* Free a reference operation structure VP. */
220 free_reference (vn_reference_s
*vr
)
222 vr
->operands
.release ();
226 /* vn_reference hashtable helpers. */
228 struct vn_reference_hasher
: pointer_hash
<vn_reference_s
>
230 static inline hashval_t
hash (const vn_reference_s
*);
231 static inline bool equal (const vn_reference_s
*, const vn_reference_s
*);
232 static inline void remove (vn_reference_s
*);
235 /* Return the hashcode for a given reference operation P1. */
238 vn_reference_hasher::hash (const vn_reference_s
*vr1
)
240 return vr1
->hashcode
;
244 vn_reference_hasher::equal (const vn_reference_s
*v
, const vn_reference_s
*c
)
246 return vn_reference_eq (v
, c
);
250 vn_reference_hasher::remove (vn_reference_s
*v
)
255 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
256 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
259 /* The set of hashtables and alloc_pool's for their items. */
261 typedef struct vn_tables_s
263 vn_nary_op_table_type
*nary
;
264 vn_phi_table_type
*phis
;
265 vn_reference_table_type
*references
;
266 struct obstack nary_obstack
;
267 object_allocator
<vn_phi_s
> *phis_pool
;
268 object_allocator
<vn_reference_s
> *references_pool
;
272 /* vn_constant hashtable helpers. */
274 struct vn_constant_hasher
: free_ptr_hash
<vn_constant_s
>
276 static inline hashval_t
hash (const vn_constant_s
*);
277 static inline bool equal (const vn_constant_s
*, const vn_constant_s
*);
280 /* Hash table hash function for vn_constant_t. */
283 vn_constant_hasher::hash (const vn_constant_s
*vc1
)
285 return vc1
->hashcode
;
288 /* Hash table equality function for vn_constant_t. */
291 vn_constant_hasher::equal (const vn_constant_s
*vc1
, const vn_constant_s
*vc2
)
293 if (vc1
->hashcode
!= vc2
->hashcode
)
296 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
299 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
300 static bitmap constant_value_ids
;
303 /* Valid hashtables storing information we have proven to be
306 static vn_tables_t valid_info
;
308 /* Optimistic hashtables storing information we are making assumptions about
309 during iterations. */
311 static vn_tables_t optimistic_info
;
313 /* Pointer to the set of hashtables that is currently being used.
314 Should always point to either the optimistic_info, or the
317 static vn_tables_t current_info
;
320 /* Reverse post order index for each basic block. */
322 static int *rpo_numbers
;
324 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
326 /* Return the SSA value of the VUSE x, supporting released VDEFs
327 during elimination which will value-number the VDEF to the
328 associated VUSE (but not substitute in the whole lattice). */
331 vuse_ssa_val (tree x
)
340 while (SSA_NAME_IN_FREE_LIST (x
));
345 /* This represents the top of the VN lattice, which is the universal
350 /* Unique counter for our value ids. */
352 static unsigned int next_value_id
;
354 /* Next DFS number and the stack for strongly connected component
357 static unsigned int next_dfs_num
;
358 static vec
<tree
> sccstack
;
362 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
363 are allocated on an obstack for locality reasons, and to free them
364 without looping over the vec. */
366 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
367 static struct obstack vn_ssa_aux_obstack
;
369 /* Return whether there is value numbering information for a given SSA name. */
372 has_VN_INFO (tree name
)
374 if (SSA_NAME_VERSION (name
) < vn_ssa_aux_table
.length ())
375 return vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] != NULL
;
379 /* Return the value numbering information for a given SSA name. */
384 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
385 gcc_checking_assert (res
);
389 /* Set the value numbering info for a given SSA name to a given
393 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
395 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
398 /* Initialize the value numbering info for a given SSA name.
399 This should be called just once for every SSA name. */
402 VN_INFO_GET (tree name
)
404 vn_ssa_aux_t newinfo
;
406 gcc_assert (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ()
407 || vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] == NULL
);
408 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
409 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
410 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
411 vn_ssa_aux_table
.safe_grow_cleared (SSA_NAME_VERSION (name
) + 1);
412 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
417 /* Return the vn_kind the expression computed by the stmt should be
421 vn_get_stmt_kind (gimple
*stmt
)
423 switch (gimple_code (stmt
))
431 enum tree_code code
= gimple_assign_rhs_code (stmt
);
432 tree rhs1
= gimple_assign_rhs1 (stmt
);
433 switch (get_gimple_rhs_class (code
))
435 case GIMPLE_UNARY_RHS
:
436 case GIMPLE_BINARY_RHS
:
437 case GIMPLE_TERNARY_RHS
:
439 case GIMPLE_SINGLE_RHS
:
440 switch (TREE_CODE_CLASS (code
))
443 /* VOP-less references can go through unary case. */
444 if ((code
== REALPART_EXPR
445 || code
== IMAGPART_EXPR
446 || code
== VIEW_CONVERT_EXPR
447 || code
== BIT_FIELD_REF
)
448 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
452 case tcc_declaration
:
459 if (code
== ADDR_EXPR
)
460 return (is_gimple_min_invariant (rhs1
)
461 ? VN_CONSTANT
: VN_REFERENCE
);
462 else if (code
== CONSTRUCTOR
)
475 /* Lookup a value id for CONSTANT and return it. If it does not
479 get_constant_value_id (tree constant
)
481 vn_constant_s
**slot
;
482 struct vn_constant_s vc
;
484 vc
.hashcode
= vn_hash_constant_with_type (constant
);
485 vc
.constant
= constant
;
486 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
488 return (*slot
)->value_id
;
492 /* Lookup a value id for CONSTANT, and if it does not exist, create a
493 new one and return it. If it does exist, return it. */
496 get_or_alloc_constant_value_id (tree constant
)
498 vn_constant_s
**slot
;
499 struct vn_constant_s vc
;
502 vc
.hashcode
= vn_hash_constant_with_type (constant
);
503 vc
.constant
= constant
;
504 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
506 return (*slot
)->value_id
;
508 vcp
= XNEW (struct vn_constant_s
);
509 vcp
->hashcode
= vc
.hashcode
;
510 vcp
->constant
= constant
;
511 vcp
->value_id
= get_next_value_id ();
513 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
514 return vcp
->value_id
;
517 /* Return true if V is a value id for a constant. */
520 value_id_constant_p (unsigned int v
)
522 return bitmap_bit_p (constant_value_ids
, v
);
525 /* Compute the hash for a reference operand VRO1. */
528 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
530 hstate
.add_int (vro1
->opcode
);
532 inchash::add_expr (vro1
->op0
, hstate
);
534 inchash::add_expr (vro1
->op1
, hstate
);
536 inchash::add_expr (vro1
->op2
, hstate
);
539 /* Compute a hash for the reference operation VR1 and return it. */
542 vn_reference_compute_hash (const vn_reference_t vr1
)
544 inchash::hash hstate
;
547 vn_reference_op_t vro
;
548 HOST_WIDE_INT off
= -1;
551 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
553 if (vro
->opcode
== MEM_REF
)
555 else if (vro
->opcode
!= ADDR_EXPR
)
567 hstate
.add_int (off
);
570 && vro
->opcode
== ADDR_EXPR
)
574 tree op
= TREE_OPERAND (vro
->op0
, 0);
575 hstate
.add_int (TREE_CODE (op
));
576 inchash::add_expr (op
, hstate
);
580 vn_reference_op_compute_hash (vro
, hstate
);
583 result
= hstate
.end ();
584 /* ??? We would ICE later if we hash instead of adding that in. */
586 result
+= SSA_NAME_VERSION (vr1
->vuse
);
591 /* Return true if reference operations VR1 and VR2 are equivalent. This
592 means they have the same set of operands and vuses. */
595 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
599 /* Early out if this is not a hash collision. */
600 if (vr1
->hashcode
!= vr2
->hashcode
)
603 /* The VOP needs to be the same. */
604 if (vr1
->vuse
!= vr2
->vuse
)
607 /* If the operands are the same we are done. */
608 if (vr1
->operands
== vr2
->operands
)
611 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
614 if (INTEGRAL_TYPE_P (vr1
->type
)
615 && INTEGRAL_TYPE_P (vr2
->type
))
617 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
620 else if (INTEGRAL_TYPE_P (vr1
->type
)
621 && (TYPE_PRECISION (vr1
->type
)
622 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
624 else if (INTEGRAL_TYPE_P (vr2
->type
)
625 && (TYPE_PRECISION (vr2
->type
)
626 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
633 HOST_WIDE_INT off1
= 0, off2
= 0;
634 vn_reference_op_t vro1
, vro2
;
635 vn_reference_op_s tem1
, tem2
;
636 bool deref1
= false, deref2
= false;
637 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
639 if (vro1
->opcode
== MEM_REF
)
641 /* Do not look through a storage order barrier. */
642 else if (vro1
->opcode
== VIEW_CONVERT_EXPR
&& vro1
->reverse
)
648 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
650 if (vro2
->opcode
== MEM_REF
)
652 /* Do not look through a storage order barrier. */
653 else if (vro2
->opcode
== VIEW_CONVERT_EXPR
&& vro2
->reverse
)
661 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
663 memset (&tem1
, 0, sizeof (tem1
));
664 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
665 tem1
.type
= TREE_TYPE (tem1
.op0
);
666 tem1
.opcode
= TREE_CODE (tem1
.op0
);
670 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
672 memset (&tem2
, 0, sizeof (tem2
));
673 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
674 tem2
.type
= TREE_TYPE (tem2
.op0
);
675 tem2
.opcode
= TREE_CODE (tem2
.op0
);
679 if (deref1
!= deref2
)
681 if (!vn_reference_op_eq (vro1
, vro2
))
686 while (vr1
->operands
.length () != i
687 || vr2
->operands
.length () != j
);
692 /* Copy the operations present in load/store REF into RESULT, a vector of
693 vn_reference_op_s's. */
696 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
698 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
700 vn_reference_op_s temp
;
704 memset (&temp
, 0, sizeof (temp
));
705 temp
.type
= TREE_TYPE (ref
);
706 temp
.opcode
= TREE_CODE (ref
);
707 temp
.op0
= TMR_INDEX (ref
);
708 temp
.op1
= TMR_STEP (ref
);
709 temp
.op2
= TMR_OFFSET (ref
);
711 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
712 temp
.base
= MR_DEPENDENCE_BASE (ref
);
713 result
->quick_push (temp
);
715 memset (&temp
, 0, sizeof (temp
));
716 temp
.type
= NULL_TREE
;
717 temp
.opcode
= ERROR_MARK
;
718 temp
.op0
= TMR_INDEX2 (ref
);
720 result
->quick_push (temp
);
722 memset (&temp
, 0, sizeof (temp
));
723 temp
.type
= NULL_TREE
;
724 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
725 temp
.op0
= TMR_BASE (ref
);
727 result
->quick_push (temp
);
731 /* For non-calls, store the information that makes up the address. */
735 vn_reference_op_s temp
;
737 memset (&temp
, 0, sizeof (temp
));
738 temp
.type
= TREE_TYPE (ref
);
739 temp
.opcode
= TREE_CODE (ref
);
745 temp
.op0
= TREE_OPERAND (ref
, 1);
748 temp
.op0
= TREE_OPERAND (ref
, 1);
752 /* The base address gets its own vn_reference_op_s structure. */
753 temp
.op0
= TREE_OPERAND (ref
, 1);
755 offset_int off
= mem_ref_offset (ref
);
756 if (wi::fits_shwi_p (off
))
757 temp
.off
= off
.to_shwi ();
759 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
760 temp
.base
= MR_DEPENDENCE_BASE (ref
);
761 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
764 /* Record bits, position and storage order. */
765 temp
.op0
= TREE_OPERAND (ref
, 1);
766 temp
.op1
= TREE_OPERAND (ref
, 2);
767 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 2)))
769 HOST_WIDE_INT off
= tree_to_shwi (TREE_OPERAND (ref
, 2));
770 if (off
% BITS_PER_UNIT
== 0)
771 temp
.off
= off
/ BITS_PER_UNIT
;
773 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
776 /* The field decl is enough to unambiguously specify the field,
777 a matching type is not necessary and a mismatching type
778 is always a spurious difference. */
779 temp
.type
= NULL_TREE
;
780 temp
.op0
= TREE_OPERAND (ref
, 1);
781 temp
.op1
= TREE_OPERAND (ref
, 2);
783 tree this_offset
= component_ref_field_offset (ref
);
785 && TREE_CODE (this_offset
) == INTEGER_CST
)
787 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
788 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
791 = (wi::to_offset (this_offset
)
792 + (wi::to_offset (bit_offset
) >> LOG2_BITS_PER_UNIT
));
793 if (wi::fits_shwi_p (off
)
794 /* Probibit value-numbering zero offset components
795 of addresses the same before the pass folding
796 __builtin_object_size had a chance to run
797 (checking cfun->after_inlining does the
799 && (TREE_CODE (orig
) != ADDR_EXPR
801 || cfun
->after_inlining
))
802 temp
.off
= off
.to_shwi ();
807 case ARRAY_RANGE_REF
:
810 tree eltype
= TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref
, 0)));
811 /* Record index as operand. */
812 temp
.op0
= TREE_OPERAND (ref
, 1);
813 /* Always record lower bounds and element size. */
814 temp
.op1
= array_ref_low_bound (ref
);
815 /* But record element size in units of the type alignment. */
816 temp
.op2
= TREE_OPERAND (ref
, 3);
817 temp
.align
= eltype
->type_common
.align
;
819 temp
.op2
= size_binop (EXACT_DIV_EXPR
, TYPE_SIZE_UNIT (eltype
),
820 size_int (TYPE_ALIGN_UNIT (eltype
)));
821 if (TREE_CODE (temp
.op0
) == INTEGER_CST
822 && TREE_CODE (temp
.op1
) == INTEGER_CST
823 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
825 offset_int off
= ((wi::to_offset (temp
.op0
)
826 - wi::to_offset (temp
.op1
))
827 * wi::to_offset (temp
.op2
)
828 * vn_ref_op_align_unit (&temp
));
829 if (wi::fits_shwi_p (off
))
830 temp
.off
= off
.to_shwi();
835 if (DECL_HARD_REGISTER (ref
))
844 /* Canonicalize decls to MEM[&decl] which is what we end up with
845 when valueizing MEM[ptr] with ptr = &decl. */
846 temp
.opcode
= MEM_REF
;
847 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
849 result
->safe_push (temp
);
850 temp
.opcode
= ADDR_EXPR
;
851 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
852 temp
.type
= TREE_TYPE (temp
.op0
);
866 if (is_gimple_min_invariant (ref
))
872 /* These are only interesting for their operands, their
873 existence, and their type. They will never be the last
874 ref in the chain of references (IE they require an
875 operand), so we don't have to put anything
876 for op* as it will be handled by the iteration */
880 case VIEW_CONVERT_EXPR
:
882 temp
.reverse
= storage_order_barrier_p (ref
);
885 /* This is only interesting for its constant offset. */
886 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
891 result
->safe_push (temp
);
893 if (REFERENCE_CLASS_P (ref
)
894 || TREE_CODE (ref
) == MODIFY_EXPR
895 || TREE_CODE (ref
) == WITH_SIZE_EXPR
896 || (TREE_CODE (ref
) == ADDR_EXPR
897 && !is_gimple_min_invariant (ref
)))
898 ref
= TREE_OPERAND (ref
, 0);
904 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
905 operands in *OPS, the reference alias set SET and the reference type TYPE.
906 Return true if something useful was produced. */
909 ao_ref_init_from_vn_reference (ao_ref
*ref
,
910 alias_set_type set
, tree type
,
911 vec
<vn_reference_op_s
> ops
)
913 vn_reference_op_t op
;
915 tree base
= NULL_TREE
;
917 offset_int offset
= 0;
919 offset_int size
= -1;
920 tree size_tree
= NULL_TREE
;
921 alias_set_type base_alias_set
= -1;
923 /* First get the final access size from just the outermost expression. */
925 if (op
->opcode
== COMPONENT_REF
)
926 size_tree
= DECL_SIZE (op
->op0
);
927 else if (op
->opcode
== BIT_FIELD_REF
)
931 machine_mode mode
= TYPE_MODE (type
);
933 size_tree
= TYPE_SIZE (type
);
935 size
= int (GET_MODE_BITSIZE (mode
));
937 if (size_tree
!= NULL_TREE
938 && TREE_CODE (size_tree
) == INTEGER_CST
)
939 size
= wi::to_offset (size_tree
);
941 /* Initially, maxsize is the same as the accessed element size.
942 In the following it will only grow (or become -1). */
945 /* Compute cumulative bit-offset for nested component-refs and array-refs,
946 and find the ultimate containing object. */
947 FOR_EACH_VEC_ELT (ops
, i
, op
)
951 /* These may be in the reference ops, but we cannot do anything
952 sensible with them here. */
954 /* Apart from ADDR_EXPR arguments to MEM_REF. */
955 if (base
!= NULL_TREE
956 && TREE_CODE (base
) == MEM_REF
958 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
960 vn_reference_op_t pop
= &ops
[i
-1];
961 base
= TREE_OPERAND (op
->op0
, 0);
968 offset
+= pop
->off
* BITS_PER_UNIT
;
976 /* Record the base objects. */
978 base_alias_set
= get_deref_alias_set (op
->op0
);
979 *op0_p
= build2 (MEM_REF
, op
->type
,
981 MR_DEPENDENCE_CLIQUE (*op0_p
) = op
->clique
;
982 MR_DEPENDENCE_BASE (*op0_p
) = op
->base
;
983 op0_p
= &TREE_OPERAND (*op0_p
, 0);
994 /* And now the usual component-reference style ops. */
996 offset
+= wi::to_offset (op
->op1
);
1001 tree field
= op
->op0
;
1002 /* We do not have a complete COMPONENT_REF tree here so we
1003 cannot use component_ref_field_offset. Do the interesting
1005 tree this_offset
= DECL_FIELD_OFFSET (field
);
1007 if (op
->op1
|| TREE_CODE (this_offset
) != INTEGER_CST
)
1011 offset_int woffset
= (wi::to_offset (this_offset
)
1012 << LOG2_BITS_PER_UNIT
);
1013 woffset
+= wi::to_offset (DECL_FIELD_BIT_OFFSET (field
));
1019 case ARRAY_RANGE_REF
:
1021 /* We recorded the lower bound and the element size. */
1022 if (TREE_CODE (op
->op0
) != INTEGER_CST
1023 || TREE_CODE (op
->op1
) != INTEGER_CST
1024 || TREE_CODE (op
->op2
) != INTEGER_CST
)
1029 = wi::sext (wi::to_offset (op
->op0
) - wi::to_offset (op
->op1
),
1030 TYPE_PRECISION (TREE_TYPE (op
->op0
)));
1031 woffset
*= wi::to_offset (op
->op2
) * vn_ref_op_align_unit (op
);
1032 woffset
<<= LOG2_BITS_PER_UNIT
;
1044 case VIEW_CONVERT_EXPR
:
1061 if (base
== NULL_TREE
)
1064 ref
->ref
= NULL_TREE
;
1066 ref
->ref_alias_set
= set
;
1067 if (base_alias_set
!= -1)
1068 ref
->base_alias_set
= base_alias_set
;
1070 ref
->base_alias_set
= get_alias_set (base
);
1071 /* We discount volatiles from value-numbering elsewhere. */
1072 ref
->volatile_p
= false;
1074 if (!wi::fits_shwi_p (size
) || wi::neg_p (size
))
1082 ref
->size
= size
.to_shwi ();
1084 if (!wi::fits_shwi_p (offset
))
1091 ref
->offset
= offset
.to_shwi ();
1093 if (!wi::fits_shwi_p (max_size
) || wi::neg_p (max_size
))
1096 ref
->max_size
= max_size
.to_shwi ();
1101 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1102 vn_reference_op_s's. */
1105 copy_reference_ops_from_call (gcall
*call
,
1106 vec
<vn_reference_op_s
> *result
)
1108 vn_reference_op_s temp
;
1110 tree lhs
= gimple_call_lhs (call
);
1113 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1114 different. By adding the lhs here in the vector, we ensure that the
1115 hashcode is different, guaranteeing a different value number. */
1116 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1118 memset (&temp
, 0, sizeof (temp
));
1119 temp
.opcode
= MODIFY_EXPR
;
1120 temp
.type
= TREE_TYPE (lhs
);
1123 result
->safe_push (temp
);
1126 /* Copy the type, opcode, function, static chain and EH region, if any. */
1127 memset (&temp
, 0, sizeof (temp
));
1128 temp
.type
= gimple_call_return_type (call
);
1129 temp
.opcode
= CALL_EXPR
;
1130 temp
.op0
= gimple_call_fn (call
);
1131 temp
.op1
= gimple_call_chain (call
);
1132 if (stmt_could_throw_p (call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1133 temp
.op2
= size_int (lr
);
1135 if (gimple_call_with_bounds_p (call
))
1136 temp
.with_bounds
= 1;
1137 result
->safe_push (temp
);
1139 /* Copy the call arguments. As they can be references as well,
1140 just chain them together. */
1141 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1143 tree callarg
= gimple_call_arg (call
, i
);
1144 copy_reference_ops_from_ref (callarg
, result
);
1148 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1149 *I_P to point to the last element of the replacement. */
1151 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1154 unsigned int i
= *i_p
;
1155 vn_reference_op_t op
= &(*ops
)[i
];
1156 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1158 HOST_WIDE_INT addr_offset
= 0;
1160 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1161 from .foo.bar to the preceding MEM_REF offset and replace the
1162 address with &OBJ. */
1163 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1165 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1166 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1168 offset_int off
= offset_int::from (mem_op
->op0
, SIGNED
);
1170 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1171 op
->op0
= build_fold_addr_expr (addr_base
);
1172 if (tree_fits_shwi_p (mem_op
->op0
))
1173 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1181 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1182 *I_P to point to the last element of the replacement. */
1184 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1187 unsigned int i
= *i_p
;
1188 vn_reference_op_t op
= &(*ops
)[i
];
1189 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1191 enum tree_code code
;
1194 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1195 if (!is_gimple_assign (def_stmt
))
1198 code
= gimple_assign_rhs_code (def_stmt
);
1199 if (code
!= ADDR_EXPR
1200 && code
!= POINTER_PLUS_EXPR
)
1203 off
= offset_int::from (mem_op
->op0
, SIGNED
);
1205 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1206 from .foo.bar to the preceding MEM_REF offset and replace the
1207 address with &OBJ. */
1208 if (code
== ADDR_EXPR
)
1210 tree addr
, addr_base
;
1211 HOST_WIDE_INT addr_offset
;
1213 addr
= gimple_assign_rhs1 (def_stmt
);
1214 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1216 /* If that didn't work because the address isn't invariant propagate
1217 the reference tree from the address operation in case the current
1218 dereference isn't offsetted. */
1220 && *i_p
== ops
->length () - 1
1222 /* This makes us disable this transform for PRE where the
1223 reference ops might be also used for code insertion which
1225 && default_vn_walk_kind
== VN_WALKREWRITE
)
1227 auto_vec
<vn_reference_op_s
, 32> tem
;
1228 copy_reference_ops_from_ref (TREE_OPERAND (addr
, 0), &tem
);
1229 /* Make sure to preserve TBAA info. The only objects not
1230 wrapped in MEM_REFs that can have their address taken are
1232 if (tem
.length () >= 2
1233 && tem
[tem
.length () - 2].opcode
== MEM_REF
)
1235 vn_reference_op_t new_mem_op
= &tem
[tem
.length () - 2];
1236 new_mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
),
1240 gcc_assert (tem
.last ().opcode
== STRING_CST
);
1243 ops
->safe_splice (tem
);
1248 || TREE_CODE (addr_base
) != MEM_REF
)
1252 off
+= mem_ref_offset (addr_base
);
1253 op
->op0
= TREE_OPERAND (addr_base
, 0);
1258 ptr
= gimple_assign_rhs1 (def_stmt
);
1259 ptroff
= gimple_assign_rhs2 (def_stmt
);
1260 if (TREE_CODE (ptr
) != SSA_NAME
1261 || TREE_CODE (ptroff
) != INTEGER_CST
)
1264 off
+= wi::to_offset (ptroff
);
1268 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1269 if (tree_fits_shwi_p (mem_op
->op0
))
1270 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1273 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1274 op
->op0
= SSA_VAL (op
->op0
);
1275 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1276 op
->opcode
= TREE_CODE (op
->op0
);
1279 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1280 vn_reference_maybe_forwprop_address (ops
, i_p
);
1281 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1282 vn_reference_fold_indirect (ops
, i_p
);
1286 /* Optimize the reference REF to a constant if possible or return
1287 NULL_TREE if not. */
1290 fully_constant_vn_reference_p (vn_reference_t ref
)
1292 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1293 vn_reference_op_t op
;
1295 /* Try to simplify the translated expression if it is
1296 a call to a builtin function with at most two arguments. */
1298 if (op
->opcode
== CALL_EXPR
1299 && TREE_CODE (op
->op0
) == ADDR_EXPR
1300 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1301 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1302 && operands
.length () >= 2
1303 && operands
.length () <= 3)
1305 vn_reference_op_t arg0
, arg1
= NULL
;
1306 bool anyconst
= false;
1307 arg0
= &operands
[1];
1308 if (operands
.length () > 2)
1309 arg1
= &operands
[2];
1310 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1311 || (arg0
->opcode
== ADDR_EXPR
1312 && is_gimple_min_invariant (arg0
->op0
)))
1315 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1316 || (arg1
->opcode
== ADDR_EXPR
1317 && is_gimple_min_invariant (arg1
->op0
))))
1321 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1324 arg1
? arg1
->op0
: NULL
);
1326 && TREE_CODE (folded
) == NOP_EXPR
)
1327 folded
= TREE_OPERAND (folded
, 0);
1329 && is_gimple_min_invariant (folded
))
1334 /* Simplify reads from constants or constant initializers. */
1335 else if (BITS_PER_UNIT
== 8
1336 && is_gimple_reg_type (ref
->type
)
1337 && (!INTEGRAL_TYPE_P (ref
->type
)
1338 || TYPE_PRECISION (ref
->type
) % BITS_PER_UNIT
== 0))
1340 HOST_WIDE_INT off
= 0;
1342 if (INTEGRAL_TYPE_P (ref
->type
))
1343 size
= TYPE_PRECISION (ref
->type
);
1345 size
= tree_to_shwi (TYPE_SIZE (ref
->type
));
1346 if (size
% BITS_PER_UNIT
!= 0
1347 || size
> MAX_BITSIZE_MODE_ANY_MODE
)
1349 size
/= BITS_PER_UNIT
;
1351 for (i
= 0; i
< operands
.length (); ++i
)
1353 if (TREE_CODE_CLASS (operands
[i
].opcode
) == tcc_constant
)
1358 if (operands
[i
].off
== -1)
1360 off
+= operands
[i
].off
;
1361 if (operands
[i
].opcode
== MEM_REF
)
1367 vn_reference_op_t base
= &operands
[--i
];
1368 tree ctor
= error_mark_node
;
1369 tree decl
= NULL_TREE
;
1370 if (TREE_CODE_CLASS (base
->opcode
) == tcc_constant
)
1372 else if (base
->opcode
== MEM_REF
1373 && base
[1].opcode
== ADDR_EXPR
1374 && (TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == VAR_DECL
1375 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == CONST_DECL
))
1377 decl
= TREE_OPERAND (base
[1].op0
, 0);
1378 ctor
= ctor_for_folding (decl
);
1380 if (ctor
== NULL_TREE
)
1381 return build_zero_cst (ref
->type
);
1382 else if (ctor
!= error_mark_node
)
1386 tree res
= fold_ctor_reference (ref
->type
, ctor
,
1387 off
* BITS_PER_UNIT
,
1388 size
* BITS_PER_UNIT
, decl
);
1391 STRIP_USELESS_TYPE_CONVERSION (res
);
1392 if (is_gimple_min_invariant (res
))
1398 unsigned char buf
[MAX_BITSIZE_MODE_ANY_MODE
/ BITS_PER_UNIT
];
1399 int len
= native_encode_expr (ctor
, buf
, size
, off
);
1401 return native_interpret_expr (ref
->type
, buf
, len
);
1409 /* Return true if OPS contain a storage order barrier. */
1412 contains_storage_order_barrier_p (vec
<vn_reference_op_s
> ops
)
1414 vn_reference_op_t op
;
1417 FOR_EACH_VEC_ELT (ops
, i
, op
)
1418 if (op
->opcode
== VIEW_CONVERT_EXPR
&& op
->reverse
)
1424 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1425 structures into their value numbers. This is done in-place, and
1426 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1427 whether any operands were valueized. */
1429 static vec
<vn_reference_op_s
>
1430 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1432 vn_reference_op_t vro
;
1435 *valueized_anything
= false;
1437 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1439 if (vro
->opcode
== SSA_NAME
1440 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1442 tree tem
= SSA_VAL (vro
->op0
);
1443 if (tem
!= vro
->op0
)
1445 *valueized_anything
= true;
1448 /* If it transforms from an SSA_NAME to a constant, update
1450 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1451 vro
->opcode
= TREE_CODE (vro
->op0
);
1453 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1455 tree tem
= SSA_VAL (vro
->op1
);
1456 if (tem
!= vro
->op1
)
1458 *valueized_anything
= true;
1462 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1464 tree tem
= SSA_VAL (vro
->op2
);
1465 if (tem
!= vro
->op2
)
1467 *valueized_anything
= true;
1471 /* If it transforms from an SSA_NAME to an address, fold with
1472 a preceding indirect reference. */
1475 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1476 && orig
[i
- 1].opcode
== MEM_REF
)
1478 if (vn_reference_fold_indirect (&orig
, &i
))
1479 *valueized_anything
= true;
1482 && vro
->opcode
== SSA_NAME
1483 && orig
[i
- 1].opcode
== MEM_REF
)
1485 if (vn_reference_maybe_forwprop_address (&orig
, &i
))
1486 *valueized_anything
= true;
1488 /* If it transforms a non-constant ARRAY_REF into a constant
1489 one, adjust the constant offset. */
1490 else if (vro
->opcode
== ARRAY_REF
1492 && TREE_CODE (vro
->op0
) == INTEGER_CST
1493 && TREE_CODE (vro
->op1
) == INTEGER_CST
1494 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1496 offset_int off
= ((wi::to_offset (vro
->op0
)
1497 - wi::to_offset (vro
->op1
))
1498 * wi::to_offset (vro
->op2
)
1499 * vn_ref_op_align_unit (vro
));
1500 if (wi::fits_shwi_p (off
))
1501 vro
->off
= off
.to_shwi ();
1508 static vec
<vn_reference_op_s
>
1509 valueize_refs (vec
<vn_reference_op_s
> orig
)
1512 return valueize_refs_1 (orig
, &tem
);
1515 static vec
<vn_reference_op_s
> shared_lookup_references
;
1517 /* Create a vector of vn_reference_op_s structures from REF, a
1518 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1519 this function. *VALUEIZED_ANYTHING will specify whether any
1520 operands were valueized. */
1522 static vec
<vn_reference_op_s
>
1523 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1527 shared_lookup_references
.truncate (0);
1528 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1529 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1530 valueized_anything
);
1531 return shared_lookup_references
;
1534 /* Create a vector of vn_reference_op_s structures from CALL, a
1535 call statement. The vector is shared among all callers of
1538 static vec
<vn_reference_op_s
>
1539 valueize_shared_reference_ops_from_call (gcall
*call
)
1543 shared_lookup_references
.truncate (0);
1544 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1545 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1546 return shared_lookup_references
;
1549 /* Lookup a SCCVN reference operation VR in the current hash table.
1550 Returns the resulting value number if it exists in the hash table,
1551 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1552 vn_reference_t stored in the hashtable if something is found. */
1555 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1557 vn_reference_s
**slot
;
1560 hash
= vr
->hashcode
;
1561 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1562 if (!slot
&& current_info
== optimistic_info
)
1563 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1567 *vnresult
= (vn_reference_t
)*slot
;
1568 return ((vn_reference_t
)*slot
)->result
;
1574 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1575 with the current VUSE and performs the expression lookup. */
1578 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1579 unsigned int cnt
, void *vr_
)
1581 vn_reference_t vr
= (vn_reference_t
)vr_
;
1582 vn_reference_s
**slot
;
1585 /* This bounds the stmt walks we perform on reference lookups
1586 to O(1) instead of O(N) where N is the number of dominating
1588 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1592 *last_vuse_ptr
= vuse
;
1594 /* Fixup vuse and hash. */
1596 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1597 vr
->vuse
= vuse_ssa_val (vuse
);
1599 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1601 hash
= vr
->hashcode
;
1602 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1603 if (!slot
&& current_info
== optimistic_info
)
1604 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1611 /* Lookup an existing or insert a new vn_reference entry into the
1612 value table for the VUSE, SET, TYPE, OPERANDS reference which
1613 has the value VALUE which is either a constant or an SSA name. */
1615 static vn_reference_t
1616 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1619 vec
<vn_reference_op_s
,
1624 vn_reference_t result
;
1627 vr1
.operands
= operands
;
1630 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1631 if (vn_reference_lookup_1 (&vr1
, &result
))
1633 if (TREE_CODE (value
) == SSA_NAME
)
1634 value_id
= VN_INFO (value
)->value_id
;
1636 value_id
= get_or_alloc_constant_value_id (value
);
1637 return vn_reference_insert_pieces (vuse
, set
, type
,
1638 operands
.copy (), value
, value_id
);
1641 static vn_nary_op_t
vn_nary_op_insert_stmt (gimple
*stmt
, tree result
);
1642 static unsigned mprts_hook_cnt
;
1644 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
1647 vn_lookup_simplify_result (code_helper rcode
, tree type
, tree
*ops
)
1649 if (!rcode
.is_tree_code ())
1651 vn_nary_op_t vnresult
= NULL
;
1652 tree res
= vn_nary_op_lookup_pieces (TREE_CODE_LENGTH ((tree_code
) rcode
),
1653 (tree_code
) rcode
, type
, ops
, &vnresult
);
1654 /* We can end up endlessly recursing simplifications if the lookup above
1655 presents us with a def-use chain that mirrors the original simplification.
1656 See PR80887 for an example. Limit successful lookup artificially
1657 to 10 times if we are called as mprts_hook. */
1660 && --mprts_hook_cnt
== 0)
1662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1663 fprintf (dump_file
, "Resetting mprts_hook after too many "
1670 /* Return a value-number for RCODE OPS... either by looking up an existing
1671 value-number for the simplified result or by inserting the operation if
1675 vn_nary_build_or_lookup_1 (code_helper rcode
, tree type
, tree
*ops
,
1678 tree result
= NULL_TREE
;
1679 /* We will be creating a value number for
1681 So first simplify and lookup this expression to see if it
1682 is already available. */
1683 mprts_hook
= vn_lookup_simplify_result
;
1686 switch (TREE_CODE_LENGTH ((tree_code
) rcode
))
1689 res
= gimple_resimplify1 (NULL
, &rcode
, type
, ops
, vn_valueize
);
1692 res
= gimple_resimplify2 (NULL
, &rcode
, type
, ops
, vn_valueize
);
1695 res
= gimple_resimplify3 (NULL
, &rcode
, type
, ops
, vn_valueize
);
1699 gimple
*new_stmt
= NULL
;
1701 && gimple_simplified_result_is_gimple_val (rcode
, ops
))
1702 /* The expression is already available. */
1706 tree val
= vn_lookup_simplify_result (rcode
, type
, ops
);
1709 gimple_seq stmts
= NULL
;
1710 result
= maybe_push_res_to_seq (rcode
, type
, ops
, &stmts
);
1713 gcc_assert (gimple_seq_singleton_p (stmts
));
1714 new_stmt
= gimple_seq_first_stmt (stmts
);
1718 /* The expression is already available. */
1723 /* The expression is not yet available, value-number lhs to
1724 the new SSA_NAME we created. */
1725 /* Initialize value-number information properly. */
1726 VN_INFO_GET (result
)->valnum
= result
;
1727 VN_INFO (result
)->value_id
= get_next_value_id ();
1728 gimple_seq_add_stmt_without_update (&VN_INFO (result
)->expr
,
1730 VN_INFO (result
)->needs_insertion
= true;
1731 /* ??? PRE phi-translation inserts NARYs without corresponding
1732 SSA name result. Re-use those but set their result according
1733 to the stmt we just built. */
1734 vn_nary_op_t nary
= NULL
;
1735 vn_nary_op_lookup_stmt (new_stmt
, &nary
);
1738 gcc_assert (nary
->result
== NULL_TREE
);
1739 nary
->result
= gimple_assign_lhs (new_stmt
);
1741 /* As all "inserted" statements are singleton SCCs, insert
1742 to the valid table. This is strictly needed to
1743 avoid re-generating new value SSA_NAMEs for the same
1744 expression during SCC iteration over and over (the
1745 optimistic table gets cleared after each iteration).
1746 We do not need to insert into the optimistic table, as
1747 lookups there will fall back to the valid table. */
1748 else if (current_info
== optimistic_info
)
1750 current_info
= valid_info
;
1751 vn_nary_op_insert_stmt (new_stmt
, result
);
1752 current_info
= optimistic_info
;
1755 vn_nary_op_insert_stmt (new_stmt
, result
);
1756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1758 fprintf (dump_file
, "Inserting name ");
1759 print_generic_expr (dump_file
, result
);
1760 fprintf (dump_file
, " for expression ");
1761 print_gimple_expr (dump_file
, new_stmt
, 0, TDF_SLIM
);
1762 fprintf (dump_file
, "\n");
1768 /* Return a value-number for RCODE OPS... either by looking up an existing
1769 value-number for the simplified result or by inserting the operation. */
1772 vn_nary_build_or_lookup (code_helper rcode
, tree type
, tree
*ops
)
1774 return vn_nary_build_or_lookup_1 (rcode
, type
, ops
, true);
1777 /* Try to simplify the expression RCODE OPS... of type TYPE and return
1778 its value if present. */
1781 vn_nary_simplify (vn_nary_op_t nary
)
1783 if (nary
->length
> 3)
1786 memcpy (ops
, nary
->op
, sizeof (tree
) * nary
->length
);
1787 return vn_nary_build_or_lookup_1 (nary
->opcode
, nary
->type
, ops
, false);
1791 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1792 from the statement defining VUSE and if not successful tries to
1793 translate *REFP and VR_ through an aggregate copy at the definition
1794 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
1795 of *REF and *VR. If only disambiguation was performed then
1796 *DISAMBIGUATE_ONLY is set to true. */
1799 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
,
1800 bool *disambiguate_only
)
1802 vn_reference_t vr
= (vn_reference_t
)vr_
;
1803 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1804 tree base
= ao_ref_base (ref
);
1805 HOST_WIDE_INT offset
, maxsize
;
1806 static vec
<vn_reference_op_s
> lhs_ops
;
1808 bool lhs_ref_ok
= false;
1810 /* If the reference is based on a parameter that was determined as
1811 pointing to readonly memory it doesn't change. */
1812 if (TREE_CODE (base
) == MEM_REF
1813 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
1814 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base
, 0))
1815 && bitmap_bit_p (const_parms
,
1816 SSA_NAME_VERSION (TREE_OPERAND (base
, 0))))
1818 *disambiguate_only
= true;
1822 /* First try to disambiguate after value-replacing in the definitions LHS. */
1823 if (is_gimple_assign (def_stmt
))
1825 tree lhs
= gimple_assign_lhs (def_stmt
);
1826 bool valueized_anything
= false;
1827 /* Avoid re-allocation overhead. */
1828 lhs_ops
.truncate (0);
1829 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1830 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1831 if (valueized_anything
)
1833 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1834 get_alias_set (lhs
),
1835 TREE_TYPE (lhs
), lhs_ops
);
1837 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1839 *disambiguate_only
= true;
1845 ao_ref_init (&lhs_ref
, lhs
);
1849 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
1850 && gimple_call_num_args (def_stmt
) <= 4)
1852 /* For builtin calls valueize its arguments and call the
1853 alias oracle again. Valueization may improve points-to
1854 info of pointers and constify size and position arguments.
1855 Originally this was motivated by PR61034 which has
1856 conditional calls to free falsely clobbering ref because
1857 of imprecise points-to info of the argument. */
1859 bool valueized_anything
= false;
1860 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1862 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
1863 if (TREE_CODE (oldargs
[i
]) == SSA_NAME
1864 && VN_INFO (oldargs
[i
])->valnum
!= oldargs
[i
])
1866 gimple_call_set_arg (def_stmt
, i
, VN_INFO (oldargs
[i
])->valnum
);
1867 valueized_anything
= true;
1870 if (valueized_anything
)
1872 bool res
= call_may_clobber_ref_p_1 (as_a
<gcall
*> (def_stmt
),
1874 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1875 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
1878 *disambiguate_only
= true;
1884 if (*disambiguate_only
)
1887 offset
= ref
->offset
;
1888 maxsize
= ref
->max_size
;
1890 /* If we cannot constrain the size of the reference we cannot
1891 test if anything kills it. */
1895 /* We can't deduce anything useful from clobbers. */
1896 if (gimple_clobber_p (def_stmt
))
1899 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1900 from that definition.
1902 if (is_gimple_reg_type (vr
->type
)
1903 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1904 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1905 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1906 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1908 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1910 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1912 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
,
1914 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1915 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1916 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1918 && operand_equal_p (base
, base2
, 0)
1919 && offset2
<= offset
1920 && offset2
+ size2
>= offset
+ maxsize
)
1922 tree val
= build_zero_cst (vr
->type
);
1923 return vn_reference_lookup_or_insert_for_pieces
1924 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1928 /* 2) Assignment from an empty CONSTRUCTOR. */
1929 else if (is_gimple_reg_type (vr
->type
)
1930 && gimple_assign_single_p (def_stmt
)
1931 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1932 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1935 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1937 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1938 &offset2
, &size2
, &maxsize2
, &reverse
);
1940 && operand_equal_p (base
, base2
, 0)
1941 && offset2
<= offset
1942 && offset2
+ size2
>= offset
+ maxsize
)
1944 tree val
= build_zero_cst (vr
->type
);
1945 return vn_reference_lookup_or_insert_for_pieces
1946 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1950 /* 3) Assignment from a constant. We can use folds native encode/interpret
1951 routines to extract the assigned bits. */
1952 else if (ref
->size
== maxsize
1953 && is_gimple_reg_type (vr
->type
)
1954 && !contains_storage_order_barrier_p (vr
->operands
)
1955 && gimple_assign_single_p (def_stmt
)
1956 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1957 && maxsize
% BITS_PER_UNIT
== 0
1958 && offset
% BITS_PER_UNIT
== 0
1959 && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
))
1960 || (TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
1961 && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt
))))))
1964 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1966 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1967 &offset2
, &size2
, &maxsize2
, &reverse
);
1970 && maxsize2
== size2
1971 && size2
% BITS_PER_UNIT
== 0
1972 && offset2
% BITS_PER_UNIT
== 0
1973 && operand_equal_p (base
, base2
, 0)
1974 && offset2
<= offset
1975 && offset2
+ size2
>= offset
+ maxsize
)
1977 /* We support up to 512-bit values (for V8DFmode). */
1978 unsigned char buffer
[64];
1981 tree rhs
= gimple_assign_rhs1 (def_stmt
);
1982 if (TREE_CODE (rhs
) == SSA_NAME
)
1983 rhs
= SSA_VAL (rhs
);
1984 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1985 buffer
, sizeof (buffer
));
1988 tree type
= vr
->type
;
1989 /* Make sure to interpret in a type that has a range
1990 covering the whole access size. */
1991 if (INTEGRAL_TYPE_P (vr
->type
)
1992 && ref
->size
!= TYPE_PRECISION (vr
->type
))
1993 type
= build_nonstandard_integer_type (ref
->size
,
1994 TYPE_UNSIGNED (type
));
1995 tree val
= native_interpret_expr (type
,
1997 + ((offset
- offset2
)
1999 ref
->size
/ BITS_PER_UNIT
);
2000 /* If we chop off bits because the types precision doesn't
2001 match the memory access size this is ok when optimizing
2002 reads but not when called from the DSE code during
2005 && type
!= vr
->type
)
2007 if (! int_fits_type_p (val
, vr
->type
))
2010 val
= fold_convert (vr
->type
, val
);
2014 return vn_reference_lookup_or_insert_for_pieces
2015 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2020 /* 4) Assignment from an SSA name which definition we may be able
2021 to access pieces from. */
2022 else if (ref
->size
== maxsize
2023 && is_gimple_reg_type (vr
->type
)
2024 && !contains_storage_order_barrier_p (vr
->operands
)
2025 && gimple_assign_single_p (def_stmt
)
2026 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
2029 HOST_WIDE_INT offset2
, size2
, maxsize2
;
2031 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
2032 &offset2
, &size2
, &maxsize2
,
2036 && maxsize2
== size2
2037 && operand_equal_p (base
, base2
, 0)
2038 && offset2
<= offset
2039 && offset2
+ size2
>= offset
+ maxsize
2040 /* ??? We can't handle bitfield precision extracts without
2041 either using an alternate type for the BIT_FIELD_REF and
2042 then doing a conversion or possibly adjusting the offset
2043 according to endianness. */
2044 && (! INTEGRAL_TYPE_P (vr
->type
)
2045 || ref
->size
== TYPE_PRECISION (vr
->type
))
2046 && ref
->size
% BITS_PER_UNIT
== 0)
2048 code_helper rcode
= BIT_FIELD_REF
;
2050 ops
[0] = SSA_VAL (gimple_assign_rhs1 (def_stmt
));
2051 ops
[1] = bitsize_int (ref
->size
);
2052 ops
[2] = bitsize_int (offset
- offset2
);
2053 tree val
= vn_nary_build_or_lookup (rcode
, vr
->type
, ops
);
2055 && (TREE_CODE (val
) != SSA_NAME
2056 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
2058 vn_reference_t res
= vn_reference_lookup_or_insert_for_pieces
2059 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2065 /* 5) For aggregate copies translate the reference through them if
2066 the copy kills ref. */
2067 else if (vn_walk_kind
== VN_WALKREWRITE
2068 && gimple_assign_single_p (def_stmt
)
2069 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
2070 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
2071 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
2074 HOST_WIDE_INT maxsize2
;
2076 auto_vec
<vn_reference_op_s
> rhs
;
2077 vn_reference_op_t vro
;
2083 /* See if the assignment kills REF. */
2084 base2
= ao_ref_base (&lhs_ref
);
2085 maxsize2
= lhs_ref
.max_size
;
2088 && (TREE_CODE (base
) != MEM_REF
2089 || TREE_CODE (base2
) != MEM_REF
2090 || TREE_OPERAND (base
, 0) != TREE_OPERAND (base2
, 0)
2091 || !tree_int_cst_equal (TREE_OPERAND (base
, 1),
2092 TREE_OPERAND (base2
, 1))))
2093 || !stmt_kills_ref_p (def_stmt
, ref
))
2096 /* Find the common base of ref and the lhs. lhs_ops already
2097 contains valueized operands for the lhs. */
2098 i
= vr
->operands
.length () - 1;
2099 j
= lhs_ops
.length () - 1;
2100 while (j
>= 0 && i
>= 0
2101 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
2107 /* ??? The innermost op should always be a MEM_REF and we already
2108 checked that the assignment to the lhs kills vr. Thus for
2109 aggregate copies using char[] types the vn_reference_op_eq
2110 may fail when comparing types for compatibility. But we really
2111 don't care here - further lookups with the rewritten operands
2112 will simply fail if we messed up types too badly. */
2113 HOST_WIDE_INT extra_off
= 0;
2114 if (j
== 0 && i
>= 0
2115 && lhs_ops
[0].opcode
== MEM_REF
2116 && lhs_ops
[0].off
!= -1)
2118 if (lhs_ops
[0].off
== vr
->operands
[i
].off
)
2120 else if (vr
->operands
[i
].opcode
== MEM_REF
2121 && vr
->operands
[i
].off
!= -1)
2123 extra_off
= vr
->operands
[i
].off
- lhs_ops
[0].off
;
2128 /* i now points to the first additional op.
2129 ??? LHS may not be completely contained in VR, one or more
2130 VIEW_CONVERT_EXPRs could be in its way. We could at least
2131 try handling outermost VIEW_CONVERT_EXPRs. */
2135 /* Punt if the additional ops contain a storage order barrier. */
2136 for (k
= i
; k
>= 0; k
--)
2138 vro
= &vr
->operands
[k
];
2139 if (vro
->opcode
== VIEW_CONVERT_EXPR
&& vro
->reverse
)
2143 /* Now re-write REF to be based on the rhs of the assignment. */
2144 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
2146 /* Apply an extra offset to the inner MEM_REF of the RHS. */
2149 if (rhs
.length () < 2
2150 || rhs
[0].opcode
!= MEM_REF
2151 || rhs
[0].off
== -1)
2153 rhs
[0].off
+= extra_off
;
2154 rhs
[0].op0
= int_const_binop (PLUS_EXPR
, rhs
[0].op0
,
2155 build_int_cst (TREE_TYPE (rhs
[0].op0
),
2159 /* We need to pre-pend vr->operands[0..i] to rhs. */
2160 vec
<vn_reference_op_s
> old
= vr
->operands
;
2161 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
2162 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
2164 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
2165 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
2166 vr
->operands
[i
+ 1 + j
] = *vro
;
2167 vr
->operands
= valueize_refs (vr
->operands
);
2168 if (old
== shared_lookup_references
)
2169 shared_lookup_references
= vr
->operands
;
2170 vr
->hashcode
= vn_reference_compute_hash (vr
);
2172 /* Try folding the new reference to a constant. */
2173 tree val
= fully_constant_vn_reference_p (vr
);
2175 return vn_reference_lookup_or_insert_for_pieces
2176 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2178 /* Adjust *ref from the new operands. */
2179 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2181 /* This can happen with bitfields. */
2182 if (ref
->size
!= r
.size
)
2186 /* Do not update last seen VUSE after translating. */
2187 last_vuse_ptr
= NULL
;
2189 /* Keep looking for the adjusted *REF / VR pair. */
2193 /* 6) For memcpy copies translate the reference through them if
2194 the copy kills ref. */
2195 else if (vn_walk_kind
== VN_WALKREWRITE
2196 && is_gimple_reg_type (vr
->type
)
2197 /* ??? Handle BCOPY as well. */
2198 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
2199 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
2200 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
2201 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
2202 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
2203 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
2204 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
2205 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
2209 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
2210 vn_reference_op_s op
;
2213 /* Only handle non-variable, addressable refs. */
2214 if (ref
->size
!= maxsize
2215 || offset
% BITS_PER_UNIT
!= 0
2216 || ref
->size
% BITS_PER_UNIT
!= 0)
2219 /* Extract a pointer base and an offset for the destination. */
2220 lhs
= gimple_call_arg (def_stmt
, 0);
2222 if (TREE_CODE (lhs
) == SSA_NAME
)
2224 lhs
= SSA_VAL (lhs
);
2225 if (TREE_CODE (lhs
) == SSA_NAME
)
2227 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
2228 if (gimple_assign_single_p (def_stmt
)
2229 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2230 lhs
= gimple_assign_rhs1 (def_stmt
);
2233 if (TREE_CODE (lhs
) == ADDR_EXPR
)
2235 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
2239 if (TREE_CODE (tem
) == MEM_REF
2240 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
2242 lhs
= TREE_OPERAND (tem
, 0);
2243 if (TREE_CODE (lhs
) == SSA_NAME
)
2244 lhs
= SSA_VAL (lhs
);
2245 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
2247 else if (DECL_P (tem
))
2248 lhs
= build_fold_addr_expr (tem
);
2252 if (TREE_CODE (lhs
) != SSA_NAME
2253 && TREE_CODE (lhs
) != ADDR_EXPR
)
2256 /* Extract a pointer base and an offset for the source. */
2257 rhs
= gimple_call_arg (def_stmt
, 1);
2259 if (TREE_CODE (rhs
) == SSA_NAME
)
2260 rhs
= SSA_VAL (rhs
);
2261 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2263 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
2267 if (TREE_CODE (tem
) == MEM_REF
2268 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
2270 rhs
= TREE_OPERAND (tem
, 0);
2271 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
2273 else if (DECL_P (tem
))
2274 rhs
= build_fold_addr_expr (tem
);
2278 if (TREE_CODE (rhs
) != SSA_NAME
2279 && TREE_CODE (rhs
) != ADDR_EXPR
)
2282 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
2284 /* The bases of the destination and the references have to agree. */
2285 if ((TREE_CODE (base
) != MEM_REF
2287 || (TREE_CODE (base
) == MEM_REF
2288 && (TREE_OPERAND (base
, 0) != lhs
2289 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
2291 && (TREE_CODE (lhs
) != ADDR_EXPR
2292 || TREE_OPERAND (lhs
, 0) != base
)))
2295 at
= offset
/ BITS_PER_UNIT
;
2296 if (TREE_CODE (base
) == MEM_REF
)
2297 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
2298 /* If the access is completely outside of the memcpy destination
2299 area there is no aliasing. */
2300 if (lhs_offset
>= at
+ maxsize
/ BITS_PER_UNIT
2301 || lhs_offset
+ copy_size
<= at
)
2303 /* And the access has to be contained within the memcpy destination. */
2305 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
2308 /* Make room for 2 operands in the new reference. */
2309 if (vr
->operands
.length () < 2)
2311 vec
<vn_reference_op_s
> old
= vr
->operands
;
2312 vr
->operands
.safe_grow_cleared (2);
2313 if (old
== shared_lookup_references
)
2314 shared_lookup_references
= vr
->operands
;
2317 vr
->operands
.truncate (2);
2319 /* The looked-through reference is a simple MEM_REF. */
2320 memset (&op
, 0, sizeof (op
));
2322 op
.opcode
= MEM_REF
;
2323 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
2324 op
.off
= at
- lhs_offset
+ rhs_offset
;
2325 vr
->operands
[0] = op
;
2326 op
.type
= TREE_TYPE (rhs
);
2327 op
.opcode
= TREE_CODE (rhs
);
2330 vr
->operands
[1] = op
;
2331 vr
->hashcode
= vn_reference_compute_hash (vr
);
2333 /* Try folding the new reference to a constant. */
2334 tree val
= fully_constant_vn_reference_p (vr
);
2336 return vn_reference_lookup_or_insert_for_pieces
2337 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2339 /* Adjust *ref from the new operands. */
2340 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2342 /* This can happen with bitfields. */
2343 if (ref
->size
!= r
.size
)
2347 /* Do not update last seen VUSE after translating. */
2348 last_vuse_ptr
= NULL
;
2350 /* Keep looking for the adjusted *REF / VR pair. */
2354 /* Bail out and stop walking. */
2358 /* Return a reference op vector from OP that can be used for
2359 vn_reference_lookup_pieces. The caller is responsible for releasing
2362 vec
<vn_reference_op_s
>
2363 vn_reference_operands_for_lookup (tree op
)
2366 return valueize_shared_reference_ops_from_ref (op
, &valueized
).copy ();
2369 /* Lookup a reference operation by it's parts, in the current hash table.
2370 Returns the resulting value number if it exists in the hash table,
2371 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2372 vn_reference_t stored in the hashtable if something is found. */
2375 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2376 vec
<vn_reference_op_s
> operands
,
2377 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2379 struct vn_reference_s vr1
;
2387 vr1
.vuse
= vuse_ssa_val (vuse
);
2388 shared_lookup_references
.truncate (0);
2389 shared_lookup_references
.safe_grow (operands
.length ());
2390 memcpy (shared_lookup_references
.address (),
2391 operands
.address (),
2392 sizeof (vn_reference_op_s
)
2393 * operands
.length ());
2394 vr1
.operands
= operands
= shared_lookup_references
2395 = valueize_refs (shared_lookup_references
);
2398 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2399 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2402 vn_reference_lookup_1 (&vr1
, vnresult
);
2404 && kind
!= VN_NOWALK
2408 vn_walk_kind
= kind
;
2409 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2411 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2412 vn_reference_lookup_2
,
2413 vn_reference_lookup_3
,
2414 vuse_ssa_val
, &vr1
);
2415 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2419 return (*vnresult
)->result
;
2424 /* Lookup OP in the current hash table, and return the resulting value
2425 number if it exists in the hash table. Return NULL_TREE if it does
2426 not exist in the hash table or if the result field of the structure
2427 was NULL.. VNRESULT will be filled in with the vn_reference_t
2428 stored in the hashtable if one exists. When TBAA_P is false assume
2429 we are looking up a store and treat it as having alias-set zero. */
2432 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2433 vn_reference_t
*vnresult
, bool tbaa_p
)
2435 vec
<vn_reference_op_s
> operands
;
2436 struct vn_reference_s vr1
;
2438 bool valuezied_anything
;
2443 vr1
.vuse
= vuse_ssa_val (vuse
);
2444 vr1
.operands
= operands
2445 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2446 vr1
.type
= TREE_TYPE (op
);
2447 vr1
.set
= tbaa_p
? get_alias_set (op
) : 0;
2448 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2449 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2452 if (kind
!= VN_NOWALK
2455 vn_reference_t wvnresult
;
2457 /* Make sure to use a valueized reference if we valueized anything.
2458 Otherwise preserve the full reference for advanced TBAA. */
2459 if (!valuezied_anything
2460 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2462 ao_ref_init (&r
, op
);
2464 r
.ref_alias_set
= r
.base_alias_set
= 0;
2465 vn_walk_kind
= kind
;
2467 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2468 vn_reference_lookup_2
,
2469 vn_reference_lookup_3
,
2470 vuse_ssa_val
, &vr1
);
2471 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2475 *vnresult
= wvnresult
;
2476 return wvnresult
->result
;
2482 return vn_reference_lookup_1 (&vr1
, vnresult
);
2485 /* Lookup CALL in the current hash table and return the entry in
2486 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2489 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
2495 tree vuse
= gimple_vuse (call
);
2497 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2498 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
2499 vr
->type
= gimple_expr_type (call
);
2501 vr
->hashcode
= vn_reference_compute_hash (vr
);
2502 vn_reference_lookup_1 (vr
, vnresult
);
2505 /* Insert OP into the current hash table with a value number of
2506 RESULT, and return the resulting reference structure we created. */
2508 static vn_reference_t
2509 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2511 vn_reference_s
**slot
;
2515 vr1
= current_info
->references_pool
->allocate ();
2516 if (TREE_CODE (result
) == SSA_NAME
)
2517 vr1
->value_id
= VN_INFO (result
)->value_id
;
2519 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2520 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2521 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2522 vr1
->type
= TREE_TYPE (op
);
2523 vr1
->set
= get_alias_set (op
);
2524 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2525 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2526 vr1
->result_vdef
= vdef
;
2528 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2531 /* Because we lookup stores using vuses, and value number failures
2532 using the vdefs (see visit_reference_op_store for how and why),
2533 it's possible that on failure we may try to insert an already
2534 inserted store. This is not wrong, there is no ssa name for a
2535 store that we could use as a differentiator anyway. Thus, unlike
2536 the other lookup functions, you cannot gcc_assert (!*slot)
2539 /* But free the old slot in case of a collision. */
2541 free_reference (*slot
);
2547 /* Insert a reference by it's pieces into the current hash table with
2548 a value number of RESULT. Return the resulting reference
2549 structure we created. */
2552 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2553 vec
<vn_reference_op_s
> operands
,
2554 tree result
, unsigned int value_id
)
2557 vn_reference_s
**slot
;
2560 vr1
= current_info
->references_pool
->allocate ();
2561 vr1
->value_id
= value_id
;
2562 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2563 vr1
->operands
= valueize_refs (operands
);
2566 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2567 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2568 result
= SSA_VAL (result
);
2569 vr1
->result
= result
;
2571 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2574 /* At this point we should have all the things inserted that we have
2575 seen before, and we should never try inserting something that
2577 gcc_assert (!*slot
);
2579 free_reference (*slot
);
2585 /* Compute and return the hash value for nary operation VBO1. */
2588 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2590 inchash::hash hstate
;
2593 for (i
= 0; i
< vno1
->length
; ++i
)
2594 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2595 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2597 if (((vno1
->length
== 2
2598 && commutative_tree_code (vno1
->opcode
))
2599 || (vno1
->length
== 3
2600 && commutative_ternary_tree_code (vno1
->opcode
)))
2601 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
2602 std::swap (vno1
->op
[0], vno1
->op
[1]);
2603 else if (TREE_CODE_CLASS (vno1
->opcode
) == tcc_comparison
2604 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
2606 std::swap (vno1
->op
[0], vno1
->op
[1]);
2607 vno1
->opcode
= swap_tree_comparison (vno1
->opcode
);
2610 hstate
.add_int (vno1
->opcode
);
2611 for (i
= 0; i
< vno1
->length
; ++i
)
2612 inchash::add_expr (vno1
->op
[i
], hstate
);
2614 return hstate
.end ();
2617 /* Compare nary operations VNO1 and VNO2 and return true if they are
2621 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2625 if (vno1
->hashcode
!= vno2
->hashcode
)
2628 if (vno1
->length
!= vno2
->length
)
2631 if (vno1
->opcode
!= vno2
->opcode
2632 || !types_compatible_p (vno1
->type
, vno2
->type
))
2635 for (i
= 0; i
< vno1
->length
; ++i
)
2636 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2642 /* Initialize VNO from the pieces provided. */
2645 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2646 enum tree_code code
, tree type
, tree
*ops
)
2649 vno
->length
= length
;
2651 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2654 /* Initialize VNO from OP. */
2657 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2661 vno
->opcode
= TREE_CODE (op
);
2662 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2663 vno
->type
= TREE_TYPE (op
);
2664 for (i
= 0; i
< vno
->length
; ++i
)
2665 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2668 /* Return the number of operands for a vn_nary ops structure from STMT. */
2671 vn_nary_length_from_stmt (gimple
*stmt
)
2673 switch (gimple_assign_rhs_code (stmt
))
2677 case VIEW_CONVERT_EXPR
:
2684 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2687 return gimple_num_ops (stmt
) - 1;
2691 /* Initialize VNO from STMT. */
2694 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple
*stmt
)
2698 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2699 vno
->type
= gimple_expr_type (stmt
);
2700 switch (vno
->opcode
)
2704 case VIEW_CONVERT_EXPR
:
2706 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2711 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2712 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2713 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2717 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2718 for (i
= 0; i
< vno
->length
; ++i
)
2719 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2723 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2724 vno
->length
= gimple_num_ops (stmt
) - 1;
2725 for (i
= 0; i
< vno
->length
; ++i
)
2726 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2730 /* Compute the hashcode for VNO and look for it in the hash table;
2731 return the resulting value number if it exists in the hash table.
2732 Return NULL_TREE if it does not exist in the hash table or if the
2733 result field of the operation is NULL. VNRESULT will contain the
2734 vn_nary_op_t from the hashtable if it exists. */
2737 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2739 vn_nary_op_s
**slot
;
2744 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2745 slot
= current_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2747 if (!slot
&& current_info
== optimistic_info
)
2748 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2754 return (*slot
)->result
;
2757 /* Lookup a n-ary operation by its pieces and return the resulting value
2758 number if it exists in the hash table. Return NULL_TREE if it does
2759 not exist in the hash table or if the result field of the operation
2760 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2764 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2765 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2767 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2768 sizeof_vn_nary_op (length
));
2769 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2770 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2773 /* Lookup OP in the current hash table, and return the resulting value
2774 number if it exists in the hash table. Return NULL_TREE if it does
2775 not exist in the hash table or if the result field of the operation
2776 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2780 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2783 = XALLOCAVAR (struct vn_nary_op_s
,
2784 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2785 init_vn_nary_op_from_op (vno1
, op
);
2786 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2789 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2790 value number if it exists in the hash table. Return NULL_TREE if
2791 it does not exist in the hash table. VNRESULT will contain the
2792 vn_nary_op_t from the hashtable if it exists. */
2795 vn_nary_op_lookup_stmt (gimple
*stmt
, vn_nary_op_t
*vnresult
)
2798 = XALLOCAVAR (struct vn_nary_op_s
,
2799 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2800 init_vn_nary_op_from_stmt (vno1
, stmt
);
2801 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2804 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2807 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2809 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2812 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2816 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2818 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2819 ¤t_info
->nary_obstack
);
2821 vno1
->value_id
= value_id
;
2822 vno1
->length
= length
;
2823 vno1
->result
= result
;
2828 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2829 VNO->HASHCODE first. */
2832 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
2835 vn_nary_op_s
**slot
;
2838 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2840 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2841 /* While we do not want to insert things twice it's awkward to
2842 avoid it in the case where visit_nary_op pattern-matches stuff
2843 and ends up simplifying the replacement to itself. We then
2844 get two inserts, one from visit_nary_op and one from
2845 vn_nary_build_or_lookup.
2846 So allow inserts with the same value number. */
2847 if (*slot
&& (*slot
)->result
== vno
->result
)
2850 gcc_assert (!*slot
);
2856 /* Insert a n-ary operation into the current hash table using it's
2857 pieces. Return the vn_nary_op_t structure we created and put in
2861 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2862 tree type
, tree
*ops
,
2863 tree result
, unsigned int value_id
)
2865 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2866 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2867 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2870 /* Insert OP into the current hash table with a value number of
2871 RESULT. Return the vn_nary_op_t structure we created and put in
2875 vn_nary_op_insert (tree op
, tree result
)
2877 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2880 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2881 init_vn_nary_op_from_op (vno1
, op
);
2882 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2885 /* Insert the rhs of STMT into the current hash table with a value number of
2889 vn_nary_op_insert_stmt (gimple
*stmt
, tree result
)
2892 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2893 result
, VN_INFO (result
)->value_id
);
2894 init_vn_nary_op_from_stmt (vno1
, stmt
);
2895 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2898 /* Compute a hashcode for PHI operation VP1 and return it. */
2900 static inline hashval_t
2901 vn_phi_compute_hash (vn_phi_t vp1
)
2903 inchash::hash
hstate (vp1
->phiargs
.length () > 2
2904 ? vp1
->block
->index
: vp1
->phiargs
.length ());
2910 /* If all PHI arguments are constants we need to distinguish
2911 the PHI node via its type. */
2913 hstate
.merge_hash (vn_hash_type (type
));
2915 FOR_EACH_EDGE (e
, ei
, vp1
->block
->preds
)
2917 /* Don't hash backedge values they need to be handled as VN_TOP
2918 for optimistic value-numbering. */
2919 if (e
->flags
& EDGE_DFS_BACK
)
2922 phi1op
= vp1
->phiargs
[e
->dest_idx
];
2923 if (phi1op
== VN_TOP
)
2925 inchash::add_expr (phi1op
, hstate
);
2928 return hstate
.end ();
2932 /* Return true if COND1 and COND2 represent the same condition, set
2933 *INVERTED_P if one needs to be inverted to make it the same as
2937 cond_stmts_equal_p (gcond
*cond1
, tree lhs1
, tree rhs1
,
2938 gcond
*cond2
, tree lhs2
, tree rhs2
, bool *inverted_p
)
2940 enum tree_code code1
= gimple_cond_code (cond1
);
2941 enum tree_code code2
= gimple_cond_code (cond2
);
2943 *inverted_p
= false;
2946 else if (code1
== swap_tree_comparison (code2
))
2947 std::swap (lhs2
, rhs2
);
2948 else if (code1
== invert_tree_comparison (code2
, HONOR_NANS (lhs2
)))
2950 else if (code1
== invert_tree_comparison
2951 (swap_tree_comparison (code2
), HONOR_NANS (lhs2
)))
2953 std::swap (lhs2
, rhs2
);
2959 return ((expressions_equal_p (lhs1
, lhs2
)
2960 && expressions_equal_p (rhs1
, rhs2
))
2961 || (commutative_tree_code (code1
)
2962 && expressions_equal_p (lhs1
, rhs2
)
2963 && expressions_equal_p (rhs1
, lhs2
)));
2966 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2969 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2971 if (vp1
->hashcode
!= vp2
->hashcode
)
2974 if (vp1
->block
!= vp2
->block
)
2976 if (vp1
->phiargs
.length () != vp2
->phiargs
.length ())
2979 switch (vp1
->phiargs
.length ())
2982 /* Single-arg PHIs are just copies. */
2987 /* Rule out backedges into the PHI. */
2988 if (vp1
->block
->loop_father
->header
== vp1
->block
2989 || vp2
->block
->loop_father
->header
== vp2
->block
)
2992 /* If the PHI nodes do not have compatible types
2993 they are not the same. */
2994 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2998 = get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3000 = get_immediate_dominator (CDI_DOMINATORS
, vp2
->block
);
3001 /* If the immediate dominator end in switch stmts multiple
3002 values may end up in the same PHI arg via intermediate
3004 if (EDGE_COUNT (idom1
->succs
) != 2
3005 || EDGE_COUNT (idom2
->succs
) != 2)
3008 /* Verify the controlling stmt is the same. */
3009 gimple
*last1
= last_stmt (idom1
);
3010 gimple
*last2
= last_stmt (idom2
);
3011 if (gimple_code (last1
) != GIMPLE_COND
3012 || gimple_code (last2
) != GIMPLE_COND
)
3015 if (! cond_stmts_equal_p (as_a
<gcond
*> (last1
),
3016 vp1
->cclhs
, vp1
->ccrhs
,
3017 as_a
<gcond
*> (last2
),
3018 vp2
->cclhs
, vp2
->ccrhs
,
3022 /* Get at true/false controlled edges into the PHI. */
3023 edge te1
, te2
, fe1
, fe2
;
3024 if (! extract_true_false_controlled_edges (idom1
, vp1
->block
,
3026 || ! extract_true_false_controlled_edges (idom2
, vp2
->block
,
3030 /* Swap edges if the second condition is the inverted of the
3033 std::swap (te2
, fe2
);
3035 /* ??? Handle VN_TOP specially. */
3036 if (! expressions_equal_p (vp1
->phiargs
[te1
->dest_idx
],
3037 vp2
->phiargs
[te2
->dest_idx
])
3038 || ! expressions_equal_p (vp1
->phiargs
[fe1
->dest_idx
],
3039 vp2
->phiargs
[fe2
->dest_idx
]))
3050 /* If the PHI nodes do not have compatible types
3051 they are not the same. */
3052 if (!types_compatible_p (vp1
->type
, vp2
->type
))
3055 /* Any phi in the same block will have it's arguments in the
3056 same edge order, because of how we store phi nodes. */
3059 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
3061 tree phi2op
= vp2
->phiargs
[i
];
3062 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
3064 if (!expressions_equal_p (phi1op
, phi2op
))
3071 static vec
<tree
> shared_lookup_phiargs
;
3073 /* Lookup PHI in the current hash table, and return the resulting
3074 value number if it exists in the hash table. Return NULL_TREE if
3075 it does not exist in the hash table. */
3078 vn_phi_lookup (gimple
*phi
)
3081 struct vn_phi_s vp1
;
3085 shared_lookup_phiargs
.truncate (0);
3086 shared_lookup_phiargs
.safe_grow (gimple_phi_num_args (phi
));
3088 /* Canonicalize the SSA_NAME's to their value number. */
3089 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3091 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3092 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
3093 shared_lookup_phiargs
[e
->dest_idx
] = def
;
3095 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
3096 vp1
.phiargs
= shared_lookup_phiargs
;
3097 vp1
.block
= gimple_bb (phi
);
3098 /* Extract values of the controlling condition. */
3099 vp1
.cclhs
= NULL_TREE
;
3100 vp1
.ccrhs
= NULL_TREE
;
3101 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
.block
);
3102 if (EDGE_COUNT (idom1
->succs
) == 2)
3103 if (gcond
*last1
= dyn_cast
<gcond
*> (last_stmt (idom1
)))
3105 vp1
.cclhs
= vn_valueize (gimple_cond_lhs (last1
));
3106 vp1
.ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
3108 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
3109 slot
= current_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
3111 if (!slot
&& current_info
== optimistic_info
)
3112 slot
= valid_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
3116 return (*slot
)->result
;
3119 /* Insert PHI into the current hash table with a value number of
3123 vn_phi_insert (gimple
*phi
, tree result
)
3126 vn_phi_t vp1
= current_info
->phis_pool
->allocate ();
3127 vec
<tree
> args
= vNULL
;
3131 args
.safe_grow (gimple_phi_num_args (phi
));
3133 /* Canonicalize the SSA_NAME's to their value number. */
3134 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3136 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3137 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
3138 args
[e
->dest_idx
] = def
;
3140 vp1
->value_id
= VN_INFO (result
)->value_id
;
3141 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
3142 vp1
->phiargs
= args
;
3143 vp1
->block
= gimple_bb (phi
);
3144 /* Extract values of the controlling condition. */
3145 vp1
->cclhs
= NULL_TREE
;
3146 vp1
->ccrhs
= NULL_TREE
;
3147 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3148 if (EDGE_COUNT (idom1
->succs
) == 2)
3149 if (gcond
*last1
= dyn_cast
<gcond
*> (last_stmt (idom1
)))
3151 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
3152 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
3154 vp1
->result
= result
;
3155 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
3157 slot
= current_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
3159 /* Because we iterate over phi operations more than once, it's
3160 possible the slot might already exist here, hence no assert.*/
3166 /* Print set of components in strongly connected component SCC to OUT. */
3169 print_scc (FILE *out
, vec
<tree
> scc
)
3174 fprintf (out
, "SCC consists of %u:", scc
.length ());
3175 FOR_EACH_VEC_ELT (scc
, i
, var
)
3178 print_generic_expr (out
, var
);
3180 fprintf (out
, "\n");
3183 /* Return true if BB1 is dominated by BB2 taking into account edges
3184 that are not executable. */
3187 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
)
3192 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3195 /* Before iterating we'd like to know if there exists a
3196 (executable) path from bb2 to bb1 at all, if not we can
3197 directly return false. For now simply iterate once. */
3199 /* Iterate to the single executable bb1 predecessor. */
3200 if (EDGE_COUNT (bb1
->preds
) > 1)
3203 FOR_EACH_EDGE (e
, ei
, bb1
->preds
)
3204 if (e
->flags
& EDGE_EXECUTABLE
)
3217 /* Re-do the dominance check with changed bb1. */
3218 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3223 /* Iterate to the single executable bb2 successor. */
3225 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
3226 if (e
->flags
& EDGE_EXECUTABLE
)
3237 /* Verify the reached block is only reached through succe.
3238 If there is only one edge we can spare us the dominator
3239 check and iterate directly. */
3240 if (EDGE_COUNT (succe
->dest
->preds
) > 1)
3242 FOR_EACH_EDGE (e
, ei
, succe
->dest
->preds
)
3244 && (e
->flags
& EDGE_EXECUTABLE
))
3254 /* Re-do the dominance check with changed bb2. */
3255 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3260 /* We could now iterate updating bb1 / bb2. */
3264 /* Set the value number of FROM to TO, return true if it has changed
3268 set_ssa_val_to (tree from
, tree to
)
3270 tree currval
= SSA_VAL (from
);
3271 HOST_WIDE_INT toff
, coff
;
3273 /* The only thing we allow as value numbers are ssa_names
3274 and invariants. So assert that here. We don't allow VN_TOP
3275 as visiting a stmt should produce a value-number other than
3277 ??? Still VN_TOP can happen for unreachable code, so force
3278 it to varying in that case. Not all code is prepared to
3279 get VN_TOP on valueization. */
3282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3283 fprintf (dump_file
, "Forcing value number to varying on "
3284 "receiving VN_TOP\n");
3288 gcc_assert (to
!= NULL_TREE
3289 && ((TREE_CODE (to
) == SSA_NAME
3290 && (to
== from
|| SSA_VAL (to
) == to
))
3291 || is_gimple_min_invariant (to
)));
3295 if (currval
== from
)
3297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3299 fprintf (dump_file
, "Not changing value number of ");
3300 print_generic_expr (dump_file
, from
);
3301 fprintf (dump_file
, " from VARYING to ");
3302 print_generic_expr (dump_file
, to
);
3303 fprintf (dump_file
, "\n");
3307 else if (currval
!= VN_TOP
3308 && ! is_gimple_min_invariant (currval
)
3309 && is_gimple_min_invariant (to
))
3311 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3313 fprintf (dump_file
, "Forcing VARYING instead of changing "
3314 "value number of ");
3315 print_generic_expr (dump_file
, from
);
3316 fprintf (dump_file
, " from ");
3317 print_generic_expr (dump_file
, currval
);
3318 fprintf (dump_file
, " (non-constant) to ");
3319 print_generic_expr (dump_file
, to
);
3320 fprintf (dump_file
, " (constant)\n");
3324 else if (TREE_CODE (to
) == SSA_NAME
3325 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
3329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3331 fprintf (dump_file
, "Setting value number of ");
3332 print_generic_expr (dump_file
, from
);
3333 fprintf (dump_file
, " to ");
3334 print_generic_expr (dump_file
, to
);
3338 && !operand_equal_p (currval
, to
, 0)
3339 /* ??? For addresses involving volatile objects or types operand_equal_p
3340 does not reliably detect ADDR_EXPRs as equal. We know we are only
3341 getting invariant gimple addresses here, so can use
3342 get_addr_base_and_unit_offset to do this comparison. */
3343 && !(TREE_CODE (currval
) == ADDR_EXPR
3344 && TREE_CODE (to
) == ADDR_EXPR
3345 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
3346 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
3349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3350 fprintf (dump_file
, " (changed)\n");
3352 /* If we equate two SSA names we have to make the side-band info
3353 of the leader conservative (and remember whatever original value
3355 if (TREE_CODE (to
) == SSA_NAME
)
3357 if (INTEGRAL_TYPE_P (TREE_TYPE (to
))
3358 && SSA_NAME_RANGE_INFO (to
))
3360 if (SSA_NAME_IS_DEFAULT_DEF (to
)
3361 || dominated_by_p_w_unex
3362 (gimple_bb (SSA_NAME_DEF_STMT (from
)),
3363 gimple_bb (SSA_NAME_DEF_STMT (to
))))
3364 /* Keep the info from the dominator. */
3368 /* Save old info. */
3369 if (! VN_INFO (to
)->info
.range_info
)
3371 VN_INFO (to
)->info
.range_info
= SSA_NAME_RANGE_INFO (to
);
3372 VN_INFO (to
)->range_info_anti_range_p
3373 = SSA_NAME_ANTI_RANGE_P (to
);
3375 /* Rather than allocating memory and unioning the info
3377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3379 fprintf (dump_file
, "clearing range info of ");
3380 print_generic_expr (dump_file
, to
);
3381 fprintf (dump_file
, "\n");
3383 SSA_NAME_RANGE_INFO (to
) = NULL
;
3386 else if (POINTER_TYPE_P (TREE_TYPE (to
))
3387 && SSA_NAME_PTR_INFO (to
))
3389 if (SSA_NAME_IS_DEFAULT_DEF (to
)
3390 || dominated_by_p_w_unex
3391 (gimple_bb (SSA_NAME_DEF_STMT (from
)),
3392 gimple_bb (SSA_NAME_DEF_STMT (to
))))
3393 /* Keep the info from the dominator. */
3395 else if (! SSA_NAME_PTR_INFO (from
)
3396 /* Handle the case of trivially equivalent info. */
3397 || memcmp (SSA_NAME_PTR_INFO (to
),
3398 SSA_NAME_PTR_INFO (from
),
3399 sizeof (ptr_info_def
)) != 0)
3401 /* Save old info. */
3402 if (! VN_INFO (to
)->info
.ptr_info
)
3403 VN_INFO (to
)->info
.ptr_info
= SSA_NAME_PTR_INFO (to
);
3404 /* Rather than allocating memory and unioning the info
3406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3408 fprintf (dump_file
, "clearing points-to info of ");
3409 print_generic_expr (dump_file
, to
);
3410 fprintf (dump_file
, "\n");
3412 SSA_NAME_PTR_INFO (to
) = NULL
;
3417 VN_INFO (from
)->valnum
= to
;
3420 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3421 fprintf (dump_file
, "\n");
3425 /* Mark as processed all the definitions in the defining stmt of USE, or
3429 mark_use_processed (tree use
)
3433 gimple
*stmt
= SSA_NAME_DEF_STMT (use
);
3435 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
3437 VN_INFO (use
)->use_processed
= true;
3441 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
3443 tree def
= DEF_FROM_PTR (defp
);
3445 VN_INFO (def
)->use_processed
= true;
3449 /* Set all definitions in STMT to value number to themselves.
3450 Return true if a value number changed. */
3453 defs_to_varying (gimple
*stmt
)
3455 bool changed
= false;
3459 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
3461 tree def
= DEF_FROM_PTR (defp
);
3462 changed
|= set_ssa_val_to (def
, def
);
3467 /* Visit a copy between LHS and RHS, return true if the value number
3471 visit_copy (tree lhs
, tree rhs
)
3474 rhs
= SSA_VAL (rhs
);
3476 return set_ssa_val_to (lhs
, rhs
);
3479 /* Lookup a value for OP in type WIDE_TYPE where the value in type of OP
3483 valueized_wider_op (tree wide_type
, tree op
)
3485 if (TREE_CODE (op
) == SSA_NAME
)
3488 /* Either we have the op widened available. */
3491 tree tem
= vn_nary_op_lookup_pieces (1, NOP_EXPR
,
3492 wide_type
, ops
, NULL
);
3496 /* Or the op is truncated from some existing value. */
3497 if (TREE_CODE (op
) == SSA_NAME
)
3499 gimple
*def
= SSA_NAME_DEF_STMT (op
);
3500 if (is_gimple_assign (def
)
3501 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def
)))
3503 tem
= gimple_assign_rhs1 (def
);
3504 if (useless_type_conversion_p (wide_type
, TREE_TYPE (tem
)))
3506 if (TREE_CODE (tem
) == SSA_NAME
)
3507 tem
= SSA_VAL (tem
);
3513 /* For constants simply extend it. */
3514 if (TREE_CODE (op
) == INTEGER_CST
)
3515 return wide_int_to_tree (wide_type
, op
);
3520 /* Visit a nary operator RHS, value number it, and return true if the
3521 value number of LHS has changed as a result. */
3524 visit_nary_op (tree lhs
, gassign
*stmt
)
3526 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
3528 return set_ssa_val_to (lhs
, result
);
3530 /* Do some special pattern matching for redundancies of operations
3531 in different types. */
3532 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3533 tree type
= TREE_TYPE (lhs
);
3534 tree rhs1
= gimple_assign_rhs1 (stmt
);
3538 /* Match arithmetic done in a different type where we can easily
3539 substitute the result from some earlier sign-changed or widened
3541 if (INTEGRAL_TYPE_P (type
)
3542 && TREE_CODE (rhs1
) == SSA_NAME
3543 /* We only handle sign-changes or zero-extension -> & mask. */
3544 && ((TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3545 && TYPE_PRECISION (type
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
3546 || TYPE_PRECISION (type
) == TYPE_PRECISION (TREE_TYPE (rhs1
))))
3548 gassign
*def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (rhs1
));
3550 && (gimple_assign_rhs_code (def
) == PLUS_EXPR
3551 || gimple_assign_rhs_code (def
) == MINUS_EXPR
3552 || gimple_assign_rhs_code (def
) == MULT_EXPR
))
3555 /* Either we have the op widened available. */
3556 ops
[0] = valueized_wider_op (type
,
3557 gimple_assign_rhs1 (def
));
3559 ops
[1] = valueized_wider_op (type
,
3560 gimple_assign_rhs2 (def
));
3561 if (ops
[0] && ops
[1])
3563 ops
[0] = vn_nary_op_lookup_pieces
3564 (2, gimple_assign_rhs_code (def
), type
, ops
, NULL
);
3565 /* We have wider operation available. */
3568 unsigned lhs_prec
= TYPE_PRECISION (type
);
3569 unsigned rhs_prec
= TYPE_PRECISION (TREE_TYPE (rhs1
));
3570 if (lhs_prec
== rhs_prec
)
3573 result
= vn_nary_build_or_lookup (NOP_EXPR
,
3577 bool changed
= set_ssa_val_to (lhs
, result
);
3578 vn_nary_op_insert_stmt (stmt
, result
);
3584 ops
[1] = wide_int_to_tree (type
,
3585 wi::mask (rhs_prec
, false,
3587 result
= vn_nary_build_or_lookup (BIT_AND_EXPR
,
3592 bool changed
= set_ssa_val_to (lhs
, result
);
3593 vn_nary_op_insert_stmt (stmt
, result
);
3604 bool changed
= set_ssa_val_to (lhs
, lhs
);
3605 vn_nary_op_insert_stmt (stmt
, lhs
);
3609 /* Visit a call STMT storing into LHS. Return true if the value number
3610 of the LHS has changed as a result. */
3613 visit_reference_op_call (tree lhs
, gcall
*stmt
)
3615 bool changed
= false;
3616 struct vn_reference_s vr1
;
3617 vn_reference_t vnresult
= NULL
;
3618 tree vdef
= gimple_vdef (stmt
);
3620 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
3621 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
3624 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
3627 if (vnresult
->result_vdef
&& vdef
)
3628 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3630 /* If the call was discovered to be pure or const reflect
3631 that as far as possible. */
3632 changed
|= set_ssa_val_to (vdef
, vuse_ssa_val (gimple_vuse (stmt
)));
3634 if (!vnresult
->result
&& lhs
)
3635 vnresult
->result
= lhs
;
3637 if (vnresult
->result
&& lhs
)
3638 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
3643 vn_reference_s
**slot
;
3644 tree vdef_val
= vdef
;
3647 /* If we value numbered an indirect functions function to
3648 one not clobbering memory value number its VDEF to its
3650 tree fn
= gimple_call_fn (stmt
);
3651 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
3654 if (TREE_CODE (fn
) == ADDR_EXPR
3655 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
3656 && (flags_from_decl_or_type (TREE_OPERAND (fn
, 0))
3657 & (ECF_CONST
| ECF_PURE
)))
3658 vdef_val
= vuse_ssa_val (gimple_vuse (stmt
));
3660 changed
|= set_ssa_val_to (vdef
, vdef_val
);
3663 changed
|= set_ssa_val_to (lhs
, lhs
);
3664 vr2
= current_info
->references_pool
->allocate ();
3665 vr2
->vuse
= vr1
.vuse
;
3666 /* As we are not walking the virtual operand chain we know the
3667 shared_lookup_references are still original so we can re-use
3669 vr2
->operands
= vr1
.operands
.copy ();
3670 vr2
->type
= vr1
.type
;
3672 vr2
->hashcode
= vr1
.hashcode
;
3674 vr2
->result_vdef
= vdef_val
;
3675 slot
= current_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
3677 gcc_assert (!*slot
);
3684 /* Visit a load from a reference operator RHS, part of STMT, value number it,
3685 and return true if the value number of the LHS has changed as a result. */
3688 visit_reference_op_load (tree lhs
, tree op
, gimple
*stmt
)
3690 bool changed
= false;
3694 last_vuse
= gimple_vuse (stmt
);
3695 last_vuse_ptr
= &last_vuse
;
3696 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
3697 default_vn_walk_kind
, NULL
, true);
3698 last_vuse_ptr
= NULL
;
3700 /* We handle type-punning through unions by value-numbering based
3701 on offset and size of the access. Be prepared to handle a
3702 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
3704 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
3706 /* We will be setting the value number of lhs to the value number
3707 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
3708 So first simplify and lookup this expression to see if it
3709 is already available. */
3710 code_helper rcode
= VIEW_CONVERT_EXPR
;
3711 tree ops
[3] = { result
};
3712 result
= vn_nary_build_or_lookup (rcode
, TREE_TYPE (op
), ops
);
3716 changed
= set_ssa_val_to (lhs
, result
);
3719 changed
= set_ssa_val_to (lhs
, lhs
);
3720 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
3727 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3728 and return true if the value number of the LHS has changed as a result. */
3731 visit_reference_op_store (tree lhs
, tree op
, gimple
*stmt
)
3733 bool changed
= false;
3734 vn_reference_t vnresult
= NULL
;
3736 bool resultsame
= false;
3737 tree vuse
= gimple_vuse (stmt
);
3738 tree vdef
= gimple_vdef (stmt
);
3740 if (TREE_CODE (op
) == SSA_NAME
)
3743 /* First we want to lookup using the *vuses* from the store and see
3744 if there the last store to this location with the same address
3747 The vuses represent the memory state before the store. If the
3748 memory state, address, and value of the store is the same as the
3749 last store to this location, then this store will produce the
3750 same memory state as that store.
3752 In this case the vdef versions for this store are value numbered to those
3753 vuse versions, since they represent the same memory state after
3756 Otherwise, the vdefs for the store are used when inserting into
3757 the table, since the store generates a new memory state. */
3759 vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, &vnresult
, false);
3761 && vnresult
->result
)
3763 tree result
= vnresult
->result
;
3764 if (TREE_CODE (result
) == SSA_NAME
)
3765 result
= SSA_VAL (result
);
3766 resultsame
= expressions_equal_p (result
, op
);
3769 /* If the TBAA state isn't compatible for downstream reads
3770 we cannot value-number the VDEFs the same. */
3771 alias_set_type set
= get_alias_set (lhs
);
3772 if (vnresult
->set
!= set
3773 && ! alias_set_subset_of (set
, vnresult
->set
))
3780 /* Only perform the following when being called from PRE
3781 which embeds tail merging. */
3782 if (default_vn_walk_kind
== VN_WALK
)
3784 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3785 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
, false);
3788 VN_INFO (vdef
)->use_processed
= true;
3789 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3795 fprintf (dump_file
, "No store match\n");
3796 fprintf (dump_file
, "Value numbering store ");
3797 print_generic_expr (dump_file
, lhs
);
3798 fprintf (dump_file
, " to ");
3799 print_generic_expr (dump_file
, op
);
3800 fprintf (dump_file
, "\n");
3802 /* Have to set value numbers before insert, since insert is
3803 going to valueize the references in-place. */
3805 changed
|= set_ssa_val_to (vdef
, vdef
);
3807 /* Do not insert structure copies into the tables. */
3808 if (is_gimple_min_invariant (op
)
3809 || is_gimple_reg (op
))
3810 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3812 /* Only perform the following when being called from PRE
3813 which embeds tail merging. */
3814 if (default_vn_walk_kind
== VN_WALK
)
3816 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3817 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3822 /* We had a match, so value number the vdef to have the value
3823 number of the vuse it came from. */
3825 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3826 fprintf (dump_file
, "Store matched earlier value, "
3827 "value numbering store vdefs to matching vuses.\n");
3829 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3835 /* Visit and value number PHI, return true if the value number
3839 visit_phi (gimple
*phi
)
3841 bool changed
= false;
3843 tree sameval
= VN_TOP
;
3844 bool allsame
= true;
3845 unsigned n_executable
= 0;
3847 /* TODO: We could check for this in init_sccvn, and replace this
3848 with a gcc_assert. */
3849 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3850 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3852 /* See if all non-TOP arguments have the same value. TOP is
3853 equivalent to everything, so we can ignore it. */
3856 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3857 if (e
->flags
& EDGE_EXECUTABLE
)
3859 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3862 if (TREE_CODE (def
) == SSA_NAME
)
3863 def
= SSA_VAL (def
);
3866 if (sameval
== VN_TOP
)
3868 else if (!expressions_equal_p (def
, sameval
))
3875 /* If none of the edges was executable or all incoming values are
3876 undefined keep the value-number at VN_TOP. If only a single edge
3877 is exectuable use its value. */
3878 if (sameval
== VN_TOP
3879 || n_executable
== 1)
3880 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3882 /* First see if it is equivalent to a phi node in this block. We prefer
3883 this as it allows IV elimination - see PRs 66502 and 67167. */
3884 result
= vn_phi_lookup (phi
);
3886 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3887 /* Otherwise all value numbered to the same value, the phi node has that
3890 changed
= set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3893 vn_phi_insert (phi
, PHI_RESULT (phi
));
3894 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3900 /* Try to simplify RHS using equivalences and constant folding. */
3903 try_to_simplify (gassign
*stmt
)
3905 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3908 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3909 in this case, there is no point in doing extra work. */
3910 if (code
== SSA_NAME
)
3913 /* First try constant folding based on our current lattice. */
3914 mprts_hook
= vn_lookup_simplify_result
;
3916 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
, vn_valueize
);
3919 && (TREE_CODE (tem
) == SSA_NAME
3920 || is_gimple_min_invariant (tem
)))
3926 /* Visit and value number USE, return true if the value number
3930 visit_use (tree use
)
3932 bool changed
= false;
3933 gimple
*stmt
= SSA_NAME_DEF_STMT (use
);
3935 mark_use_processed (use
);
3937 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3938 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3939 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3941 fprintf (dump_file
, "Value numbering ");
3942 print_generic_expr (dump_file
, use
);
3943 fprintf (dump_file
, " stmt = ");
3944 print_gimple_stmt (dump_file
, stmt
, 0);
3947 /* Handle uninitialized uses. */
3948 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3949 changed
= set_ssa_val_to (use
, use
);
3950 else if (gimple_code (stmt
) == GIMPLE_PHI
)
3951 changed
= visit_phi (stmt
);
3952 else if (gimple_has_volatile_ops (stmt
))
3953 changed
= defs_to_varying (stmt
);
3954 else if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
3956 enum tree_code code
= gimple_assign_rhs_code (ass
);
3957 tree lhs
= gimple_assign_lhs (ass
);
3958 tree rhs1
= gimple_assign_rhs1 (ass
);
3961 /* Shortcut for copies. Simplifying copies is pointless,
3962 since we copy the expression and value they represent. */
3963 if (code
== SSA_NAME
3964 && TREE_CODE (lhs
) == SSA_NAME
)
3966 changed
= visit_copy (lhs
, rhs1
);
3969 simplified
= try_to_simplify (ass
);
3972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3974 fprintf (dump_file
, "RHS ");
3975 print_gimple_expr (dump_file
, ass
, 0);
3976 fprintf (dump_file
, " simplified to ");
3977 print_generic_expr (dump_file
, simplified
);
3978 fprintf (dump_file
, "\n");
3981 /* Setting value numbers to constants will occasionally
3982 screw up phi congruence because constants are not
3983 uniquely associated with a single ssa name that can be
3986 && is_gimple_min_invariant (simplified
)
3987 && TREE_CODE (lhs
) == SSA_NAME
)
3989 changed
= set_ssa_val_to (lhs
, simplified
);
3993 && TREE_CODE (simplified
) == SSA_NAME
3994 && TREE_CODE (lhs
) == SSA_NAME
)
3996 changed
= visit_copy (lhs
, simplified
);
4000 if ((TREE_CODE (lhs
) == SSA_NAME
4001 /* We can substitute SSA_NAMEs that are live over
4002 abnormal edges with their constant value. */
4003 && !(gimple_assign_copy_p (ass
)
4004 && is_gimple_min_invariant (rhs1
))
4006 && is_gimple_min_invariant (simplified
))
4007 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
4008 /* Stores or copies from SSA_NAMEs that are live over
4009 abnormal edges are a problem. */
4010 || (code
== SSA_NAME
4011 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
4012 changed
= defs_to_varying (ass
);
4013 else if (REFERENCE_CLASS_P (lhs
)
4015 changed
= visit_reference_op_store (lhs
, rhs1
, ass
);
4016 else if (TREE_CODE (lhs
) == SSA_NAME
)
4018 if ((gimple_assign_copy_p (ass
)
4019 && is_gimple_min_invariant (rhs1
))
4021 && is_gimple_min_invariant (simplified
)))
4024 changed
= set_ssa_val_to (lhs
, simplified
);
4026 changed
= set_ssa_val_to (lhs
, rhs1
);
4030 /* Visit the original statement. */
4031 switch (vn_get_stmt_kind (ass
))
4034 changed
= visit_nary_op (lhs
, ass
);
4037 changed
= visit_reference_op_load (lhs
, rhs1
, ass
);
4040 changed
= defs_to_varying (ass
);
4046 changed
= defs_to_varying (ass
);
4048 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
4050 tree lhs
= gimple_call_lhs (call_stmt
);
4051 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
4053 /* Try constant folding based on our current lattice. */
4054 tree simplified
= gimple_fold_stmt_to_constant_1 (call_stmt
,
4058 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4060 fprintf (dump_file
, "call ");
4061 print_gimple_expr (dump_file
, call_stmt
, 0);
4062 fprintf (dump_file
, " simplified to ");
4063 print_generic_expr (dump_file
, simplified
);
4064 fprintf (dump_file
, "\n");
4067 /* Setting value numbers to constants will occasionally
4068 screw up phi congruence because constants are not
4069 uniquely associated with a single ssa name that can be
4072 && is_gimple_min_invariant (simplified
))
4074 changed
= set_ssa_val_to (lhs
, simplified
);
4075 if (gimple_vdef (call_stmt
))
4076 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
4077 SSA_VAL (gimple_vuse (call_stmt
)));
4081 && TREE_CODE (simplified
) == SSA_NAME
)
4083 changed
= visit_copy (lhs
, simplified
);
4084 if (gimple_vdef (call_stmt
))
4085 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
4086 SSA_VAL (gimple_vuse (call_stmt
)));
4089 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
4091 changed
= defs_to_varying (call_stmt
);
4096 /* Pick up flags from a devirtualization target. */
4097 tree fn
= gimple_call_fn (stmt
);
4098 int extra_fnflags
= 0;
4099 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
4102 if (TREE_CODE (fn
) == ADDR_EXPR
4103 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
)
4104 extra_fnflags
= flags_from_decl_or_type (TREE_OPERAND (fn
, 0));
4106 if (!gimple_call_internal_p (call_stmt
)
4107 && (/* Calls to the same function with the same vuse
4108 and the same operands do not necessarily return the same
4109 value, unless they're pure or const. */
4110 ((gimple_call_flags (call_stmt
) | extra_fnflags
)
4111 & (ECF_PURE
| ECF_CONST
))
4112 /* If calls have a vdef, subsequent calls won't have
4113 the same incoming vuse. So, if 2 calls with vdef have the
4114 same vuse, we know they're not subsequent.
4115 We can value number 2 calls to the same function with the
4116 same vuse and the same operands which are not subsequent
4117 the same, because there is no code in the program that can
4118 compare the 2 values... */
4119 || (gimple_vdef (call_stmt
)
4120 /* ... unless the call returns a pointer which does
4121 not alias with anything else. In which case the
4122 information that the values are distinct are encoded
4124 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
4125 /* Only perform the following when being called from PRE
4126 which embeds tail merging. */
4127 && default_vn_walk_kind
== VN_WALK
)))
4128 changed
= visit_reference_op_call (lhs
, call_stmt
);
4130 changed
= defs_to_varying (call_stmt
);
4133 changed
= defs_to_varying (stmt
);
4138 /* Compare two operands by reverse postorder index */
4141 compare_ops (const void *pa
, const void *pb
)
4143 const tree opa
= *((const tree
*)pa
);
4144 const tree opb
= *((const tree
*)pb
);
4145 gimple
*opstmta
= SSA_NAME_DEF_STMT (opa
);
4146 gimple
*opstmtb
= SSA_NAME_DEF_STMT (opb
);
4150 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
4151 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
4152 else if (gimple_nop_p (opstmta
))
4154 else if (gimple_nop_p (opstmtb
))
4157 bba
= gimple_bb (opstmta
);
4158 bbb
= gimple_bb (opstmtb
);
4161 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
4169 if (gimple_code (opstmta
) == GIMPLE_PHI
4170 && gimple_code (opstmtb
) == GIMPLE_PHI
)
4171 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
4172 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
4174 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
4176 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
4177 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
4179 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
4181 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
4184 /* Sort an array containing members of a strongly connected component
4185 SCC so that the members are ordered by RPO number.
4186 This means that when the sort is complete, iterating through the
4187 array will give you the members in RPO order. */
4190 sort_scc (vec
<tree
> scc
)
4192 scc
.qsort (compare_ops
);
4195 /* Insert the no longer used nary ONARY to the hash INFO. */
4198 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
4200 size_t size
= sizeof_vn_nary_op (onary
->length
);
4201 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
4202 &info
->nary_obstack
);
4203 memcpy (nary
, onary
, size
);
4204 vn_nary_op_insert_into (nary
, info
->nary
, false);
4207 /* Insert the no longer used phi OPHI to the hash INFO. */
4210 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
4212 vn_phi_t phi
= info
->phis_pool
->allocate ();
4214 memcpy (phi
, ophi
, sizeof (*phi
));
4215 ophi
->phiargs
.create (0);
4216 slot
= info
->phis
->find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
4217 gcc_assert (!*slot
);
4221 /* Insert the no longer used reference OREF to the hash INFO. */
4224 copy_reference (vn_reference_t oref
, vn_tables_t info
)
4227 vn_reference_s
**slot
;
4228 ref
= info
->references_pool
->allocate ();
4229 memcpy (ref
, oref
, sizeof (*ref
));
4230 oref
->operands
.create (0);
4231 slot
= info
->references
->find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
4233 free_reference (*slot
);
4237 /* Process a strongly connected component in the SSA graph. */
4240 process_scc (vec
<tree
> scc
)
4244 unsigned int iterations
= 0;
4245 bool changed
= true;
4246 vn_nary_op_iterator_type hin
;
4247 vn_phi_iterator_type hip
;
4248 vn_reference_iterator_type hir
;
4253 /* If the SCC has a single member, just visit it. */
4254 if (scc
.length () == 1)
4257 if (VN_INFO (use
)->use_processed
)
4259 /* We need to make sure it doesn't form a cycle itself, which can
4260 happen for self-referential PHI nodes. In that case we would
4261 end up inserting an expression with VN_TOP operands into the
4262 valid table which makes us derive bogus equivalences later.
4263 The cheapest way to check this is to assume it for all PHI nodes. */
4264 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
4265 /* Fallthru to iteration. */ ;
4273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4274 print_scc (dump_file
, scc
);
4276 /* Iterate over the SCC with the optimistic table until it stops
4278 current_info
= optimistic_info
;
4283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4284 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
4285 /* As we are value-numbering optimistically we have to
4286 clear the expression tables and the simplified expressions
4287 in each iteration until we converge. */
4288 optimistic_info
->nary
->empty ();
4289 optimistic_info
->phis
->empty ();
4290 optimistic_info
->references
->empty ();
4291 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
4292 gcc_obstack_init (&optimistic_info
->nary_obstack
);
4293 optimistic_info
->phis_pool
->release ();
4294 optimistic_info
->references_pool
->release ();
4295 FOR_EACH_VEC_ELT (scc
, i
, var
)
4296 gcc_assert (!VN_INFO (var
)->needs_insertion
4297 && VN_INFO (var
)->expr
== NULL
);
4298 FOR_EACH_VEC_ELT (scc
, i
, var
)
4299 changed
|= visit_use (var
);
4302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4303 fprintf (dump_file
, "Processing SCC needed %d iterations\n", iterations
);
4304 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
4306 /* Finally, copy the contents of the no longer used optimistic
4307 table to the valid table. */
4308 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
4309 copy_nary (nary
, valid_info
);
4310 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
4311 copy_phi (phi
, valid_info
);
4312 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->references
,
4313 ref
, vn_reference_t
, hir
)
4314 copy_reference (ref
, valid_info
);
4316 current_info
= valid_info
;
4320 /* Pop the components of the found SCC for NAME off the SCC stack
4321 and process them. Returns true if all went well, false if
4322 we run into resource limits. */
4325 extract_and_process_scc_for_name (tree name
)
4330 /* Found an SCC, pop the components off the SCC stack and
4334 x
= sccstack
.pop ();
4336 VN_INFO (x
)->on_sccstack
= false;
4338 } while (x
!= name
);
4340 /* Drop all defs in the SCC to varying in case a SCC turns out to be
4342 ??? Just switch to a non-optimistic mode that avoids any iteration. */
4343 if (scc
.length () > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
4347 print_scc (dump_file
, scc
);
4348 fprintf (dump_file
, "WARNING: Giving up value-numbering SCC due to "
4349 "size %u exceeding %u\n", scc
.length (),
4350 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
4354 FOR_EACH_VEC_ELT (scc
, i
, var
)
4356 gimple
*def
= SSA_NAME_DEF_STMT (var
);
4357 mark_use_processed (var
);
4358 if (SSA_NAME_IS_DEFAULT_DEF (var
)
4359 || gimple_code (def
) == GIMPLE_PHI
)
4360 set_ssa_val_to (var
, var
);
4362 defs_to_varying (def
);
4367 if (scc
.length () > 1)
4373 /* Depth first search on NAME to discover and process SCC's in the SSA
4375 Execution of this algorithm relies on the fact that the SCC's are
4376 popped off the stack in topological order.
4377 Returns true if successful, false if we stopped processing SCC's due
4378 to resource constraints. */
4383 auto_vec
<ssa_op_iter
> itervec
;
4384 auto_vec
<tree
> namevec
;
4385 use_operand_p usep
= NULL
;
4392 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
4393 VN_INFO (name
)->visited
= true;
4394 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
4396 sccstack
.safe_push (name
);
4397 VN_INFO (name
)->on_sccstack
= true;
4398 defstmt
= SSA_NAME_DEF_STMT (name
);
4400 /* Recursively DFS on our operands, looking for SCC's. */
4401 if (!gimple_nop_p (defstmt
))
4403 /* Push a new iterator. */
4404 if (gphi
*phi
= dyn_cast
<gphi
*> (defstmt
))
4405 usep
= op_iter_init_phiuse (&iter
, phi
, SSA_OP_ALL_USES
);
4407 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
4410 clear_and_done_ssa_iter (&iter
);
4414 /* If we are done processing uses of a name, go up the stack
4415 of iterators and process SCCs as we found them. */
4416 if (op_iter_done (&iter
))
4418 /* See if we found an SCC. */
4419 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
4420 extract_and_process_scc_for_name (name
);
4422 /* Check if we are done. */
4423 if (namevec
.is_empty ())
4426 /* Restore the last use walker and continue walking there. */
4428 name
= namevec
.pop ();
4429 memcpy (&iter
, &itervec
.last (),
4430 sizeof (ssa_op_iter
));
4432 goto continue_walking
;
4435 use
= USE_FROM_PTR (usep
);
4437 /* Since we handle phi nodes, we will sometimes get
4438 invariants in the use expression. */
4439 if (TREE_CODE (use
) == SSA_NAME
)
4441 if (! (VN_INFO (use
)->visited
))
4443 /* Recurse by pushing the current use walking state on
4444 the stack and starting over. */
4445 itervec
.safe_push (iter
);
4446 namevec
.safe_push (name
);
4451 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
4452 VN_INFO (use
)->low
);
4454 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
4455 && VN_INFO (use
)->on_sccstack
)
4457 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
4458 VN_INFO (name
)->low
);
4462 usep
= op_iter_next_use (&iter
);
4466 /* Allocate a value number table. */
4469 allocate_vn_table (vn_tables_t table
)
4471 table
->phis
= new vn_phi_table_type (23);
4472 table
->nary
= new vn_nary_op_table_type (23);
4473 table
->references
= new vn_reference_table_type (23);
4475 gcc_obstack_init (&table
->nary_obstack
);
4476 table
->phis_pool
= new object_allocator
<vn_phi_s
> ("VN phis");
4477 table
->references_pool
= new object_allocator
<vn_reference_s
>
4481 /* Free a value number table. */
4484 free_vn_table (vn_tables_t table
)
4490 delete table
->references
;
4491 table
->references
= NULL
;
4492 obstack_free (&table
->nary_obstack
, NULL
);
4493 delete table
->phis_pool
;
4494 delete table
->references_pool
;
4501 int *rpo_numbers_temp
;
4503 calculate_dominance_info (CDI_DOMINATORS
);
4504 mark_dfs_back_edges ();
4506 sccstack
.create (0);
4507 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
4509 constant_value_ids
= BITMAP_ALLOC (NULL
);
4514 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
4515 /* VEC_alloc doesn't actually grow it to the right size, it just
4516 preallocates the space to do so. */
4517 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
4518 gcc_obstack_init (&vn_ssa_aux_obstack
);
4520 shared_lookup_phiargs
.create (0);
4521 shared_lookup_references
.create (0);
4522 rpo_numbers
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
4524 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
4525 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
4527 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4528 the i'th block in RPO order is bb. We want to map bb's to RPO
4529 numbers, so we need to rearrange this array. */
4530 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
4531 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
4533 XDELETE (rpo_numbers_temp
);
4535 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
4537 renumber_gimple_stmt_uids ();
4539 /* Create the valid and optimistic value numbering tables. */
4540 valid_info
= XCNEW (struct vn_tables_s
);
4541 allocate_vn_table (valid_info
);
4542 optimistic_info
= XCNEW (struct vn_tables_s
);
4543 allocate_vn_table (optimistic_info
);
4544 current_info
= valid_info
;
4546 /* Create the VN_INFO structures, and initialize value numbers to
4547 TOP or VARYING for parameters. */
4551 FOR_EACH_SSA_NAME (i
, name
, cfun
)
4553 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4554 VN_INFO (name
)->needs_insertion
= false;
4555 VN_INFO (name
)->expr
= NULL
;
4556 VN_INFO (name
)->value_id
= 0;
4558 if (!SSA_NAME_IS_DEFAULT_DEF (name
))
4561 switch (TREE_CODE (SSA_NAME_VAR (name
)))
4564 /* Undefined vars keep TOP. */
4568 /* Parameters are VARYING but we can record a condition
4569 if we know it is a non-NULL pointer. */
4570 VN_INFO (name
)->visited
= true;
4571 VN_INFO (name
)->valnum
= name
;
4572 if (POINTER_TYPE_P (TREE_TYPE (name
))
4573 && nonnull_arg_p (SSA_NAME_VAR (name
)))
4577 ops
[1] = build_int_cst (TREE_TYPE (name
), 0);
4578 vn_nary_op_insert_pieces (2, NE_EXPR
, boolean_type_node
, ops
,
4579 boolean_true_node
, 0);
4580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4582 fprintf (dump_file
, "Recording ");
4583 print_generic_expr (dump_file
, name
, TDF_SLIM
);
4584 fprintf (dump_file
, " != 0\n");
4590 /* If the result is passed by invisible reference the default
4591 def is initialized, otherwise it's uninitialized. */
4592 if (DECL_BY_REFERENCE (SSA_NAME_VAR (name
)))
4594 VN_INFO (name
)->visited
= true;
4595 VN_INFO (name
)->valnum
= name
;
4605 /* Restore SSA info that has been reset on value leaders. */
4608 scc_vn_restore_ssa_info (void)
4613 FOR_EACH_SSA_NAME (i
, name
, cfun
)
4615 if (has_VN_INFO (name
))
4617 if (VN_INFO (name
)->needs_insertion
)
4619 else if (POINTER_TYPE_P (TREE_TYPE (name
))
4620 && VN_INFO (name
)->info
.ptr_info
)
4621 SSA_NAME_PTR_INFO (name
) = VN_INFO (name
)->info
.ptr_info
;
4622 else if (INTEGRAL_TYPE_P (TREE_TYPE (name
))
4623 && VN_INFO (name
)->info
.range_info
)
4625 SSA_NAME_RANGE_INFO (name
) = VN_INFO (name
)->info
.range_info
;
4626 SSA_NAME_ANTI_RANGE_P (name
)
4627 = VN_INFO (name
)->range_info_anti_range_p
;
4639 delete constant_to_value_id
;
4640 constant_to_value_id
= NULL
;
4641 BITMAP_FREE (constant_value_ids
);
4642 shared_lookup_phiargs
.release ();
4643 shared_lookup_references
.release ();
4644 XDELETEVEC (rpo_numbers
);
4646 FOR_EACH_SSA_NAME (i
, name
, cfun
)
4648 if (has_VN_INFO (name
)
4649 && VN_INFO (name
)->needs_insertion
)
4650 release_ssa_name (name
);
4652 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4653 vn_ssa_aux_table
.release ();
4655 sccstack
.release ();
4656 free_vn_table (valid_info
);
4657 XDELETE (valid_info
);
4658 free_vn_table (optimistic_info
);
4659 XDELETE (optimistic_info
);
4661 BITMAP_FREE (const_parms
);
4664 /* Set *ID according to RESULT. */
4667 set_value_id_for_result (tree result
, unsigned int *id
)
4669 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4670 *id
= VN_INFO (result
)->value_id
;
4671 else if (result
&& is_gimple_min_invariant (result
))
4672 *id
= get_or_alloc_constant_value_id (result
);
4674 *id
= get_next_value_id ();
4677 /* Set the value ids in the valid hash tables. */
4680 set_hashtable_value_ids (void)
4682 vn_nary_op_iterator_type hin
;
4683 vn_phi_iterator_type hip
;
4684 vn_reference_iterator_type hir
;
4689 /* Now set the value ids of the things we had put in the hash
4692 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4693 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4695 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4696 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4698 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4700 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4703 class sccvn_dom_walker
: public dom_walker
4707 : dom_walker (CDI_DOMINATORS
, true), cond_stack (0) {}
4709 virtual edge
before_dom_children (basic_block
);
4710 virtual void after_dom_children (basic_block
);
4712 void record_cond (basic_block
,
4713 enum tree_code code
, tree lhs
, tree rhs
, bool value
);
4714 void record_conds (basic_block
,
4715 enum tree_code code
, tree lhs
, tree rhs
, bool value
);
4717 auto_vec
<std::pair
<basic_block
, std::pair
<vn_nary_op_t
, vn_nary_op_t
> > >
4721 /* Record a temporary condition for the BB and its dominated blocks. */
4724 sccvn_dom_walker::record_cond (basic_block bb
,
4725 enum tree_code code
, tree lhs
, tree rhs
,
4728 tree ops
[2] = { lhs
, rhs
};
4729 vn_nary_op_t old
= NULL
;
4730 if (vn_nary_op_lookup_pieces (2, code
, boolean_type_node
, ops
, &old
))
4731 current_info
->nary
->remove_elt_with_hash (old
, old
->hashcode
);
4733 = vn_nary_op_insert_pieces (2, code
, boolean_type_node
, ops
,
4736 : boolean_false_node
, 0);
4737 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4739 fprintf (dump_file
, "Recording temporarily ");
4740 print_generic_expr (dump_file
, ops
[0], TDF_SLIM
);
4741 fprintf (dump_file
, " %s ", get_tree_code_name (code
));
4742 print_generic_expr (dump_file
, ops
[1], TDF_SLIM
);
4743 fprintf (dump_file
, " == %s%s\n",
4744 value
? "true" : "false",
4745 old
? " (old entry saved)" : "");
4747 cond_stack
.safe_push (std::make_pair (bb
, std::make_pair (cond
, old
)));
4750 /* Record temporary conditions for the BB and its dominated blocks
4751 according to LHS CODE RHS == VALUE and its dominated conditions. */
4754 sccvn_dom_walker::record_conds (basic_block bb
,
4755 enum tree_code code
, tree lhs
, tree rhs
,
4758 /* Record the original condition. */
4759 record_cond (bb
, code
, lhs
, rhs
, value
);
4764 /* Record dominated conditions if the condition is true. Note that
4765 the inversion is already recorded. */
4770 record_cond (bb
, code
== LT_EXPR
? LE_EXPR
: GE_EXPR
, lhs
, rhs
, true);
4771 record_cond (bb
, NE_EXPR
, lhs
, rhs
, true);
4772 record_cond (bb
, EQ_EXPR
, lhs
, rhs
, false);
4776 record_cond (bb
, LE_EXPR
, lhs
, rhs
, true);
4777 record_cond (bb
, GE_EXPR
, lhs
, rhs
, true);
4778 record_cond (bb
, LT_EXPR
, lhs
, rhs
, false);
4779 record_cond (bb
, GT_EXPR
, lhs
, rhs
, false);
4787 /* Restore expressions and values derived from conditionals. */
4790 sccvn_dom_walker::after_dom_children (basic_block bb
)
4792 while (!cond_stack
.is_empty ()
4793 && cond_stack
.last ().first
== bb
)
4795 vn_nary_op_t cond
= cond_stack
.last ().second
.first
;
4796 vn_nary_op_t old
= cond_stack
.last ().second
.second
;
4797 current_info
->nary
->remove_elt_with_hash (cond
, cond
->hashcode
);
4799 vn_nary_op_insert_into (old
, current_info
->nary
, false);
4804 /* Value number all statements in BB. */
4807 sccvn_dom_walker::before_dom_children (basic_block bb
)
4812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4813 fprintf (dump_file
, "Visiting BB %d\n", bb
->index
);
4815 /* If we have a single predecessor record the equivalence from a
4816 possible condition on the predecessor edge. */
4818 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4820 /* Ignore simple backedges from this to allow recording conditions
4822 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
4834 /* Check if there are multiple executable successor edges in
4835 the source block. Otherwise there is no additional info
4838 FOR_EACH_EDGE (e2
, ei
, pred_e
->src
->succs
)
4840 && e2
->flags
& EDGE_EXECUTABLE
)
4842 if (e2
&& (e2
->flags
& EDGE_EXECUTABLE
))
4844 gimple
*stmt
= last_stmt (pred_e
->src
);
4846 && gimple_code (stmt
) == GIMPLE_COND
)
4848 enum tree_code code
= gimple_cond_code (stmt
);
4849 tree lhs
= gimple_cond_lhs (stmt
);
4850 tree rhs
= gimple_cond_rhs (stmt
);
4851 record_conds (bb
, code
, lhs
, rhs
,
4852 (pred_e
->flags
& EDGE_TRUE_VALUE
) != 0);
4853 code
= invert_tree_comparison (code
, HONOR_NANS (lhs
));
4854 if (code
!= ERROR_MARK
)
4855 record_conds (bb
, code
, lhs
, rhs
,
4856 (pred_e
->flags
& EDGE_TRUE_VALUE
) == 0);
4861 /* Value-number all defs in the basic-block. */
4862 for (gphi_iterator gsi
= gsi_start_phis (bb
);
4863 !gsi_end_p (gsi
); gsi_next (&gsi
))
4865 gphi
*phi
= gsi
.phi ();
4866 tree res
= PHI_RESULT (phi
);
4867 if (!VN_INFO (res
)->visited
)
4870 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
4871 !gsi_end_p (gsi
); gsi_next (&gsi
))
4875 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_ALL_DEFS
)
4876 if (!VN_INFO (op
)->visited
)
4880 /* Finally look at the last stmt. */
4881 gimple
*stmt
= last_stmt (bb
);
4885 enum gimple_code code
= gimple_code (stmt
);
4886 if (code
!= GIMPLE_COND
4887 && code
!= GIMPLE_SWITCH
4888 && code
!= GIMPLE_GOTO
)
4891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4893 fprintf (dump_file
, "Visiting control stmt ending BB %d: ", bb
->index
);
4894 print_gimple_stmt (dump_file
, stmt
, 0);
4897 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4898 if value-numbering can prove they are not reachable. Handling
4899 computed gotos is also possible. */
4905 tree lhs
= vn_valueize (gimple_cond_lhs (stmt
));
4906 tree rhs
= vn_valueize (gimple_cond_rhs (stmt
));
4907 val
= gimple_simplify (gimple_cond_code (stmt
),
4908 boolean_type_node
, lhs
, rhs
,
4910 /* If that didn't simplify to a constant see if we have recorded
4911 temporary expressions from taken edges. */
4912 if (!val
|| TREE_CODE (val
) != INTEGER_CST
)
4917 val
= vn_nary_op_lookup_pieces (2, gimple_cond_code (stmt
),
4918 boolean_type_node
, ops
, NULL
);
4923 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
4926 val
= gimple_goto_dest (stmt
);
4934 edge taken
= find_taken_edge (bb
, vn_valueize (val
));
4938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4939 fprintf (dump_file
, "Marking all edges out of BB %d but (%d -> %d) as "
4940 "not executable\n", bb
->index
, bb
->index
, taken
->dest
->index
);
4945 /* Do SCCVN. Returns true if it finished, false if we bailed out
4946 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4947 how we use the alias oracle walking during the VN process. */
4950 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4954 default_vn_walk_kind
= default_vn_walk_kind_
;
4958 /* Collect pointers we know point to readonly memory. */
4959 const_parms
= BITMAP_ALLOC (NULL
);
4960 tree fnspec
= lookup_attribute ("fn spec",
4961 TYPE_ATTRIBUTES (TREE_TYPE (cfun
->decl
)));
4964 fnspec
= TREE_VALUE (TREE_VALUE (fnspec
));
4966 for (tree arg
= DECL_ARGUMENTS (cfun
->decl
);
4967 arg
; arg
= DECL_CHAIN (arg
), ++i
)
4969 if (i
>= (unsigned) TREE_STRING_LENGTH (fnspec
))
4971 if (TREE_STRING_POINTER (fnspec
)[i
] == 'R'
4972 || TREE_STRING_POINTER (fnspec
)[i
] == 'r')
4974 tree name
= ssa_default_def (cfun
, arg
);
4976 bitmap_set_bit (const_parms
, SSA_NAME_VERSION (name
));
4981 /* Walk all blocks in dominator order, value-numbering stmts
4982 SSA defs and decide whether outgoing edges are not executable. */
4983 sccvn_dom_walker walker
;
4984 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4986 /* Initialize the value ids and prune out remaining VN_TOPs
4990 FOR_EACH_SSA_NAME (i
, name
, cfun
)
4992 vn_ssa_aux_t info
= VN_INFO (name
);
4994 info
->valnum
= name
;
4995 if (info
->valnum
== name
4996 || info
->valnum
== VN_TOP
)
4997 info
->value_id
= get_next_value_id ();
4998 else if (is_gimple_min_invariant (info
->valnum
))
4999 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
5003 FOR_EACH_SSA_NAME (i
, name
, cfun
)
5005 vn_ssa_aux_t info
= VN_INFO (name
);
5006 if (TREE_CODE (info
->valnum
) == SSA_NAME
5007 && info
->valnum
!= name
5008 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
5009 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
5012 set_hashtable_value_ids ();
5014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5016 fprintf (dump_file
, "Value numbers:\n");
5017 FOR_EACH_SSA_NAME (i
, name
, cfun
)
5019 if (VN_INFO (name
)->visited
5020 && SSA_VAL (name
) != name
)
5022 print_generic_expr (dump_file
, name
);
5023 fprintf (dump_file
, " = ");
5024 print_generic_expr (dump_file
, SSA_VAL (name
));
5025 fprintf (dump_file
, "\n");
5031 /* Return the maximum value id we have ever seen. */
5034 get_max_value_id (void)
5036 return next_value_id
;
5039 /* Return the next unique value id. */
5042 get_next_value_id (void)
5044 return next_value_id
++;
5048 /* Compare two expressions E1 and E2 and return true if they are equal. */
5051 expressions_equal_p (tree e1
, tree e2
)
5053 /* The obvious case. */
5057 /* If either one is VN_TOP consider them equal. */
5058 if (e1
== VN_TOP
|| e2
== VN_TOP
)
5061 /* If only one of them is null, they cannot be equal. */
5065 /* Now perform the actual comparison. */
5066 if (TREE_CODE (e1
) == TREE_CODE (e2
)
5067 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
5074 /* Return true if the nary operation NARY may trap. This is a copy
5075 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
5078 vn_nary_may_trap (vn_nary_op_t nary
)
5081 tree rhs2
= NULL_TREE
;
5082 bool honor_nans
= false;
5083 bool honor_snans
= false;
5084 bool fp_operation
= false;
5085 bool honor_trapv
= false;
5089 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
5090 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
5091 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
5094 fp_operation
= FLOAT_TYPE_P (type
);
5097 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
5098 honor_snans
= flag_signaling_nans
!= 0;
5100 else if (INTEGRAL_TYPE_P (type
)
5101 && TYPE_OVERFLOW_TRAPS (type
))
5104 if (nary
->length
>= 2)
5106 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
5108 honor_nans
, honor_snans
, rhs2
,
5114 for (i
= 0; i
< nary
->length
; ++i
)
5115 if (tree_could_trap_p (nary
->op
[i
]))