1 /* SCC value numbering for trees
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "stor-layout.h"
32 #include "hard-reg-set.h"
35 #include "dominance.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
40 #include "tree-inline.h"
41 #include "hash-table.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
45 #include "gimple-fold.h"
47 #include "gimple-expr.h"
51 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "stringpool.h"
55 #include "tree-ssanames.h"
60 #include "alloc-pool.h"
64 #include "tree-ssa-propagate.h"
65 #include "tree-ssa-sccvn.h"
69 /* This algorithm is based on the SCC algorithm presented by Keith
70 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
71 (http://citeseer.ist.psu.edu/41805.html). In
72 straight line code, it is equivalent to a regular hash based value
73 numbering that is performed in reverse postorder.
75 For code with cycles, there are two alternatives, both of which
76 require keeping the hashtables separate from the actual list of
77 value numbers for SSA names.
79 1. Iterate value numbering in an RPO walk of the blocks, removing
80 all the entries from the hashtable after each iteration (but
81 keeping the SSA name->value number mapping between iterations).
82 Iterate until it does not change.
84 2. Perform value numbering as part of an SCC walk on the SSA graph,
85 iterating only the cycles in the SSA graph until they do not change
86 (using a separate, optimistic hashtable for value numbering the SCC
89 The second is not just faster in practice (because most SSA graph
90 cycles do not involve all the variables in the graph), it also has
93 One of these nice properties is that when we pop an SCC off the
94 stack, we are guaranteed to have processed all the operands coming from
95 *outside of that SCC*, so we do not need to do anything special to
96 ensure they have value numbers.
98 Another nice property is that the SCC walk is done as part of a DFS
99 of the SSA graph, which makes it easy to perform combining and
100 simplifying operations at the same time.
102 The code below is deliberately written in a way that makes it easy
103 to separate the SCC walk from the other work it does.
105 In order to propagate constants through the code, we track which
106 expressions contain constants, and use those while folding. In
107 theory, we could also track expressions whose value numbers are
108 replaced, in case we end up folding based on expression
111 In order to value number memory, we assign value numbers to vuses.
112 This enables us to note that, for example, stores to the same
113 address of the same value from the same starting memory states are
117 1. We can iterate only the changing portions of the SCC's, but
118 I have not seen an SCC big enough for this to be a win.
119 2. If you differentiate between phi nodes for loops and phi nodes
120 for if-then-else, you can properly consider phi nodes in different
121 blocks for equivalence.
122 3. We could value number vuses in more cases, particularly, whole
127 /* vn_nary_op hashtable helpers. */
129 struct vn_nary_op_hasher
: typed_noop_remove
<vn_nary_op_s
>
131 typedef vn_nary_op_s value_type
;
132 typedef vn_nary_op_s compare_type
;
133 static inline hashval_t
hash (const value_type
*);
134 static inline bool equal (const value_type
*, const compare_type
*);
137 /* Return the computed hashcode for nary operation P1. */
140 vn_nary_op_hasher::hash (const value_type
*vno1
)
142 return vno1
->hashcode
;
145 /* Compare nary operations P1 and P2 and return true if they are
149 vn_nary_op_hasher::equal (const value_type
*vno1
, const compare_type
*vno2
)
151 return vn_nary_op_eq (vno1
, vno2
);
154 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
155 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
158 /* vn_phi hashtable helpers. */
161 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
165 typedef vn_phi_s value_type
;
166 typedef vn_phi_s compare_type
;
167 static inline hashval_t
hash (const value_type
*);
168 static inline bool equal (const value_type
*, const compare_type
*);
169 static inline void remove (value_type
*);
172 /* Return the computed hashcode for phi operation P1. */
175 vn_phi_hasher::hash (const value_type
*vp1
)
177 return vp1
->hashcode
;
180 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
183 vn_phi_hasher::equal (const value_type
*vp1
, const compare_type
*vp2
)
185 return vn_phi_eq (vp1
, vp2
);
188 /* Free a phi operation structure VP. */
191 vn_phi_hasher::remove (value_type
*phi
)
193 phi
->phiargs
.release ();
196 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
197 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
200 /* Compare two reference operands P1 and P2 for equality. Return true if
201 they are equal, and false otherwise. */
204 vn_reference_op_eq (const void *p1
, const void *p2
)
206 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
207 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
209 return (vro1
->opcode
== vro2
->opcode
210 /* We do not care for differences in type qualification. */
211 && (vro1
->type
== vro2
->type
212 || (vro1
->type
&& vro2
->type
213 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
214 TYPE_MAIN_VARIANT (vro2
->type
))))
215 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
216 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
217 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
220 /* Free a reference operation structure VP. */
223 free_reference (vn_reference_s
*vr
)
225 vr
->operands
.release ();
229 /* vn_reference hashtable helpers. */
231 struct vn_reference_hasher
233 typedef vn_reference_s value_type
;
234 typedef vn_reference_s compare_type
;
235 static inline hashval_t
hash (const value_type
*);
236 static inline bool equal (const value_type
*, const compare_type
*);
237 static inline void remove (value_type
*);
240 /* Return the hashcode for a given reference operation P1. */
243 vn_reference_hasher::hash (const value_type
*vr1
)
245 return vr1
->hashcode
;
249 vn_reference_hasher::equal (const value_type
*v
, const compare_type
*c
)
251 return vn_reference_eq (v
, c
);
255 vn_reference_hasher::remove (value_type
*v
)
260 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
261 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
264 /* The set of hashtables and alloc_pool's for their items. */
266 typedef struct vn_tables_s
268 vn_nary_op_table_type
*nary
;
269 vn_phi_table_type
*phis
;
270 vn_reference_table_type
*references
;
271 struct obstack nary_obstack
;
272 alloc_pool phis_pool
;
273 alloc_pool references_pool
;
277 /* vn_constant hashtable helpers. */
279 struct vn_constant_hasher
: typed_free_remove
<vn_constant_s
>
281 typedef vn_constant_s value_type
;
282 typedef vn_constant_s compare_type
;
283 static inline hashval_t
hash (const value_type
*);
284 static inline bool equal (const value_type
*, const compare_type
*);
287 /* Hash table hash function for vn_constant_t. */
290 vn_constant_hasher::hash (const value_type
*vc1
)
292 return vc1
->hashcode
;
295 /* Hash table equality function for vn_constant_t. */
298 vn_constant_hasher::equal (const value_type
*vc1
, const compare_type
*vc2
)
300 if (vc1
->hashcode
!= vc2
->hashcode
)
303 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
306 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
307 static bitmap constant_value_ids
;
310 /* Valid hashtables storing information we have proven to be
313 static vn_tables_t valid_info
;
315 /* Optimistic hashtables storing information we are making assumptions about
316 during iterations. */
318 static vn_tables_t optimistic_info
;
320 /* Pointer to the set of hashtables that is currently being used.
321 Should always point to either the optimistic_info, or the
324 static vn_tables_t current_info
;
327 /* Reverse post order index for each basic block. */
329 static int *rpo_numbers
;
331 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
333 /* Return the SSA value of the VUSE x, supporting released VDEFs
334 during elimination which will value-number the VDEF to the
335 associated VUSE (but not substitute in the whole lattice). */
338 vuse_ssa_val (tree x
)
347 while (SSA_NAME_IN_FREE_LIST (x
));
352 /* This represents the top of the VN lattice, which is the universal
357 /* Unique counter for our value ids. */
359 static unsigned int next_value_id
;
361 /* Next DFS number and the stack for strongly connected component
364 static unsigned int next_dfs_num
;
365 static vec
<tree
> sccstack
;
369 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
370 are allocated on an obstack for locality reasons, and to free them
371 without looping over the vec. */
373 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
374 static struct obstack vn_ssa_aux_obstack
;
376 /* Return the value numbering information for a given SSA name. */
381 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
382 gcc_checking_assert (res
);
386 /* Set the value numbering info for a given SSA name to a given
390 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
392 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
395 /* Initialize the value numbering info for a given SSA name.
396 This should be called just once for every SSA name. */
399 VN_INFO_GET (tree name
)
401 vn_ssa_aux_t newinfo
;
403 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
404 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
405 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
406 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
407 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
412 /* Get the representative expression for the SSA_NAME NAME. Returns
413 the representative SSA_NAME if there is no expression associated with it. */
416 vn_get_expr_for (tree name
)
418 vn_ssa_aux_t vn
= VN_INFO (name
);
420 tree expr
= NULL_TREE
;
423 if (vn
->valnum
== VN_TOP
)
426 /* If the value-number is a constant it is the representative
428 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
431 /* Get to the information of the value of this SSA_NAME. */
432 vn
= VN_INFO (vn
->valnum
);
434 /* If the value-number is a constant it is the representative
436 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
439 /* Else if we have an expression, return it. */
440 if (vn
->expr
!= NULL_TREE
)
443 /* Otherwise use the defining statement to build the expression. */
444 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
446 /* If the value number is not an assignment use it directly. */
447 if (!is_gimple_assign (def_stmt
))
450 /* Note that we can valueize here because we clear the cached
451 simplified expressions after each optimistic iteration. */
452 code
= gimple_assign_rhs_code (def_stmt
);
453 switch (TREE_CODE_CLASS (code
))
456 if ((code
== REALPART_EXPR
457 || code
== IMAGPART_EXPR
458 || code
== VIEW_CONVERT_EXPR
)
459 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
461 expr
= fold_build1 (code
,
462 gimple_expr_type (def_stmt
),
463 vn_valueize (TREE_OPERAND
464 (gimple_assign_rhs1 (def_stmt
), 0)));
468 expr
= fold_build1 (code
,
469 gimple_expr_type (def_stmt
),
470 vn_valueize (gimple_assign_rhs1 (def_stmt
)));
474 expr
= fold_build2 (code
,
475 gimple_expr_type (def_stmt
),
476 vn_valueize (gimple_assign_rhs1 (def_stmt
)),
477 vn_valueize (gimple_assign_rhs2 (def_stmt
)));
480 case tcc_exceptional
:
481 if (code
== CONSTRUCTOR
483 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
484 expr
= gimple_assign_rhs1 (def_stmt
);
489 if (expr
== NULL_TREE
)
492 /* Cache the expression. */
498 /* Return the vn_kind the expression computed by the stmt should be
502 vn_get_stmt_kind (gimple stmt
)
504 switch (gimple_code (stmt
))
512 enum tree_code code
= gimple_assign_rhs_code (stmt
);
513 tree rhs1
= gimple_assign_rhs1 (stmt
);
514 switch (get_gimple_rhs_class (code
))
516 case GIMPLE_UNARY_RHS
:
517 case GIMPLE_BINARY_RHS
:
518 case GIMPLE_TERNARY_RHS
:
520 case GIMPLE_SINGLE_RHS
:
521 switch (TREE_CODE_CLASS (code
))
524 /* VOP-less references can go through unary case. */
525 if ((code
== REALPART_EXPR
526 || code
== IMAGPART_EXPR
527 || code
== VIEW_CONVERT_EXPR
528 || code
== BIT_FIELD_REF
)
529 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
533 case tcc_declaration
:
540 if (code
== ADDR_EXPR
)
541 return (is_gimple_min_invariant (rhs1
)
542 ? VN_CONSTANT
: VN_REFERENCE
);
543 else if (code
== CONSTRUCTOR
)
556 /* Lookup a value id for CONSTANT and return it. If it does not
560 get_constant_value_id (tree constant
)
562 vn_constant_s
**slot
;
563 struct vn_constant_s vc
;
565 vc
.hashcode
= vn_hash_constant_with_type (constant
);
566 vc
.constant
= constant
;
567 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
569 return (*slot
)->value_id
;
573 /* Lookup a value id for CONSTANT, and if it does not exist, create a
574 new one and return it. If it does exist, return it. */
577 get_or_alloc_constant_value_id (tree constant
)
579 vn_constant_s
**slot
;
580 struct vn_constant_s vc
;
583 vc
.hashcode
= vn_hash_constant_with_type (constant
);
584 vc
.constant
= constant
;
585 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
587 return (*slot
)->value_id
;
589 vcp
= XNEW (struct vn_constant_s
);
590 vcp
->hashcode
= vc
.hashcode
;
591 vcp
->constant
= constant
;
592 vcp
->value_id
= get_next_value_id ();
594 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
595 return vcp
->value_id
;
598 /* Return true if V is a value id for a constant. */
601 value_id_constant_p (unsigned int v
)
603 return bitmap_bit_p (constant_value_ids
, v
);
606 /* Compute the hash for a reference operand VRO1. */
609 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
611 hstate
.add_int (vro1
->opcode
);
613 inchash::add_expr (vro1
->op0
, hstate
);
615 inchash::add_expr (vro1
->op1
, hstate
);
617 inchash::add_expr (vro1
->op2
, hstate
);
620 /* Compute a hash for the reference operation VR1 and return it. */
623 vn_reference_compute_hash (const vn_reference_t vr1
)
625 inchash::hash hstate
;
628 vn_reference_op_t vro
;
629 HOST_WIDE_INT off
= -1;
632 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
634 if (vro
->opcode
== MEM_REF
)
636 else if (vro
->opcode
!= ADDR_EXPR
)
648 hstate
.add_int (off
);
651 && vro
->opcode
== ADDR_EXPR
)
655 tree op
= TREE_OPERAND (vro
->op0
, 0);
656 hstate
.add_int (TREE_CODE (op
));
657 inchash::add_expr (op
, hstate
);
661 vn_reference_op_compute_hash (vro
, hstate
);
664 result
= hstate
.end ();
665 /* ??? We would ICE later if we hash instead of adding that in. */
667 result
+= SSA_NAME_VERSION (vr1
->vuse
);
672 /* Return true if reference operations VR1 and VR2 are equivalent. This
673 means they have the same set of operands and vuses. */
676 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
680 /* Early out if this is not a hash collision. */
681 if (vr1
->hashcode
!= vr2
->hashcode
)
684 /* The VOP needs to be the same. */
685 if (vr1
->vuse
!= vr2
->vuse
)
688 /* If the operands are the same we are done. */
689 if (vr1
->operands
== vr2
->operands
)
692 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
695 if (INTEGRAL_TYPE_P (vr1
->type
)
696 && INTEGRAL_TYPE_P (vr2
->type
))
698 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
701 else if (INTEGRAL_TYPE_P (vr1
->type
)
702 && (TYPE_PRECISION (vr1
->type
)
703 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
705 else if (INTEGRAL_TYPE_P (vr2
->type
)
706 && (TYPE_PRECISION (vr2
->type
)
707 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
714 HOST_WIDE_INT off1
= 0, off2
= 0;
715 vn_reference_op_t vro1
, vro2
;
716 vn_reference_op_s tem1
, tem2
;
717 bool deref1
= false, deref2
= false;
718 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
720 if (vro1
->opcode
== MEM_REF
)
726 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
728 if (vro2
->opcode
== MEM_REF
)
736 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
738 memset (&tem1
, 0, sizeof (tem1
));
739 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
740 tem1
.type
= TREE_TYPE (tem1
.op0
);
741 tem1
.opcode
= TREE_CODE (tem1
.op0
);
745 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
747 memset (&tem2
, 0, sizeof (tem2
));
748 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
749 tem2
.type
= TREE_TYPE (tem2
.op0
);
750 tem2
.opcode
= TREE_CODE (tem2
.op0
);
754 if (deref1
!= deref2
)
756 if (!vn_reference_op_eq (vro1
, vro2
))
761 while (vr1
->operands
.length () != i
762 || vr2
->operands
.length () != j
);
767 /* Copy the operations present in load/store REF into RESULT, a vector of
768 vn_reference_op_s's. */
771 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
773 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
775 vn_reference_op_s temp
;
779 memset (&temp
, 0, sizeof (temp
));
780 temp
.type
= TREE_TYPE (ref
);
781 temp
.opcode
= TREE_CODE (ref
);
782 temp
.op0
= TMR_INDEX (ref
);
783 temp
.op1
= TMR_STEP (ref
);
784 temp
.op2
= TMR_OFFSET (ref
);
786 result
->quick_push (temp
);
788 memset (&temp
, 0, sizeof (temp
));
789 temp
.type
= NULL_TREE
;
790 temp
.opcode
= ERROR_MARK
;
791 temp
.op0
= TMR_INDEX2 (ref
);
793 result
->quick_push (temp
);
795 memset (&temp
, 0, sizeof (temp
));
796 temp
.type
= NULL_TREE
;
797 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
798 temp
.op0
= TMR_BASE (ref
);
800 result
->quick_push (temp
);
804 /* For non-calls, store the information that makes up the address. */
808 vn_reference_op_s temp
;
810 memset (&temp
, 0, sizeof (temp
));
811 temp
.type
= TREE_TYPE (ref
);
812 temp
.opcode
= TREE_CODE (ref
);
818 temp
.op0
= TREE_OPERAND (ref
, 1);
821 temp
.op0
= TREE_OPERAND (ref
, 1);
825 /* The base address gets its own vn_reference_op_s structure. */
826 temp
.op0
= TREE_OPERAND (ref
, 1);
827 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 1)))
828 temp
.off
= tree_to_shwi (TREE_OPERAND (ref
, 1));
831 /* Record bits and position. */
832 temp
.op0
= TREE_OPERAND (ref
, 1);
833 temp
.op1
= TREE_OPERAND (ref
, 2);
836 /* The field decl is enough to unambiguously specify the field,
837 a matching type is not necessary and a mismatching type
838 is always a spurious difference. */
839 temp
.type
= NULL_TREE
;
840 temp
.op0
= TREE_OPERAND (ref
, 1);
841 temp
.op1
= TREE_OPERAND (ref
, 2);
843 tree this_offset
= component_ref_field_offset (ref
);
845 && TREE_CODE (this_offset
) == INTEGER_CST
)
847 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
848 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
851 = (wi::to_offset (this_offset
)
852 + wi::lrshift (wi::to_offset (bit_offset
),
853 LOG2_BITS_PER_UNIT
));
854 if (wi::fits_shwi_p (off
)
855 /* Probibit value-numbering zero offset components
856 of addresses the same before the pass folding
857 __builtin_object_size had a chance to run
858 (checking cfun->after_inlining does the
860 && (TREE_CODE (orig
) != ADDR_EXPR
862 || cfun
->after_inlining
))
863 temp
.off
= off
.to_shwi ();
868 case ARRAY_RANGE_REF
:
870 /* Record index as operand. */
871 temp
.op0
= TREE_OPERAND (ref
, 1);
872 /* Always record lower bounds and element size. */
873 temp
.op1
= array_ref_low_bound (ref
);
874 temp
.op2
= array_ref_element_size (ref
);
875 if (TREE_CODE (temp
.op0
) == INTEGER_CST
876 && TREE_CODE (temp
.op1
) == INTEGER_CST
877 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
879 offset_int off
= ((wi::to_offset (temp
.op0
)
880 - wi::to_offset (temp
.op1
))
881 * wi::to_offset (temp
.op2
));
882 if (wi::fits_shwi_p (off
))
883 temp
.off
= off
.to_shwi();
887 if (DECL_HARD_REGISTER (ref
))
896 /* Canonicalize decls to MEM[&decl] which is what we end up with
897 when valueizing MEM[ptr] with ptr = &decl. */
898 temp
.opcode
= MEM_REF
;
899 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
901 result
->safe_push (temp
);
902 temp
.opcode
= ADDR_EXPR
;
903 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
904 temp
.type
= TREE_TYPE (temp
.op0
);
918 if (is_gimple_min_invariant (ref
))
924 /* These are only interesting for their operands, their
925 existence, and their type. They will never be the last
926 ref in the chain of references (IE they require an
927 operand), so we don't have to put anything
928 for op* as it will be handled by the iteration */
930 case VIEW_CONVERT_EXPR
:
934 /* This is only interesting for its constant offset. */
935 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
940 result
->safe_push (temp
);
942 if (REFERENCE_CLASS_P (ref
)
943 || TREE_CODE (ref
) == MODIFY_EXPR
944 || TREE_CODE (ref
) == WITH_SIZE_EXPR
945 || (TREE_CODE (ref
) == ADDR_EXPR
946 && !is_gimple_min_invariant (ref
)))
947 ref
= TREE_OPERAND (ref
, 0);
953 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
954 operands in *OPS, the reference alias set SET and the reference type TYPE.
955 Return true if something useful was produced. */
958 ao_ref_init_from_vn_reference (ao_ref
*ref
,
959 alias_set_type set
, tree type
,
960 vec
<vn_reference_op_s
> ops
)
962 vn_reference_op_t op
;
964 tree base
= NULL_TREE
;
966 HOST_WIDE_INT offset
= 0;
967 HOST_WIDE_INT max_size
;
968 HOST_WIDE_INT size
= -1;
969 tree size_tree
= NULL_TREE
;
970 alias_set_type base_alias_set
= -1;
972 /* First get the final access size from just the outermost expression. */
974 if (op
->opcode
== COMPONENT_REF
)
975 size_tree
= DECL_SIZE (op
->op0
);
976 else if (op
->opcode
== BIT_FIELD_REF
)
980 machine_mode mode
= TYPE_MODE (type
);
982 size_tree
= TYPE_SIZE (type
);
984 size
= GET_MODE_BITSIZE (mode
);
986 if (size_tree
!= NULL_TREE
)
988 if (!tree_fits_uhwi_p (size_tree
))
991 size
= tree_to_uhwi (size_tree
);
994 /* Initially, maxsize is the same as the accessed element size.
995 In the following it will only grow (or become -1). */
998 /* Compute cumulative bit-offset for nested component-refs and array-refs,
999 and find the ultimate containing object. */
1000 FOR_EACH_VEC_ELT (ops
, i
, op
)
1004 /* These may be in the reference ops, but we cannot do anything
1005 sensible with them here. */
1007 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1008 if (base
!= NULL_TREE
1009 && TREE_CODE (base
) == MEM_REF
1011 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
1013 vn_reference_op_t pop
= &ops
[i
-1];
1014 base
= TREE_OPERAND (op
->op0
, 0);
1021 offset
+= pop
->off
* BITS_PER_UNIT
;
1029 /* Record the base objects. */
1031 base_alias_set
= get_deref_alias_set (op
->op0
);
1032 *op0_p
= build2 (MEM_REF
, op
->type
,
1033 NULL_TREE
, op
->op0
);
1034 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1045 /* And now the usual component-reference style ops. */
1047 offset
+= tree_to_shwi (op
->op1
);
1052 tree field
= op
->op0
;
1053 /* We do not have a complete COMPONENT_REF tree here so we
1054 cannot use component_ref_field_offset. Do the interesting
1058 || !tree_fits_uhwi_p (DECL_FIELD_OFFSET (field
)))
1062 offset
+= (tree_to_uhwi (DECL_FIELD_OFFSET (field
))
1064 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
1069 case ARRAY_RANGE_REF
:
1071 /* We recorded the lower bound and the element size. */
1072 if (!tree_fits_shwi_p (op
->op0
)
1073 || !tree_fits_shwi_p (op
->op1
)
1074 || !tree_fits_shwi_p (op
->op2
))
1078 HOST_WIDE_INT hindex
= tree_to_shwi (op
->op0
);
1079 hindex
-= tree_to_shwi (op
->op1
);
1080 hindex
*= tree_to_shwi (op
->op2
);
1081 hindex
*= BITS_PER_UNIT
;
1093 case VIEW_CONVERT_EXPR
:
1110 if (base
== NULL_TREE
)
1113 ref
->ref
= NULL_TREE
;
1115 ref
->offset
= offset
;
1117 ref
->max_size
= max_size
;
1118 ref
->ref_alias_set
= set
;
1119 if (base_alias_set
!= -1)
1120 ref
->base_alias_set
= base_alias_set
;
1122 ref
->base_alias_set
= get_alias_set (base
);
1123 /* We discount volatiles from value-numbering elsewhere. */
1124 ref
->volatile_p
= false;
1129 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1130 vn_reference_op_s's. */
1133 copy_reference_ops_from_call (gimple call
,
1134 vec
<vn_reference_op_s
> *result
)
1136 vn_reference_op_s temp
;
1138 tree lhs
= gimple_call_lhs (call
);
1141 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1142 different. By adding the lhs here in the vector, we ensure that the
1143 hashcode is different, guaranteeing a different value number. */
1144 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1146 memset (&temp
, 0, sizeof (temp
));
1147 temp
.opcode
= MODIFY_EXPR
;
1148 temp
.type
= TREE_TYPE (lhs
);
1151 result
->safe_push (temp
);
1154 /* Copy the type, opcode, function, static chain and EH region, if any. */
1155 memset (&temp
, 0, sizeof (temp
));
1156 temp
.type
= gimple_call_return_type (call
);
1157 temp
.opcode
= CALL_EXPR
;
1158 temp
.op0
= gimple_call_fn (call
);
1159 temp
.op1
= gimple_call_chain (call
);
1160 if (stmt_could_throw_p (call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1161 temp
.op2
= size_int (lr
);
1163 if (gimple_call_with_bounds_p (call
))
1164 temp
.with_bounds
= 1;
1165 result
->safe_push (temp
);
1167 /* Copy the call arguments. As they can be references as well,
1168 just chain them together. */
1169 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1171 tree callarg
= gimple_call_arg (call
, i
);
1172 copy_reference_ops_from_ref (callarg
, result
);
1176 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1177 *I_P to point to the last element of the replacement. */
1179 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1182 unsigned int i
= *i_p
;
1183 vn_reference_op_t op
= &(*ops
)[i
];
1184 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1186 HOST_WIDE_INT addr_offset
= 0;
1188 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1189 from .foo.bar to the preceding MEM_REF offset and replace the
1190 address with &OBJ. */
1191 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1193 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1194 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1196 offset_int off
= offset_int::from (mem_op
->op0
, SIGNED
);
1198 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1199 op
->op0
= build_fold_addr_expr (addr_base
);
1200 if (tree_fits_shwi_p (mem_op
->op0
))
1201 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1207 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1208 *I_P to point to the last element of the replacement. */
1210 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1213 unsigned int i
= *i_p
;
1214 vn_reference_op_t op
= &(*ops
)[i
];
1215 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1217 enum tree_code code
;
1220 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1221 if (!is_gimple_assign (def_stmt
))
1224 code
= gimple_assign_rhs_code (def_stmt
);
1225 if (code
!= ADDR_EXPR
1226 && code
!= POINTER_PLUS_EXPR
)
1229 off
= offset_int::from (mem_op
->op0
, SIGNED
);
1231 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1232 from .foo.bar to the preceding MEM_REF offset and replace the
1233 address with &OBJ. */
1234 if (code
== ADDR_EXPR
)
1236 tree addr
, addr_base
;
1237 HOST_WIDE_INT addr_offset
;
1239 addr
= gimple_assign_rhs1 (def_stmt
);
1240 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1243 || TREE_CODE (addr_base
) != MEM_REF
)
1247 off
+= mem_ref_offset (addr_base
);
1248 op
->op0
= TREE_OPERAND (addr_base
, 0);
1253 ptr
= gimple_assign_rhs1 (def_stmt
);
1254 ptroff
= gimple_assign_rhs2 (def_stmt
);
1255 if (TREE_CODE (ptr
) != SSA_NAME
1256 || TREE_CODE (ptroff
) != INTEGER_CST
)
1259 off
+= wi::to_offset (ptroff
);
1263 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1264 if (tree_fits_shwi_p (mem_op
->op0
))
1265 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1268 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1269 op
->op0
= SSA_VAL (op
->op0
);
1270 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1271 op
->opcode
= TREE_CODE (op
->op0
);
1274 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1275 vn_reference_maybe_forwprop_address (ops
, i_p
);
1276 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1277 vn_reference_fold_indirect (ops
, i_p
);
1280 /* Optimize the reference REF to a constant if possible or return
1281 NULL_TREE if not. */
1284 fully_constant_vn_reference_p (vn_reference_t ref
)
1286 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1287 vn_reference_op_t op
;
1289 /* Try to simplify the translated expression if it is
1290 a call to a builtin function with at most two arguments. */
1292 if (op
->opcode
== CALL_EXPR
1293 && TREE_CODE (op
->op0
) == ADDR_EXPR
1294 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1295 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1296 && operands
.length () >= 2
1297 && operands
.length () <= 3)
1299 vn_reference_op_t arg0
, arg1
= NULL
;
1300 bool anyconst
= false;
1301 arg0
= &operands
[1];
1302 if (operands
.length () > 2)
1303 arg1
= &operands
[2];
1304 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1305 || (arg0
->opcode
== ADDR_EXPR
1306 && is_gimple_min_invariant (arg0
->op0
)))
1309 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1310 || (arg1
->opcode
== ADDR_EXPR
1311 && is_gimple_min_invariant (arg1
->op0
))))
1315 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1318 arg1
? arg1
->op0
: NULL
);
1320 && TREE_CODE (folded
) == NOP_EXPR
)
1321 folded
= TREE_OPERAND (folded
, 0);
1323 && is_gimple_min_invariant (folded
))
1328 /* Simplify reads from constant strings. */
1329 else if (op
->opcode
== ARRAY_REF
1330 && TREE_CODE (op
->op0
) == INTEGER_CST
1331 && integer_zerop (op
->op1
)
1332 && operands
.length () == 2)
1334 vn_reference_op_t arg0
;
1335 arg0
= &operands
[1];
1336 if (arg0
->opcode
== STRING_CST
1337 && (TYPE_MODE (op
->type
)
1338 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1339 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1340 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1341 && tree_int_cst_sgn (op
->op0
) >= 0
1342 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1343 return build_int_cst_type (op
->type
,
1344 (TREE_STRING_POINTER (arg0
->op0
)
1345 [TREE_INT_CST_LOW (op
->op0
)]));
1351 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1352 structures into their value numbers. This is done in-place, and
1353 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1354 whether any operands were valueized. */
1356 static vec
<vn_reference_op_s
>
1357 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1359 vn_reference_op_t vro
;
1362 *valueized_anything
= false;
1364 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1366 if (vro
->opcode
== SSA_NAME
1367 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1369 tree tem
= SSA_VAL (vro
->op0
);
1370 if (tem
!= vro
->op0
)
1372 *valueized_anything
= true;
1375 /* If it transforms from an SSA_NAME to a constant, update
1377 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1378 vro
->opcode
= TREE_CODE (vro
->op0
);
1380 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1382 tree tem
= SSA_VAL (vro
->op1
);
1383 if (tem
!= vro
->op1
)
1385 *valueized_anything
= true;
1389 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1391 tree tem
= SSA_VAL (vro
->op2
);
1392 if (tem
!= vro
->op2
)
1394 *valueized_anything
= true;
1398 /* If it transforms from an SSA_NAME to an address, fold with
1399 a preceding indirect reference. */
1402 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1403 && orig
[i
- 1].opcode
== MEM_REF
)
1404 vn_reference_fold_indirect (&orig
, &i
);
1406 && vro
->opcode
== SSA_NAME
1407 && orig
[i
- 1].opcode
== MEM_REF
)
1408 vn_reference_maybe_forwprop_address (&orig
, &i
);
1409 /* If it transforms a non-constant ARRAY_REF into a constant
1410 one, adjust the constant offset. */
1411 else if (vro
->opcode
== ARRAY_REF
1413 && TREE_CODE (vro
->op0
) == INTEGER_CST
1414 && TREE_CODE (vro
->op1
) == INTEGER_CST
1415 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1417 offset_int off
= ((wi::to_offset (vro
->op0
)
1418 - wi::to_offset (vro
->op1
))
1419 * wi::to_offset (vro
->op2
));
1420 if (wi::fits_shwi_p (off
))
1421 vro
->off
= off
.to_shwi ();
1428 static vec
<vn_reference_op_s
>
1429 valueize_refs (vec
<vn_reference_op_s
> orig
)
1432 return valueize_refs_1 (orig
, &tem
);
1435 static vec
<vn_reference_op_s
> shared_lookup_references
;
1437 /* Create a vector of vn_reference_op_s structures from REF, a
1438 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1439 this function. *VALUEIZED_ANYTHING will specify whether any
1440 operands were valueized. */
1442 static vec
<vn_reference_op_s
>
1443 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1447 shared_lookup_references
.truncate (0);
1448 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1449 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1450 valueized_anything
);
1451 return shared_lookup_references
;
1454 /* Create a vector of vn_reference_op_s structures from CALL, a
1455 call statement. The vector is shared among all callers of
1458 static vec
<vn_reference_op_s
>
1459 valueize_shared_reference_ops_from_call (gimple call
)
1463 shared_lookup_references
.truncate (0);
1464 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1465 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1466 return shared_lookup_references
;
1469 /* Lookup a SCCVN reference operation VR in the current hash table.
1470 Returns the resulting value number if it exists in the hash table,
1471 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1472 vn_reference_t stored in the hashtable if something is found. */
1475 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1477 vn_reference_s
**slot
;
1480 hash
= vr
->hashcode
;
1481 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1482 if (!slot
&& current_info
== optimistic_info
)
1483 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1487 *vnresult
= (vn_reference_t
)*slot
;
1488 return ((vn_reference_t
)*slot
)->result
;
1494 static tree
*last_vuse_ptr
;
1495 static vn_lookup_kind vn_walk_kind
;
1496 static vn_lookup_kind default_vn_walk_kind
;
1498 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1499 with the current VUSE and performs the expression lookup. */
1502 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1503 unsigned int cnt
, void *vr_
)
1505 vn_reference_t vr
= (vn_reference_t
)vr_
;
1506 vn_reference_s
**slot
;
1509 /* This bounds the stmt walks we perform on reference lookups
1510 to O(1) instead of O(N) where N is the number of dominating
1512 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1516 *last_vuse_ptr
= vuse
;
1518 /* Fixup vuse and hash. */
1520 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1521 vr
->vuse
= vuse_ssa_val (vuse
);
1523 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1525 hash
= vr
->hashcode
;
1526 slot
= current_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1527 if (!slot
&& current_info
== optimistic_info
)
1528 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1535 /* Lookup an existing or insert a new vn_reference entry into the
1536 value table for the VUSE, SET, TYPE, OPERANDS reference which
1537 has the value VALUE which is either a constant or an SSA name. */
1539 static vn_reference_t
1540 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1543 vec
<vn_reference_op_s
,
1547 struct vn_reference_s vr1
;
1548 vn_reference_t result
;
1551 vr1
.operands
= operands
;
1554 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1555 if (vn_reference_lookup_1 (&vr1
, &result
))
1557 if (TREE_CODE (value
) == SSA_NAME
)
1558 value_id
= VN_INFO (value
)->value_id
;
1560 value_id
= get_or_alloc_constant_value_id (value
);
1561 return vn_reference_insert_pieces (vuse
, set
, type
,
1562 operands
.copy (), value
, value_id
);
1565 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1566 from the statement defining VUSE and if not successful tries to
1567 translate *REFP and VR_ through an aggregate copy at the definition
1571 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
,
1572 bool disambiguate_only
)
1574 vn_reference_t vr
= (vn_reference_t
)vr_
;
1575 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1577 HOST_WIDE_INT offset
, maxsize
;
1578 static vec
<vn_reference_op_s
>
1581 bool lhs_ref_ok
= false;
1583 /* First try to disambiguate after value-replacing in the definitions LHS. */
1584 if (is_gimple_assign (def_stmt
))
1586 vec
<vn_reference_op_s
> tem
;
1587 tree lhs
= gimple_assign_lhs (def_stmt
);
1588 bool valueized_anything
= false;
1589 /* Avoid re-allocation overhead. */
1590 lhs_ops
.truncate (0);
1591 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1593 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1594 gcc_assert (lhs_ops
== tem
);
1595 if (valueized_anything
)
1597 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1598 get_alias_set (lhs
),
1599 TREE_TYPE (lhs
), lhs_ops
);
1601 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1606 ao_ref_init (&lhs_ref
, lhs
);
1610 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
1611 && gimple_call_num_args (def_stmt
) <= 4)
1613 /* For builtin calls valueize its arguments and call the
1614 alias oracle again. Valueization may improve points-to
1615 info of pointers and constify size and position arguments.
1616 Originally this was motivated by PR61034 which has
1617 conditional calls to free falsely clobbering ref because
1618 of imprecise points-to info of the argument. */
1620 bool valueized_anything
= false;
1621 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1623 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
1624 if (TREE_CODE (oldargs
[i
]) == SSA_NAME
1625 && VN_INFO (oldargs
[i
])->valnum
!= oldargs
[i
])
1627 gimple_call_set_arg (def_stmt
, i
, VN_INFO (oldargs
[i
])->valnum
);
1628 valueized_anything
= true;
1631 if (valueized_anything
)
1633 bool res
= call_may_clobber_ref_p_1 (def_stmt
, ref
);
1634 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1635 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
1641 if (disambiguate_only
)
1644 base
= ao_ref_base (ref
);
1645 offset
= ref
->offset
;
1646 maxsize
= ref
->max_size
;
1648 /* If we cannot constrain the size of the reference we cannot
1649 test if anything kills it. */
1653 /* We can't deduce anything useful from clobbers. */
1654 if (gimple_clobber_p (def_stmt
))
1657 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1658 from that definition.
1660 if (is_gimple_reg_type (vr
->type
)
1661 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1662 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1663 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1664 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1666 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1668 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1669 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1670 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1671 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1672 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1674 && operand_equal_p (base
, base2
, 0)
1675 && offset2
<= offset
1676 && offset2
+ size2
>= offset
+ maxsize
)
1678 tree val
= build_zero_cst (vr
->type
);
1679 return vn_reference_lookup_or_insert_for_pieces
1680 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1684 /* 2) Assignment from an empty CONSTRUCTOR. */
1685 else if (is_gimple_reg_type (vr
->type
)
1686 && gimple_assign_single_p (def_stmt
)
1687 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1688 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1691 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1692 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1693 &offset2
, &size2
, &maxsize2
);
1695 && operand_equal_p (base
, base2
, 0)
1696 && offset2
<= offset
1697 && offset2
+ size2
>= offset
+ maxsize
)
1699 tree val
= build_zero_cst (vr
->type
);
1700 return vn_reference_lookup_or_insert_for_pieces
1701 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1705 /* 3) Assignment from a constant. We can use folds native encode/interpret
1706 routines to extract the assigned bits. */
1707 else if (vn_walk_kind
== VN_WALKREWRITE
1708 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1709 && ref
->size
== maxsize
1710 && maxsize
% BITS_PER_UNIT
== 0
1711 && offset
% BITS_PER_UNIT
== 0
1712 && is_gimple_reg_type (vr
->type
)
1713 && gimple_assign_single_p (def_stmt
)
1714 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1717 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1718 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1719 &offset2
, &size2
, &maxsize2
);
1721 && maxsize2
== size2
1722 && size2
% BITS_PER_UNIT
== 0
1723 && offset2
% BITS_PER_UNIT
== 0
1724 && operand_equal_p (base
, base2
, 0)
1725 && offset2
<= offset
1726 && offset2
+ size2
>= offset
+ maxsize
)
1728 /* We support up to 512-bit values (for V8DFmode). */
1729 unsigned char buffer
[64];
1732 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1733 buffer
, sizeof (buffer
));
1736 tree val
= native_interpret_expr (vr
->type
,
1738 + ((offset
- offset2
)
1740 ref
->size
/ BITS_PER_UNIT
);
1742 return vn_reference_lookup_or_insert_for_pieces
1743 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1748 /* 4) Assignment from an SSA name which definition we may be able
1749 to access pieces from. */
1750 else if (ref
->size
== maxsize
1751 && is_gimple_reg_type (vr
->type
)
1752 && gimple_assign_single_p (def_stmt
)
1753 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1755 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1756 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1757 if (is_gimple_assign (def_stmt2
)
1758 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1759 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1760 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1763 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1764 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1765 &offset2
, &size2
, &maxsize2
);
1766 off
= offset
- offset2
;
1768 && maxsize2
== size2
1769 && operand_equal_p (base
, base2
, 0)
1770 && offset2
<= offset
1771 && offset2
+ size2
>= offset
+ maxsize
)
1773 tree val
= NULL_TREE
;
1775 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1776 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1779 val
= gimple_assign_rhs1 (def_stmt2
);
1780 else if (off
== elsz
)
1781 val
= gimple_assign_rhs2 (def_stmt2
);
1783 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1786 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1787 unsigned i
= off
/ elsz
;
1788 if (i
< CONSTRUCTOR_NELTS (ctor
))
1790 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1791 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1793 if (TREE_CODE (TREE_TYPE (elt
->value
))
1800 return vn_reference_lookup_or_insert_for_pieces
1801 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1806 /* 5) For aggregate copies translate the reference through them if
1807 the copy kills ref. */
1808 else if (vn_walk_kind
== VN_WALKREWRITE
1809 && gimple_assign_single_p (def_stmt
)
1810 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1811 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1812 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1815 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1817 auto_vec
<vn_reference_op_s
> rhs
;
1818 vn_reference_op_t vro
;
1824 /* See if the assignment kills REF. */
1825 base2
= ao_ref_base (&lhs_ref
);
1826 offset2
= lhs_ref
.offset
;
1827 size2
= lhs_ref
.size
;
1828 maxsize2
= lhs_ref
.max_size
;
1830 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1832 || offset2
+ size2
< offset
+ maxsize
)
1835 /* Find the common base of ref and the lhs. lhs_ops already
1836 contains valueized operands for the lhs. */
1837 i
= vr
->operands
.length () - 1;
1838 j
= lhs_ops
.length () - 1;
1839 while (j
>= 0 && i
>= 0
1840 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1846 /* ??? The innermost op should always be a MEM_REF and we already
1847 checked that the assignment to the lhs kills vr. Thus for
1848 aggregate copies using char[] types the vn_reference_op_eq
1849 may fail when comparing types for compatibility. But we really
1850 don't care here - further lookups with the rewritten operands
1851 will simply fail if we messed up types too badly. */
1852 if (j
== 0 && i
>= 0
1853 && lhs_ops
[0].opcode
== MEM_REF
1854 && lhs_ops
[0].off
!= -1
1855 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1858 /* i now points to the first additional op.
1859 ??? LHS may not be completely contained in VR, one or more
1860 VIEW_CONVERT_EXPRs could be in its way. We could at least
1861 try handling outermost VIEW_CONVERT_EXPRs. */
1865 /* Now re-write REF to be based on the rhs of the assignment. */
1866 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1867 /* We need to pre-pend vr->operands[0..i] to rhs. */
1868 vec
<vn_reference_op_s
> old
= vr
->operands
;
1869 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1871 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1872 if (old
== shared_lookup_references
)
1873 shared_lookup_references
= vr
->operands
;
1876 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1877 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1878 vr
->operands
[i
+ 1 + j
] = *vro
;
1879 vr
->operands
= valueize_refs (vr
->operands
);
1880 if (old
== shared_lookup_references
)
1881 shared_lookup_references
= vr
->operands
;
1882 vr
->hashcode
= vn_reference_compute_hash (vr
);
1884 /* Adjust *ref from the new operands. */
1885 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1887 /* This can happen with bitfields. */
1888 if (ref
->size
!= r
.size
)
1892 /* Do not update last seen VUSE after translating. */
1893 last_vuse_ptr
= NULL
;
1895 /* Keep looking for the adjusted *REF / VR pair. */
1899 /* 6) For memcpy copies translate the reference through them if
1900 the copy kills ref. */
1901 else if (vn_walk_kind
== VN_WALKREWRITE
1902 && is_gimple_reg_type (vr
->type
)
1903 /* ??? Handle BCOPY as well. */
1904 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1905 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1906 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1907 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1908 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1909 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1910 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1911 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
1915 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1916 vn_reference_op_s op
;
1920 /* Only handle non-variable, addressable refs. */
1921 if (ref
->size
!= maxsize
1922 || offset
% BITS_PER_UNIT
!= 0
1923 || ref
->size
% BITS_PER_UNIT
!= 0)
1926 /* Extract a pointer base and an offset for the destination. */
1927 lhs
= gimple_call_arg (def_stmt
, 0);
1929 if (TREE_CODE (lhs
) == SSA_NAME
)
1930 lhs
= SSA_VAL (lhs
);
1931 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1933 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1937 if (TREE_CODE (tem
) == MEM_REF
1938 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1940 lhs
= TREE_OPERAND (tem
, 0);
1941 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1943 else if (DECL_P (tem
))
1944 lhs
= build_fold_addr_expr (tem
);
1948 if (TREE_CODE (lhs
) != SSA_NAME
1949 && TREE_CODE (lhs
) != ADDR_EXPR
)
1952 /* Extract a pointer base and an offset for the source. */
1953 rhs
= gimple_call_arg (def_stmt
, 1);
1955 if (TREE_CODE (rhs
) == SSA_NAME
)
1956 rhs
= SSA_VAL (rhs
);
1957 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1959 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1963 if (TREE_CODE (tem
) == MEM_REF
1964 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1966 rhs
= TREE_OPERAND (tem
, 0);
1967 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1969 else if (DECL_P (tem
))
1970 rhs
= build_fold_addr_expr (tem
);
1974 if (TREE_CODE (rhs
) != SSA_NAME
1975 && TREE_CODE (rhs
) != ADDR_EXPR
)
1978 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
1980 /* The bases of the destination and the references have to agree. */
1981 if ((TREE_CODE (base
) != MEM_REF
1983 || (TREE_CODE (base
) == MEM_REF
1984 && (TREE_OPERAND (base
, 0) != lhs
1985 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
1987 && (TREE_CODE (lhs
) != ADDR_EXPR
1988 || TREE_OPERAND (lhs
, 0) != base
)))
1991 /* And the access has to be contained within the memcpy destination. */
1992 at
= offset
/ BITS_PER_UNIT
;
1993 if (TREE_CODE (base
) == MEM_REF
)
1994 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
1996 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1999 /* Make room for 2 operands in the new reference. */
2000 if (vr
->operands
.length () < 2)
2002 vec
<vn_reference_op_s
> old
= vr
->operands
;
2003 vr
->operands
.safe_grow_cleared (2);
2004 if (old
== shared_lookup_references
2005 && vr
->operands
!= old
)
2006 shared_lookup_references
= vr
->operands
;
2009 vr
->operands
.truncate (2);
2011 /* The looked-through reference is a simple MEM_REF. */
2012 memset (&op
, 0, sizeof (op
));
2014 op
.opcode
= MEM_REF
;
2015 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
2016 op
.off
= at
- lhs_offset
+ rhs_offset
;
2017 vr
->operands
[0] = op
;
2018 op
.type
= TREE_TYPE (rhs
);
2019 op
.opcode
= TREE_CODE (rhs
);
2022 vr
->operands
[1] = op
;
2023 vr
->hashcode
= vn_reference_compute_hash (vr
);
2025 /* Adjust *ref from the new operands. */
2026 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2028 /* This can happen with bitfields. */
2029 if (ref
->size
!= r
.size
)
2033 /* Do not update last seen VUSE after translating. */
2034 last_vuse_ptr
= NULL
;
2036 /* Keep looking for the adjusted *REF / VR pair. */
2040 /* Bail out and stop walking. */
2044 /* Lookup a reference operation by it's parts, in the current hash table.
2045 Returns the resulting value number if it exists in the hash table,
2046 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2047 vn_reference_t stored in the hashtable if something is found. */
2050 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2051 vec
<vn_reference_op_s
> operands
,
2052 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2054 struct vn_reference_s vr1
;
2062 vr1
.vuse
= vuse_ssa_val (vuse
);
2063 shared_lookup_references
.truncate (0);
2064 shared_lookup_references
.safe_grow (operands
.length ());
2065 memcpy (shared_lookup_references
.address (),
2066 operands
.address (),
2067 sizeof (vn_reference_op_s
)
2068 * operands
.length ());
2069 vr1
.operands
= operands
= shared_lookup_references
2070 = valueize_refs (shared_lookup_references
);
2073 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2074 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2077 vn_reference_lookup_1 (&vr1
, vnresult
);
2079 && kind
!= VN_NOWALK
2083 vn_walk_kind
= kind
;
2084 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2086 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2087 vn_reference_lookup_2
,
2088 vn_reference_lookup_3
, &vr1
);
2089 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2093 return (*vnresult
)->result
;
2098 /* Lookup OP in the current hash table, and return the resulting value
2099 number if it exists in the hash table. Return NULL_TREE if it does
2100 not exist in the hash table or if the result field of the structure
2101 was NULL.. VNRESULT will be filled in with the vn_reference_t
2102 stored in the hashtable if one exists. */
2105 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2106 vn_reference_t
*vnresult
)
2108 vec
<vn_reference_op_s
> operands
;
2109 struct vn_reference_s vr1
;
2111 bool valuezied_anything
;
2116 vr1
.vuse
= vuse_ssa_val (vuse
);
2117 vr1
.operands
= operands
2118 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2119 vr1
.type
= TREE_TYPE (op
);
2120 vr1
.set
= get_alias_set (op
);
2121 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2122 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2125 if (kind
!= VN_NOWALK
2128 vn_reference_t wvnresult
;
2130 /* Make sure to use a valueized reference if we valueized anything.
2131 Otherwise preserve the full reference for advanced TBAA. */
2132 if (!valuezied_anything
2133 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2135 ao_ref_init (&r
, op
);
2136 vn_walk_kind
= kind
;
2138 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2139 vn_reference_lookup_2
,
2140 vn_reference_lookup_3
, &vr1
);
2141 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2145 *vnresult
= wvnresult
;
2146 return wvnresult
->result
;
2152 return vn_reference_lookup_1 (&vr1
, vnresult
);
2155 /* Lookup CALL in the current hash table and return the entry in
2156 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2159 vn_reference_lookup_call (gimple call
, vn_reference_t
*vnresult
,
2165 tree vuse
= gimple_vuse (call
);
2167 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2168 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
2169 vr
->type
= gimple_expr_type (call
);
2171 vr
->hashcode
= vn_reference_compute_hash (vr
);
2172 vn_reference_lookup_1 (vr
, vnresult
);
2175 /* Insert OP into the current hash table with a value number of
2176 RESULT, and return the resulting reference structure we created. */
2178 static vn_reference_t
2179 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2181 vn_reference_s
**slot
;
2185 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2186 if (TREE_CODE (result
) == SSA_NAME
)
2187 vr1
->value_id
= VN_INFO (result
)->value_id
;
2189 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2190 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2191 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2192 vr1
->type
= TREE_TYPE (op
);
2193 vr1
->set
= get_alias_set (op
);
2194 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2195 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2196 vr1
->result_vdef
= vdef
;
2198 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2201 /* Because we lookup stores using vuses, and value number failures
2202 using the vdefs (see visit_reference_op_store for how and why),
2203 it's possible that on failure we may try to insert an already
2204 inserted store. This is not wrong, there is no ssa name for a
2205 store that we could use as a differentiator anyway. Thus, unlike
2206 the other lookup functions, you cannot gcc_assert (!*slot)
2209 /* But free the old slot in case of a collision. */
2211 free_reference (*slot
);
2217 /* Insert a reference by it's pieces into the current hash table with
2218 a value number of RESULT. Return the resulting reference
2219 structure we created. */
2222 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2223 vec
<vn_reference_op_s
> operands
,
2224 tree result
, unsigned int value_id
)
2227 vn_reference_s
**slot
;
2230 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2231 vr1
->value_id
= value_id
;
2232 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2233 vr1
->operands
= valueize_refs (operands
);
2236 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2237 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2238 result
= SSA_VAL (result
);
2239 vr1
->result
= result
;
2241 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2244 /* At this point we should have all the things inserted that we have
2245 seen before, and we should never try inserting something that
2247 gcc_assert (!*slot
);
2249 free_reference (*slot
);
2255 /* Compute and return the hash value for nary operation VBO1. */
2258 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2260 inchash::hash hstate
;
2263 for (i
= 0; i
< vno1
->length
; ++i
)
2264 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2265 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2267 if (vno1
->length
== 2
2268 && commutative_tree_code (vno1
->opcode
)
2269 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2271 tree temp
= vno1
->op
[0];
2272 vno1
->op
[0] = vno1
->op
[1];
2276 hstate
.add_int (vno1
->opcode
);
2277 for (i
= 0; i
< vno1
->length
; ++i
)
2278 inchash::add_expr (vno1
->op
[i
], hstate
);
2280 return hstate
.end ();
2283 /* Compare nary operations VNO1 and VNO2 and return true if they are
2287 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2291 if (vno1
->hashcode
!= vno2
->hashcode
)
2294 if (vno1
->length
!= vno2
->length
)
2297 if (vno1
->opcode
!= vno2
->opcode
2298 || !types_compatible_p (vno1
->type
, vno2
->type
))
2301 for (i
= 0; i
< vno1
->length
; ++i
)
2302 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2308 /* Initialize VNO from the pieces provided. */
2311 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2312 enum tree_code code
, tree type
, tree
*ops
)
2315 vno
->length
= length
;
2317 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2320 /* Initialize VNO from OP. */
2323 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2327 vno
->opcode
= TREE_CODE (op
);
2328 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2329 vno
->type
= TREE_TYPE (op
);
2330 for (i
= 0; i
< vno
->length
; ++i
)
2331 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2334 /* Return the number of operands for a vn_nary ops structure from STMT. */
2337 vn_nary_length_from_stmt (gimple stmt
)
2339 switch (gimple_assign_rhs_code (stmt
))
2343 case VIEW_CONVERT_EXPR
:
2350 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2353 return gimple_num_ops (stmt
) - 1;
2357 /* Initialize VNO from STMT. */
2360 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2364 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2365 vno
->type
= gimple_expr_type (stmt
);
2366 switch (vno
->opcode
)
2370 case VIEW_CONVERT_EXPR
:
2372 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2377 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2378 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2379 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2383 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2384 for (i
= 0; i
< vno
->length
; ++i
)
2385 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2389 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2390 vno
->length
= gimple_num_ops (stmt
) - 1;
2391 for (i
= 0; i
< vno
->length
; ++i
)
2392 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2396 /* Compute the hashcode for VNO and look for it in the hash table;
2397 return the resulting value number if it exists in the hash table.
2398 Return NULL_TREE if it does not exist in the hash table or if the
2399 result field of the operation is NULL. VNRESULT will contain the
2400 vn_nary_op_t from the hashtable if it exists. */
2403 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2405 vn_nary_op_s
**slot
;
2410 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2411 slot
= current_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2413 if (!slot
&& current_info
== optimistic_info
)
2414 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2420 return (*slot
)->result
;
2423 /* Lookup a n-ary operation by its pieces and return the resulting value
2424 number if it exists in the hash table. Return NULL_TREE if it does
2425 not exist in the hash table or if the result field of the operation
2426 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2430 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2431 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2433 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2434 sizeof_vn_nary_op (length
));
2435 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2436 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2439 /* Lookup OP in the current hash table, and return the resulting value
2440 number if it exists in the hash table. Return NULL_TREE if it does
2441 not exist in the hash table or if the result field of the operation
2442 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2446 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2449 = XALLOCAVAR (struct vn_nary_op_s
,
2450 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2451 init_vn_nary_op_from_op (vno1
, op
);
2452 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2455 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2456 value number if it exists in the hash table. Return NULL_TREE if
2457 it does not exist in the hash table. VNRESULT will contain the
2458 vn_nary_op_t from the hashtable if it exists. */
2461 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2464 = XALLOCAVAR (struct vn_nary_op_s
,
2465 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2466 init_vn_nary_op_from_stmt (vno1
, stmt
);
2467 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2470 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2473 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2475 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2478 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2482 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2484 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2485 ¤t_info
->nary_obstack
);
2487 vno1
->value_id
= value_id
;
2488 vno1
->length
= length
;
2489 vno1
->result
= result
;
2494 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2495 VNO->HASHCODE first. */
2498 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
2501 vn_nary_op_s
**slot
;
2504 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2506 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2507 gcc_assert (!*slot
);
2513 /* Insert a n-ary operation into the current hash table using it's
2514 pieces. Return the vn_nary_op_t structure we created and put in
2518 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2519 tree type
, tree
*ops
,
2520 tree result
, unsigned int value_id
)
2522 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2523 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2524 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2527 /* Insert OP into the current hash table with a value number of
2528 RESULT. Return the vn_nary_op_t structure we created and put in
2532 vn_nary_op_insert (tree op
, tree result
)
2534 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2537 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2538 init_vn_nary_op_from_op (vno1
, op
);
2539 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2542 /* Insert the rhs of STMT into the current hash table with a value number of
2546 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2549 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2550 result
, VN_INFO (result
)->value_id
);
2551 init_vn_nary_op_from_stmt (vno1
, stmt
);
2552 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2555 /* Compute a hashcode for PHI operation VP1 and return it. */
2557 static inline hashval_t
2558 vn_phi_compute_hash (vn_phi_t vp1
)
2560 inchash::hash
hstate (vp1
->block
->index
);
2565 /* If all PHI arguments are constants we need to distinguish
2566 the PHI node via its type. */
2568 hstate
.merge_hash (vn_hash_type (type
));
2570 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2572 if (phi1op
== VN_TOP
)
2574 inchash::add_expr (phi1op
, hstate
);
2577 return hstate
.end ();
2580 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2583 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2585 if (vp1
->hashcode
!= vp2
->hashcode
)
2588 if (vp1
->block
== vp2
->block
)
2593 /* If the PHI nodes do not have compatible types
2594 they are not the same. */
2595 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2598 /* Any phi in the same block will have it's arguments in the
2599 same edge order, because of how we store phi nodes. */
2600 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2602 tree phi2op
= vp2
->phiargs
[i
];
2603 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2605 if (!expressions_equal_p (phi1op
, phi2op
))
2613 static vec
<tree
> shared_lookup_phiargs
;
2615 /* Lookup PHI in the current hash table, and return the resulting
2616 value number if it exists in the hash table. Return NULL_TREE if
2617 it does not exist in the hash table. */
2620 vn_phi_lookup (gimple phi
)
2623 struct vn_phi_s vp1
;
2626 shared_lookup_phiargs
.truncate (0);
2628 /* Canonicalize the SSA_NAME's to their value number. */
2629 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2631 tree def
= PHI_ARG_DEF (phi
, i
);
2632 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2633 shared_lookup_phiargs
.safe_push (def
);
2635 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2636 vp1
.phiargs
= shared_lookup_phiargs
;
2637 vp1
.block
= gimple_bb (phi
);
2638 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2639 slot
= current_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2641 if (!slot
&& current_info
== optimistic_info
)
2642 slot
= valid_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2646 return (*slot
)->result
;
2649 /* Insert PHI into the current hash table with a value number of
2653 vn_phi_insert (gimple phi
, tree result
)
2656 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2658 vec
<tree
> args
= vNULL
;
2660 /* Canonicalize the SSA_NAME's to their value number. */
2661 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2663 tree def
= PHI_ARG_DEF (phi
, i
);
2664 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2665 args
.safe_push (def
);
2667 vp1
->value_id
= VN_INFO (result
)->value_id
;
2668 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2669 vp1
->phiargs
= args
;
2670 vp1
->block
= gimple_bb (phi
);
2671 vp1
->result
= result
;
2672 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2674 slot
= current_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2676 /* Because we iterate over phi operations more than once, it's
2677 possible the slot might already exist here, hence no assert.*/
2683 /* Print set of components in strongly connected component SCC to OUT. */
2686 print_scc (FILE *out
, vec
<tree
> scc
)
2691 fprintf (out
, "SCC consists of:");
2692 FOR_EACH_VEC_ELT (scc
, i
, var
)
2695 print_generic_expr (out
, var
, 0);
2697 fprintf (out
, "\n");
2700 /* Set the value number of FROM to TO, return true if it has changed
2704 set_ssa_val_to (tree from
, tree to
)
2706 tree currval
= SSA_VAL (from
);
2707 HOST_WIDE_INT toff
, coff
;
2709 /* The only thing we allow as value numbers are ssa_names
2710 and invariants. So assert that here. We don't allow VN_TOP
2711 as visiting a stmt should produce a value-number other than
2713 ??? Still VN_TOP can happen for unreachable code, so force
2714 it to varying in that case. Not all code is prepared to
2715 get VN_TOP on valueization. */
2718 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2719 fprintf (dump_file
, "Forcing value number to varying on "
2720 "receiving VN_TOP\n");
2724 gcc_assert (to
!= NULL_TREE
2725 && (TREE_CODE (to
) == SSA_NAME
2726 || is_gimple_min_invariant (to
)));
2730 if (currval
== from
)
2732 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2734 fprintf (dump_file
, "Not changing value number of ");
2735 print_generic_expr (dump_file
, from
, 0);
2736 fprintf (dump_file
, " from VARYING to ");
2737 print_generic_expr (dump_file
, to
, 0);
2738 fprintf (dump_file
, "\n");
2742 else if (TREE_CODE (to
) == SSA_NAME
2743 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2749 fprintf (dump_file
, "Setting value number of ");
2750 print_generic_expr (dump_file
, from
, 0);
2751 fprintf (dump_file
, " to ");
2752 print_generic_expr (dump_file
, to
, 0);
2756 && !operand_equal_p (currval
, to
, 0)
2757 /* ??? For addresses involving volatile objects or types operand_equal_p
2758 does not reliably detect ADDR_EXPRs as equal. We know we are only
2759 getting invariant gimple addresses here, so can use
2760 get_addr_base_and_unit_offset to do this comparison. */
2761 && !(TREE_CODE (currval
) == ADDR_EXPR
2762 && TREE_CODE (to
) == ADDR_EXPR
2763 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2764 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2767 VN_INFO (from
)->valnum
= to
;
2768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2769 fprintf (dump_file
, " (changed)\n");
2772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2773 fprintf (dump_file
, "\n");
2777 /* Mark as processed all the definitions in the defining stmt of USE, or
2781 mark_use_processed (tree use
)
2785 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2787 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2789 VN_INFO (use
)->use_processed
= true;
2793 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2795 tree def
= DEF_FROM_PTR (defp
);
2797 VN_INFO (def
)->use_processed
= true;
2801 /* Set all definitions in STMT to value number to themselves.
2802 Return true if a value number changed. */
2805 defs_to_varying (gimple stmt
)
2807 bool changed
= false;
2811 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2813 tree def
= DEF_FROM_PTR (defp
);
2814 changed
|= set_ssa_val_to (def
, def
);
2819 static bool expr_has_constants (tree expr
);
2821 /* Visit a copy between LHS and RHS, return true if the value number
2825 visit_copy (tree lhs
, tree rhs
)
2827 /* The copy may have a more interesting constant filled expression
2828 (we don't, since we know our RHS is just an SSA name). */
2829 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2830 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2832 /* And finally valueize. */
2833 rhs
= SSA_VAL (rhs
);
2835 return set_ssa_val_to (lhs
, rhs
);
2838 /* Visit a nary operator RHS, value number it, and return true if the
2839 value number of LHS has changed as a result. */
2842 visit_nary_op (tree lhs
, gimple stmt
)
2844 bool changed
= false;
2845 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2848 changed
= set_ssa_val_to (lhs
, result
);
2851 changed
= set_ssa_val_to (lhs
, lhs
);
2852 vn_nary_op_insert_stmt (stmt
, lhs
);
2858 /* Visit a call STMT storing into LHS. Return true if the value number
2859 of the LHS has changed as a result. */
2862 visit_reference_op_call (tree lhs
, gimple stmt
)
2864 bool changed
= false;
2865 struct vn_reference_s vr1
;
2866 vn_reference_t vnresult
= NULL
;
2867 tree vdef
= gimple_vdef (stmt
);
2869 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2870 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2873 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
2876 if (vnresult
->result_vdef
&& vdef
)
2877 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2879 if (!vnresult
->result
&& lhs
)
2880 vnresult
->result
= lhs
;
2882 if (vnresult
->result
&& lhs
)
2884 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2886 if (VN_INFO (vnresult
->result
)->has_constants
)
2887 VN_INFO (lhs
)->has_constants
= true;
2893 vn_reference_s
**slot
;
2895 changed
|= set_ssa_val_to (vdef
, vdef
);
2897 changed
|= set_ssa_val_to (lhs
, lhs
);
2898 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2899 vr2
->vuse
= vr1
.vuse
;
2900 /* As we are not walking the virtual operand chain we know the
2901 shared_lookup_references are still original so we can re-use
2903 vr2
->operands
= vr1
.operands
.copy ();
2904 vr2
->type
= vr1
.type
;
2906 vr2
->hashcode
= vr1
.hashcode
;
2908 vr2
->result_vdef
= vdef
;
2909 slot
= current_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
2911 gcc_assert (!*slot
);
2918 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2919 and return true if the value number of the LHS has changed as a result. */
2922 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2924 bool changed
= false;
2928 last_vuse
= gimple_vuse (stmt
);
2929 last_vuse_ptr
= &last_vuse
;
2930 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2931 default_vn_walk_kind
, NULL
);
2932 last_vuse_ptr
= NULL
;
2934 /* We handle type-punning through unions by value-numbering based
2935 on offset and size of the access. Be prepared to handle a
2936 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2938 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2940 /* We will be setting the value number of lhs to the value number
2941 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2942 So first simplify and lookup this expression to see if it
2943 is already available. */
2944 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2945 if ((CONVERT_EXPR_P (val
)
2946 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2947 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2949 tree tem
= vn_get_expr_for (TREE_OPERAND (val
, 0));
2950 if ((CONVERT_EXPR_P (tem
)
2951 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2952 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2953 TREE_TYPE (val
), tem
)))
2957 if (!is_gimple_min_invariant (val
)
2958 && TREE_CODE (val
) != SSA_NAME
)
2959 result
= vn_nary_op_lookup (val
, NULL
);
2960 /* If the expression is not yet available, value-number lhs to
2961 a new SSA_NAME we create. */
2964 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2966 /* Initialize value-number information properly. */
2967 VN_INFO_GET (result
)->valnum
= result
;
2968 VN_INFO (result
)->value_id
= get_next_value_id ();
2969 VN_INFO (result
)->expr
= val
;
2970 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2971 VN_INFO (result
)->needs_insertion
= true;
2972 /* As all "inserted" statements are singleton SCCs, insert
2973 to the valid table. This is strictly needed to
2974 avoid re-generating new value SSA_NAMEs for the same
2975 expression during SCC iteration over and over (the
2976 optimistic table gets cleared after each iteration).
2977 We do not need to insert into the optimistic table, as
2978 lookups there will fall back to the valid table. */
2979 if (current_info
== optimistic_info
)
2981 current_info
= valid_info
;
2982 vn_nary_op_insert (val
, result
);
2983 current_info
= optimistic_info
;
2986 vn_nary_op_insert (val
, result
);
2987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2989 fprintf (dump_file
, "Inserting name ");
2990 print_generic_expr (dump_file
, result
, 0);
2991 fprintf (dump_file
, " for expression ");
2992 print_generic_expr (dump_file
, val
, 0);
2993 fprintf (dump_file
, "\n");
3000 changed
= set_ssa_val_to (lhs
, result
);
3001 if (TREE_CODE (result
) == SSA_NAME
3002 && VN_INFO (result
)->has_constants
)
3004 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
3005 VN_INFO (lhs
)->has_constants
= true;
3010 changed
= set_ssa_val_to (lhs
, lhs
);
3011 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
3018 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3019 and return true if the value number of the LHS has changed as a result. */
3022 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
3024 bool changed
= false;
3025 vn_reference_t vnresult
= NULL
;
3026 tree result
, assign
;
3027 bool resultsame
= false;
3028 tree vuse
= gimple_vuse (stmt
);
3029 tree vdef
= gimple_vdef (stmt
);
3031 /* First we want to lookup using the *vuses* from the store and see
3032 if there the last store to this location with the same address
3035 The vuses represent the memory state before the store. If the
3036 memory state, address, and value of the store is the same as the
3037 last store to this location, then this store will produce the
3038 same memory state as that store.
3040 In this case the vdef versions for this store are value numbered to those
3041 vuse versions, since they represent the same memory state after
3044 Otherwise, the vdefs for the store are used when inserting into
3045 the table, since the store generates a new memory state. */
3047 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
3051 if (TREE_CODE (result
) == SSA_NAME
)
3052 result
= SSA_VAL (result
);
3053 if (TREE_CODE (op
) == SSA_NAME
)
3055 resultsame
= expressions_equal_p (result
, op
);
3058 if ((!result
|| !resultsame
)
3059 /* Only perform the following when being called from PRE
3060 which embeds tail merging. */
3061 && default_vn_walk_kind
== VN_WALK
)
3063 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3064 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
3067 VN_INFO (vdef
)->use_processed
= true;
3068 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3072 if (!result
|| !resultsame
)
3074 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3076 fprintf (dump_file
, "No store match\n");
3077 fprintf (dump_file
, "Value numbering store ");
3078 print_generic_expr (dump_file
, lhs
, 0);
3079 fprintf (dump_file
, " to ");
3080 print_generic_expr (dump_file
, op
, 0);
3081 fprintf (dump_file
, "\n");
3083 /* Have to set value numbers before insert, since insert is
3084 going to valueize the references in-place. */
3087 changed
|= set_ssa_val_to (vdef
, vdef
);
3090 /* Do not insert structure copies into the tables. */
3091 if (is_gimple_min_invariant (op
)
3092 || is_gimple_reg (op
))
3093 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3095 /* Only perform the following when being called from PRE
3096 which embeds tail merging. */
3097 if (default_vn_walk_kind
== VN_WALK
)
3099 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3100 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3105 /* We had a match, so value number the vdef to have the value
3106 number of the vuse it came from. */
3108 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3109 fprintf (dump_file
, "Store matched earlier value,"
3110 "value numbering store vdefs to matching vuses.\n");
3112 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3118 /* Visit and value number PHI, return true if the value number
3122 visit_phi (gimple phi
)
3124 bool changed
= false;
3126 tree sameval
= VN_TOP
;
3127 bool allsame
= true;
3129 /* TODO: We could check for this in init_sccvn, and replace this
3130 with a gcc_assert. */
3131 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3132 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3134 /* See if all non-TOP arguments have the same value. TOP is
3135 equivalent to everything, so we can ignore it. */
3138 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3139 if (e
->flags
& EDGE_EXECUTABLE
)
3141 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3143 if (TREE_CODE (def
) == SSA_NAME
)
3144 def
= SSA_VAL (def
);
3147 if (sameval
== VN_TOP
)
3153 if (!expressions_equal_p (def
, sameval
))
3161 /* If all value numbered to the same value, the phi node has that
3164 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3166 /* Otherwise, see if it is equivalent to a phi node in this block. */
3167 result
= vn_phi_lookup (phi
);
3169 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3172 vn_phi_insert (phi
, PHI_RESULT (phi
));
3173 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3174 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3175 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3181 /* Return true if EXPR contains constants. */
3184 expr_has_constants (tree expr
)
3186 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3189 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3192 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3193 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3194 /* Constants inside reference ops are rarely interesting, but
3195 it can take a lot of looking to find them. */
3197 case tcc_declaration
:
3200 return is_gimple_min_invariant (expr
);
3205 /* Return true if STMT contains constants. */
3208 stmt_has_constants (gimple stmt
)
3212 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3215 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3217 case GIMPLE_TERNARY_RHS
:
3218 tem
= gimple_assign_rhs3 (stmt
);
3219 if (TREE_CODE (tem
) == SSA_NAME
)
3220 tem
= SSA_VAL (tem
);
3221 if (is_gimple_min_invariant (tem
))
3225 case GIMPLE_BINARY_RHS
:
3226 tem
= gimple_assign_rhs2 (stmt
);
3227 if (TREE_CODE (tem
) == SSA_NAME
)
3228 tem
= SSA_VAL (tem
);
3229 if (is_gimple_min_invariant (tem
))
3233 case GIMPLE_SINGLE_RHS
:
3234 /* Constants inside reference ops are rarely interesting, but
3235 it can take a lot of looking to find them. */
3236 case GIMPLE_UNARY_RHS
:
3237 tem
= gimple_assign_rhs1 (stmt
);
3238 if (TREE_CODE (tem
) == SSA_NAME
)
3239 tem
= SSA_VAL (tem
);
3240 return is_gimple_min_invariant (tem
);
3248 /* Simplify the binary expression RHS, and return the result if
3252 simplify_binary_expression (gimple stmt
)
3254 tree result
= NULL_TREE
;
3255 tree op0
= gimple_assign_rhs1 (stmt
);
3256 tree op1
= gimple_assign_rhs2 (stmt
);
3257 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3259 /* This will not catch every single case we could combine, but will
3260 catch those with constants. The goal here is to simultaneously
3261 combine constants between expressions, but avoid infinite
3262 expansion of expressions during simplification. */
3263 op0
= vn_valueize (op0
);
3264 if (TREE_CODE (op0
) == SSA_NAME
3265 && (VN_INFO (op0
)->has_constants
3266 || TREE_CODE_CLASS (code
) == tcc_comparison
3267 || code
== COMPLEX_EXPR
))
3268 op0
= vn_get_expr_for (op0
);
3270 op1
= vn_valueize (op1
);
3271 if (TREE_CODE (op1
) == SSA_NAME
3272 && (VN_INFO (op1
)->has_constants
3273 || code
== COMPLEX_EXPR
))
3274 op1
= vn_get_expr_for (op1
);
3276 /* Pointer plus constant can be represented as invariant address.
3277 Do so to allow further propatation, see also tree forwprop. */
3278 if (code
== POINTER_PLUS_EXPR
3279 && tree_fits_uhwi_p (op1
)
3280 && TREE_CODE (op0
) == ADDR_EXPR
3281 && is_gimple_min_invariant (op0
))
3282 return build_invariant_address (TREE_TYPE (op0
),
3283 TREE_OPERAND (op0
, 0),
3284 tree_to_uhwi (op1
));
3286 /* Avoid folding if nothing changed. */
3287 if (op0
== gimple_assign_rhs1 (stmt
)
3288 && op1
== gimple_assign_rhs2 (stmt
))
3291 fold_defer_overflow_warnings ();
3293 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3295 STRIP_USELESS_TYPE_CONVERSION (result
);
3297 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3300 /* Make sure result is not a complex expression consisting
3301 of operators of operators (IE (a + b) + (a + c))
3302 Otherwise, we will end up with unbounded expressions if
3303 fold does anything at all. */
3304 if (result
&& valid_gimple_rhs_p (result
))
3310 /* Simplify the unary expression RHS, and return the result if
3314 simplify_unary_expression (gimple stmt
)
3316 tree result
= NULL_TREE
;
3317 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3318 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3320 /* We handle some tcc_reference codes here that are all
3321 GIMPLE_ASSIGN_SINGLE codes. */
3322 if (code
== REALPART_EXPR
3323 || code
== IMAGPART_EXPR
3324 || code
== VIEW_CONVERT_EXPR
3325 || code
== BIT_FIELD_REF
)
3326 op0
= TREE_OPERAND (op0
, 0);
3329 op0
= vn_valueize (op0
);
3330 if (TREE_CODE (op0
) == SSA_NAME
)
3332 if (VN_INFO (op0
)->has_constants
)
3333 op0
= vn_get_expr_for (op0
);
3334 else if (CONVERT_EXPR_CODE_P (code
)
3335 || code
== REALPART_EXPR
3336 || code
== IMAGPART_EXPR
3337 || code
== VIEW_CONVERT_EXPR
3338 || code
== BIT_FIELD_REF
)
3340 /* We want to do tree-combining on conversion-like expressions.
3341 Make sure we feed only SSA_NAMEs or constants to fold though. */
3342 tree tem
= vn_get_expr_for (op0
);
3343 if (UNARY_CLASS_P (tem
)
3344 || BINARY_CLASS_P (tem
)
3345 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3346 || TREE_CODE (tem
) == SSA_NAME
3347 || TREE_CODE (tem
) == CONSTRUCTOR
3348 || is_gimple_min_invariant (tem
))
3353 /* Avoid folding if nothing changed, but remember the expression. */
3354 if (op0
== orig_op0
)
3357 if (code
== BIT_FIELD_REF
)
3359 tree rhs
= gimple_assign_rhs1 (stmt
);
3360 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3361 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3364 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3367 STRIP_USELESS_TYPE_CONVERSION (result
);
3368 if (valid_gimple_rhs_p (result
))
3375 /* Try to simplify RHS using equivalences and constant folding. */
3378 try_to_simplify (gimple stmt
)
3380 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3383 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3384 in this case, there is no point in doing extra work. */
3385 if (code
== SSA_NAME
)
3388 /* First try constant folding based on our current lattice. */
3389 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3391 && (TREE_CODE (tem
) == SSA_NAME
3392 || is_gimple_min_invariant (tem
)))
3395 /* If that didn't work try combining multiple statements. */
3396 switch (TREE_CODE_CLASS (code
))
3399 /* Fallthrough for some unary codes that can operate on registers. */
3400 if (!(code
== REALPART_EXPR
3401 || code
== IMAGPART_EXPR
3402 || code
== VIEW_CONVERT_EXPR
3403 || code
== BIT_FIELD_REF
))
3405 /* We could do a little more with unary ops, if they expand
3406 into binary ops, but it's debatable whether it is worth it. */
3408 return simplify_unary_expression (stmt
);
3410 case tcc_comparison
:
3412 return simplify_binary_expression (stmt
);
3421 /* Visit and value number USE, return true if the value number
3425 visit_use (tree use
)
3427 bool changed
= false;
3428 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3430 mark_use_processed (use
);
3432 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3433 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3434 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3436 fprintf (dump_file
, "Value numbering ");
3437 print_generic_expr (dump_file
, use
, 0);
3438 fprintf (dump_file
, " stmt = ");
3439 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3442 /* Handle uninitialized uses. */
3443 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3444 changed
= set_ssa_val_to (use
, use
);
3447 if (gimple_code (stmt
) == GIMPLE_PHI
)
3448 changed
= visit_phi (stmt
);
3449 else if (gimple_has_volatile_ops (stmt
))
3450 changed
= defs_to_varying (stmt
);
3451 else if (is_gimple_assign (stmt
))
3453 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3454 tree lhs
= gimple_assign_lhs (stmt
);
3455 tree rhs1
= gimple_assign_rhs1 (stmt
);
3458 /* Shortcut for copies. Simplifying copies is pointless,
3459 since we copy the expression and value they represent. */
3460 if (code
== SSA_NAME
3461 && TREE_CODE (lhs
) == SSA_NAME
)
3463 changed
= visit_copy (lhs
, rhs1
);
3466 simplified
= try_to_simplify (stmt
);
3469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3471 fprintf (dump_file
, "RHS ");
3472 print_gimple_expr (dump_file
, stmt
, 0, 0);
3473 fprintf (dump_file
, " simplified to ");
3474 print_generic_expr (dump_file
, simplified
, 0);
3475 if (TREE_CODE (lhs
) == SSA_NAME
)
3476 fprintf (dump_file
, " has constants %d\n",
3477 expr_has_constants (simplified
));
3479 fprintf (dump_file
, "\n");
3482 /* Setting value numbers to constants will occasionally
3483 screw up phi congruence because constants are not
3484 uniquely associated with a single ssa name that can be
3487 && is_gimple_min_invariant (simplified
)
3488 && TREE_CODE (lhs
) == SSA_NAME
)
3490 VN_INFO (lhs
)->expr
= simplified
;
3491 VN_INFO (lhs
)->has_constants
= true;
3492 changed
= set_ssa_val_to (lhs
, simplified
);
3496 && TREE_CODE (simplified
) == SSA_NAME
3497 && TREE_CODE (lhs
) == SSA_NAME
)
3499 changed
= visit_copy (lhs
, simplified
);
3502 else if (simplified
)
3504 if (TREE_CODE (lhs
) == SSA_NAME
)
3506 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3507 /* We have to unshare the expression or else
3508 valuizing may change the IL stream. */
3509 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3512 else if (stmt_has_constants (stmt
)
3513 && TREE_CODE (lhs
) == SSA_NAME
)
3514 VN_INFO (lhs
)->has_constants
= true;
3515 else if (TREE_CODE (lhs
) == SSA_NAME
)
3517 /* We reset expr and constantness here because we may
3518 have been value numbering optimistically, and
3519 iterating. They may become non-constant in this case,
3520 even if they were optimistically constant. */
3522 VN_INFO (lhs
)->has_constants
= false;
3523 VN_INFO (lhs
)->expr
= NULL_TREE
;
3526 if ((TREE_CODE (lhs
) == SSA_NAME
3527 /* We can substitute SSA_NAMEs that are live over
3528 abnormal edges with their constant value. */
3529 && !(gimple_assign_copy_p (stmt
)
3530 && is_gimple_min_invariant (rhs1
))
3532 && is_gimple_min_invariant (simplified
))
3533 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3534 /* Stores or copies from SSA_NAMEs that are live over
3535 abnormal edges are a problem. */
3536 || (code
== SSA_NAME
3537 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3538 changed
= defs_to_varying (stmt
);
3539 else if (REFERENCE_CLASS_P (lhs
)
3541 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3542 else if (TREE_CODE (lhs
) == SSA_NAME
)
3544 if ((gimple_assign_copy_p (stmt
)
3545 && is_gimple_min_invariant (rhs1
))
3547 && is_gimple_min_invariant (simplified
)))
3549 VN_INFO (lhs
)->has_constants
= true;
3551 changed
= set_ssa_val_to (lhs
, simplified
);
3553 changed
= set_ssa_val_to (lhs
, rhs1
);
3557 /* First try to lookup the simplified expression. */
3560 enum gimple_rhs_class rhs_class
;
3563 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3564 if ((rhs_class
== GIMPLE_UNARY_RHS
3565 || rhs_class
== GIMPLE_BINARY_RHS
3566 || rhs_class
== GIMPLE_TERNARY_RHS
)
3567 && valid_gimple_rhs_p (simplified
))
3569 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3572 changed
= set_ssa_val_to (lhs
, result
);
3578 /* Otherwise visit the original statement. */
3579 switch (vn_get_stmt_kind (stmt
))
3582 changed
= visit_nary_op (lhs
, stmt
);
3585 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3588 changed
= defs_to_varying (stmt
);
3594 changed
= defs_to_varying (stmt
);
3596 else if (is_gimple_call (stmt
))
3598 tree lhs
= gimple_call_lhs (stmt
);
3599 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3601 /* Try constant folding based on our current lattice. */
3602 tree simplified
= gimple_fold_stmt_to_constant_1 (stmt
,
3606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3608 fprintf (dump_file
, "call ");
3609 print_gimple_expr (dump_file
, stmt
, 0, 0);
3610 fprintf (dump_file
, " simplified to ");
3611 print_generic_expr (dump_file
, simplified
, 0);
3612 if (TREE_CODE (lhs
) == SSA_NAME
)
3613 fprintf (dump_file
, " has constants %d\n",
3614 expr_has_constants (simplified
));
3616 fprintf (dump_file
, "\n");
3619 /* Setting value numbers to constants will occasionally
3620 screw up phi congruence because constants are not
3621 uniquely associated with a single ssa name that can be
3624 && is_gimple_min_invariant (simplified
))
3626 VN_INFO (lhs
)->expr
= simplified
;
3627 VN_INFO (lhs
)->has_constants
= true;
3628 changed
= set_ssa_val_to (lhs
, simplified
);
3629 if (gimple_vdef (stmt
))
3630 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3631 gimple_vuse (stmt
));
3635 && TREE_CODE (simplified
) == SSA_NAME
)
3637 changed
= visit_copy (lhs
, simplified
);
3638 if (gimple_vdef (stmt
))
3639 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3640 gimple_vuse (stmt
));
3645 if (stmt_has_constants (stmt
))
3646 VN_INFO (lhs
)->has_constants
= true;
3649 /* We reset expr and constantness here because we may
3650 have been value numbering optimistically, and
3651 iterating. They may become non-constant in this case,
3652 even if they were optimistically constant. */
3653 VN_INFO (lhs
)->has_constants
= false;
3654 VN_INFO (lhs
)->expr
= NULL_TREE
;
3657 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3659 changed
= defs_to_varying (stmt
);
3665 if (!gimple_call_internal_p (stmt
)
3666 && (/* Calls to the same function with the same vuse
3667 and the same operands do not necessarily return the same
3668 value, unless they're pure or const. */
3669 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3670 /* If calls have a vdef, subsequent calls won't have
3671 the same incoming vuse. So, if 2 calls with vdef have the
3672 same vuse, we know they're not subsequent.
3673 We can value number 2 calls to the same function with the
3674 same vuse and the same operands which are not subsequent
3675 the same, because there is no code in the program that can
3676 compare the 2 values... */
3677 || (gimple_vdef (stmt
)
3678 /* ... unless the call returns a pointer which does
3679 not alias with anything else. In which case the
3680 information that the values are distinct are encoded
3682 && !(gimple_call_return_flags (stmt
) & ERF_NOALIAS
)
3683 /* Only perform the following when being called from PRE
3684 which embeds tail merging. */
3685 && default_vn_walk_kind
== VN_WALK
)))
3686 changed
= visit_reference_op_call (lhs
, stmt
);
3688 changed
= defs_to_varying (stmt
);
3691 changed
= defs_to_varying (stmt
);
3697 /* Compare two operands by reverse postorder index */
3700 compare_ops (const void *pa
, const void *pb
)
3702 const tree opa
= *((const tree
*)pa
);
3703 const tree opb
= *((const tree
*)pb
);
3704 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3705 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3709 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3710 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3711 else if (gimple_nop_p (opstmta
))
3713 else if (gimple_nop_p (opstmtb
))
3716 bba
= gimple_bb (opstmta
);
3717 bbb
= gimple_bb (opstmtb
);
3720 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3728 if (gimple_code (opstmta
) == GIMPLE_PHI
3729 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3730 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3731 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3733 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3735 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3736 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3738 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3740 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3743 /* Sort an array containing members of a strongly connected component
3744 SCC so that the members are ordered by RPO number.
3745 This means that when the sort is complete, iterating through the
3746 array will give you the members in RPO order. */
3749 sort_scc (vec
<tree
> scc
)
3751 scc
.qsort (compare_ops
);
3754 /* Insert the no longer used nary ONARY to the hash INFO. */
3757 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3759 size_t size
= sizeof_vn_nary_op (onary
->length
);
3760 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3761 &info
->nary_obstack
);
3762 memcpy (nary
, onary
, size
);
3763 vn_nary_op_insert_into (nary
, info
->nary
, false);
3766 /* Insert the no longer used phi OPHI to the hash INFO. */
3769 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3771 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3773 memcpy (phi
, ophi
, sizeof (*phi
));
3774 ophi
->phiargs
.create (0);
3775 slot
= info
->phis
->find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3776 gcc_assert (!*slot
);
3780 /* Insert the no longer used reference OREF to the hash INFO. */
3783 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3786 vn_reference_s
**slot
;
3787 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3788 memcpy (ref
, oref
, sizeof (*ref
));
3789 oref
->operands
.create (0);
3790 slot
= info
->references
->find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3792 free_reference (*slot
);
3796 /* Process a strongly connected component in the SSA graph. */
3799 process_scc (vec
<tree
> scc
)
3803 unsigned int iterations
= 0;
3804 bool changed
= true;
3805 vn_nary_op_iterator_type hin
;
3806 vn_phi_iterator_type hip
;
3807 vn_reference_iterator_type hir
;
3812 /* If the SCC has a single member, just visit it. */
3813 if (scc
.length () == 1)
3816 if (VN_INFO (use
)->use_processed
)
3818 /* We need to make sure it doesn't form a cycle itself, which can
3819 happen for self-referential PHI nodes. In that case we would
3820 end up inserting an expression with VN_TOP operands into the
3821 valid table which makes us derive bogus equivalences later.
3822 The cheapest way to check this is to assume it for all PHI nodes. */
3823 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3824 /* Fallthru to iteration. */ ;
3832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3833 print_scc (dump_file
, scc
);
3835 /* Iterate over the SCC with the optimistic table until it stops
3837 current_info
= optimistic_info
;
3842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3843 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3844 /* As we are value-numbering optimistically we have to
3845 clear the expression tables and the simplified expressions
3846 in each iteration until we converge. */
3847 optimistic_info
->nary
->empty ();
3848 optimistic_info
->phis
->empty ();
3849 optimistic_info
->references
->empty ();
3850 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3851 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3852 empty_alloc_pool (optimistic_info
->phis_pool
);
3853 empty_alloc_pool (optimistic_info
->references_pool
);
3854 FOR_EACH_VEC_ELT (scc
, i
, var
)
3855 VN_INFO (var
)->expr
= NULL_TREE
;
3856 FOR_EACH_VEC_ELT (scc
, i
, var
)
3857 changed
|= visit_use (var
);
3860 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3861 fprintf (dump_file
, "Processing SCC needed %d iterations\n", iterations
);
3862 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3864 /* Finally, copy the contents of the no longer used optimistic
3865 table to the valid table. */
3866 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3867 copy_nary (nary
, valid_info
);
3868 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3869 copy_phi (phi
, valid_info
);
3870 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->references
,
3871 ref
, vn_reference_t
, hir
)
3872 copy_reference (ref
, valid_info
);
3874 current_info
= valid_info
;
3878 /* Pop the components of the found SCC for NAME off the SCC stack
3879 and process them. Returns true if all went well, false if
3880 we run into resource limits. */
3883 extract_and_process_scc_for_name (tree name
)
3888 /* Found an SCC, pop the components off the SCC stack and
3892 x
= sccstack
.pop ();
3894 VN_INFO (x
)->on_sccstack
= false;
3896 } while (x
!= name
);
3898 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3900 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3903 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3904 "SCC size %u exceeding %u\n", scc
.length (),
3905 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3910 if (scc
.length () > 1)
3918 /* Depth first search on NAME to discover and process SCC's in the SSA
3920 Execution of this algorithm relies on the fact that the SCC's are
3921 popped off the stack in topological order.
3922 Returns true if successful, false if we stopped processing SCC's due
3923 to resource constraints. */
3928 vec
<ssa_op_iter
> itervec
= vNULL
;
3929 vec
<tree
> namevec
= vNULL
;
3930 use_operand_p usep
= NULL
;
3937 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3938 VN_INFO (name
)->visited
= true;
3939 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3941 sccstack
.safe_push (name
);
3942 VN_INFO (name
)->on_sccstack
= true;
3943 defstmt
= SSA_NAME_DEF_STMT (name
);
3945 /* Recursively DFS on our operands, looking for SCC's. */
3946 if (!gimple_nop_p (defstmt
))
3948 /* Push a new iterator. */
3949 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3950 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3952 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3955 clear_and_done_ssa_iter (&iter
);
3959 /* If we are done processing uses of a name, go up the stack
3960 of iterators and process SCCs as we found them. */
3961 if (op_iter_done (&iter
))
3963 /* See if we found an SCC. */
3964 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3965 if (!extract_and_process_scc_for_name (name
))
3972 /* Check if we are done. */
3973 if (namevec
.is_empty ())
3980 /* Restore the last use walker and continue walking there. */
3982 name
= namevec
.pop ();
3983 memcpy (&iter
, &itervec
.last (),
3984 sizeof (ssa_op_iter
));
3986 goto continue_walking
;
3989 use
= USE_FROM_PTR (usep
);
3991 /* Since we handle phi nodes, we will sometimes get
3992 invariants in the use expression. */
3993 if (TREE_CODE (use
) == SSA_NAME
)
3995 if (! (VN_INFO (use
)->visited
))
3997 /* Recurse by pushing the current use walking state on
3998 the stack and starting over. */
3999 itervec
.safe_push (iter
);
4000 namevec
.safe_push (name
);
4005 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
4006 VN_INFO (use
)->low
);
4008 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
4009 && VN_INFO (use
)->on_sccstack
)
4011 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
4012 VN_INFO (name
)->low
);
4016 usep
= op_iter_next_use (&iter
);
4020 /* Allocate a value number table. */
4023 allocate_vn_table (vn_tables_t table
)
4025 table
->phis
= new vn_phi_table_type (23);
4026 table
->nary
= new vn_nary_op_table_type (23);
4027 table
->references
= new vn_reference_table_type (23);
4029 gcc_obstack_init (&table
->nary_obstack
);
4030 table
->phis_pool
= create_alloc_pool ("VN phis",
4031 sizeof (struct vn_phi_s
),
4033 table
->references_pool
= create_alloc_pool ("VN references",
4034 sizeof (struct vn_reference_s
),
4038 /* Free a value number table. */
4041 free_vn_table (vn_tables_t table
)
4047 delete table
->references
;
4048 table
->references
= NULL
;
4049 obstack_free (&table
->nary_obstack
, NULL
);
4050 free_alloc_pool (table
->phis_pool
);
4051 free_alloc_pool (table
->references_pool
);
4059 int *rpo_numbers_temp
;
4061 calculate_dominance_info (CDI_DOMINATORS
);
4062 sccstack
.create (0);
4063 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
4065 constant_value_ids
= BITMAP_ALLOC (NULL
);
4070 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
4071 /* VEC_alloc doesn't actually grow it to the right size, it just
4072 preallocates the space to do so. */
4073 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
4074 gcc_obstack_init (&vn_ssa_aux_obstack
);
4076 shared_lookup_phiargs
.create (0);
4077 shared_lookup_references
.create (0);
4078 rpo_numbers
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
4080 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
4081 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
4083 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4084 the i'th block in RPO order is bb. We want to map bb's to RPO
4085 numbers, so we need to rearrange this array. */
4086 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
4087 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
4089 XDELETE (rpo_numbers_temp
);
4091 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
4093 /* Create the VN_INFO structures, and initialize value numbers to
4095 for (i
= 0; i
< num_ssa_names
; i
++)
4097 tree name
= ssa_name (i
);
4100 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4101 VN_INFO (name
)->expr
= NULL_TREE
;
4102 VN_INFO (name
)->value_id
= 0;
4106 renumber_gimple_stmt_uids ();
4108 /* Create the valid and optimistic value numbering tables. */
4109 valid_info
= XCNEW (struct vn_tables_s
);
4110 allocate_vn_table (valid_info
);
4111 optimistic_info
= XCNEW (struct vn_tables_s
);
4112 allocate_vn_table (optimistic_info
);
4120 delete constant_to_value_id
;
4121 constant_to_value_id
= NULL
;
4122 BITMAP_FREE (constant_value_ids
);
4123 shared_lookup_phiargs
.release ();
4124 shared_lookup_references
.release ();
4125 XDELETEVEC (rpo_numbers
);
4127 for (i
= 0; i
< num_ssa_names
; i
++)
4129 tree name
= ssa_name (i
);
4131 && VN_INFO (name
)->needs_insertion
)
4132 release_ssa_name (name
);
4134 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4135 vn_ssa_aux_table
.release ();
4137 sccstack
.release ();
4138 free_vn_table (valid_info
);
4139 XDELETE (valid_info
);
4140 free_vn_table (optimistic_info
);
4141 XDELETE (optimistic_info
);
4144 /* Set *ID according to RESULT. */
4147 set_value_id_for_result (tree result
, unsigned int *id
)
4149 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4150 *id
= VN_INFO (result
)->value_id
;
4151 else if (result
&& is_gimple_min_invariant (result
))
4152 *id
= get_or_alloc_constant_value_id (result
);
4154 *id
= get_next_value_id ();
4157 /* Set the value ids in the valid hash tables. */
4160 set_hashtable_value_ids (void)
4162 vn_nary_op_iterator_type hin
;
4163 vn_phi_iterator_type hip
;
4164 vn_reference_iterator_type hir
;
4169 /* Now set the value ids of the things we had put in the hash
4172 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4173 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4175 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4176 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4178 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4180 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4183 class cond_dom_walker
: public dom_walker
4186 cond_dom_walker () : dom_walker (CDI_DOMINATORS
), fail (false) {}
4188 virtual void before_dom_children (basic_block
);
4194 cond_dom_walker::before_dom_children (basic_block bb
)
4202 /* If any of the predecessor edges that do not come from blocks dominated
4203 by us are still marked as possibly executable consider this block
4205 bool reachable
= bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
);
4206 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4207 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
4208 reachable
|= (e
->flags
& EDGE_EXECUTABLE
);
4210 /* If the block is not reachable all outgoing edges are not
4214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4215 fprintf (dump_file
, "Marking all outgoing edges of unreachable "
4216 "BB %d as not executable\n", bb
->index
);
4218 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4219 e
->flags
&= ~EDGE_EXECUTABLE
;
4223 gimple stmt
= last_stmt (bb
);
4227 enum gimple_code code
= gimple_code (stmt
);
4228 if (code
!= GIMPLE_COND
4229 && code
!= GIMPLE_SWITCH
4230 && code
!= GIMPLE_GOTO
)
4233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4235 fprintf (dump_file
, "Value-numbering operands of stmt ending BB %d: ",
4237 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4240 /* Value-number the last stmts SSA uses. */
4243 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
4244 if (VN_INFO (op
)->visited
== false
4251 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4252 if value-numbering can prove they are not reachable. Handling
4253 computed gotos is also possible. */
4259 tree lhs
= gimple_cond_lhs (stmt
);
4260 tree rhs
= gimple_cond_rhs (stmt
);
4261 /* Work hard in computing the condition and take into account
4262 the valueization of the defining stmt. */
4263 if (TREE_CODE (lhs
) == SSA_NAME
)
4264 lhs
= vn_get_expr_for (lhs
);
4265 if (TREE_CODE (rhs
) == SSA_NAME
)
4266 rhs
= vn_get_expr_for (rhs
);
4267 val
= fold_binary (gimple_cond_code (stmt
),
4268 boolean_type_node
, lhs
, rhs
);
4272 val
= gimple_switch_index (stmt
);
4275 val
= gimple_goto_dest (stmt
);
4283 edge taken
= find_taken_edge (bb
, vn_valueize (val
));
4287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4288 fprintf (dump_file
, "Marking all edges out of BB %d but (%d -> %d) as "
4289 "not executable\n", bb
->index
, bb
->index
, taken
->dest
->index
);
4291 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4293 e
->flags
&= ~EDGE_EXECUTABLE
;
4296 /* Do SCCVN. Returns true if it finished, false if we bailed out
4297 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4298 how we use the alias oracle walking during the VN process. */
4301 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4307 default_vn_walk_kind
= default_vn_walk_kind_
;
4310 current_info
= valid_info
;
4312 for (param
= DECL_ARGUMENTS (current_function_decl
);
4314 param
= DECL_CHAIN (param
))
4316 tree def
= ssa_default_def (cfun
, param
);
4319 VN_INFO (def
)->visited
= true;
4320 VN_INFO (def
)->valnum
= def
;
4324 /* Mark all edges as possibly executable. */
4325 FOR_ALL_BB_FN (bb
, cfun
)
4329 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4330 e
->flags
|= EDGE_EXECUTABLE
;
4333 /* Walk all blocks in dominator order, value-numbering the last stmts
4334 SSA uses and decide whether outgoing edges are not executable. */
4335 cond_dom_walker walker
;
4336 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4343 /* Value-number remaining SSA names. */
4344 for (i
= 1; i
< num_ssa_names
; ++i
)
4346 tree name
= ssa_name (i
);
4348 && VN_INFO (name
)->visited
== false
4349 && !has_zero_uses (name
))
4357 /* Initialize the value ids. */
4359 for (i
= 1; i
< num_ssa_names
; ++i
)
4361 tree name
= ssa_name (i
);
4365 info
= VN_INFO (name
);
4366 if (info
->valnum
== name
4367 || info
->valnum
== VN_TOP
)
4368 info
->value_id
= get_next_value_id ();
4369 else if (is_gimple_min_invariant (info
->valnum
))
4370 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4374 for (i
= 1; i
< num_ssa_names
; ++i
)
4376 tree name
= ssa_name (i
);
4380 info
= VN_INFO (name
);
4381 if (TREE_CODE (info
->valnum
) == SSA_NAME
4382 && info
->valnum
!= name
4383 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4384 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4387 set_hashtable_value_ids ();
4389 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4391 fprintf (dump_file
, "Value numbers:\n");
4392 for (i
= 0; i
< num_ssa_names
; i
++)
4394 tree name
= ssa_name (i
);
4396 && VN_INFO (name
)->visited
4397 && SSA_VAL (name
) != name
)
4399 print_generic_expr (dump_file
, name
, 0);
4400 fprintf (dump_file
, " = ");
4401 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4402 fprintf (dump_file
, "\n");
4410 /* Return the maximum value id we have ever seen. */
4413 get_max_value_id (void)
4415 return next_value_id
;
4418 /* Return the next unique value id. */
4421 get_next_value_id (void)
4423 return next_value_id
++;
4427 /* Compare two expressions E1 and E2 and return true if they are equal. */
4430 expressions_equal_p (tree e1
, tree e2
)
4432 /* The obvious case. */
4436 /* If only one of them is null, they cannot be equal. */
4440 /* Now perform the actual comparison. */
4441 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4442 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4449 /* Return true if the nary operation NARY may trap. This is a copy
4450 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4453 vn_nary_may_trap (vn_nary_op_t nary
)
4456 tree rhs2
= NULL_TREE
;
4457 bool honor_nans
= false;
4458 bool honor_snans
= false;
4459 bool fp_operation
= false;
4460 bool honor_trapv
= false;
4464 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4465 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4466 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4469 fp_operation
= FLOAT_TYPE_P (type
);
4472 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4473 honor_snans
= flag_signaling_nans
!= 0;
4475 else if (INTEGRAL_TYPE_P (type
)
4476 && TYPE_OVERFLOW_TRAPS (type
))
4479 if (nary
->length
>= 2)
4481 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4483 honor_nans
, honor_snans
, rhs2
,
4489 for (i
= 0; i
< nary
->length
; ++i
)
4490 if (tree_could_trap_p (nary
->op
[i
]))