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 (gcall
*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 (gcall
*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 (as_a
<gcall
*> (def_stmt
),
1635 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1636 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
1642 if (disambiguate_only
)
1645 base
= ao_ref_base (ref
);
1646 offset
= ref
->offset
;
1647 maxsize
= ref
->max_size
;
1649 /* If we cannot constrain the size of the reference we cannot
1650 test if anything kills it. */
1654 /* We can't deduce anything useful from clobbers. */
1655 if (gimple_clobber_p (def_stmt
))
1658 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1659 from that definition.
1661 if (is_gimple_reg_type (vr
->type
)
1662 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1663 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1664 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1665 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1667 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1669 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1670 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1671 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1672 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1673 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1675 && operand_equal_p (base
, base2
, 0)
1676 && offset2
<= offset
1677 && offset2
+ size2
>= offset
+ maxsize
)
1679 tree val
= build_zero_cst (vr
->type
);
1680 return vn_reference_lookup_or_insert_for_pieces
1681 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1685 /* 2) Assignment from an empty CONSTRUCTOR. */
1686 else if (is_gimple_reg_type (vr
->type
)
1687 && gimple_assign_single_p (def_stmt
)
1688 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1689 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1692 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1693 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1694 &offset2
, &size2
, &maxsize2
);
1696 && operand_equal_p (base
, base2
, 0)
1697 && offset2
<= offset
1698 && offset2
+ size2
>= offset
+ maxsize
)
1700 tree val
= build_zero_cst (vr
->type
);
1701 return vn_reference_lookup_or_insert_for_pieces
1702 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1706 /* 3) Assignment from a constant. We can use folds native encode/interpret
1707 routines to extract the assigned bits. */
1708 else if (vn_walk_kind
== VN_WALKREWRITE
1709 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1710 && ref
->size
== maxsize
1711 && maxsize
% BITS_PER_UNIT
== 0
1712 && offset
% BITS_PER_UNIT
== 0
1713 && is_gimple_reg_type (vr
->type
)
1714 && gimple_assign_single_p (def_stmt
)
1715 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1718 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1719 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1720 &offset2
, &size2
, &maxsize2
);
1722 && maxsize2
== size2
1723 && size2
% BITS_PER_UNIT
== 0
1724 && offset2
% BITS_PER_UNIT
== 0
1725 && operand_equal_p (base
, base2
, 0)
1726 && offset2
<= offset
1727 && offset2
+ size2
>= offset
+ maxsize
)
1729 /* We support up to 512-bit values (for V8DFmode). */
1730 unsigned char buffer
[64];
1733 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1734 buffer
, sizeof (buffer
));
1737 tree val
= native_interpret_expr (vr
->type
,
1739 + ((offset
- offset2
)
1741 ref
->size
/ BITS_PER_UNIT
);
1743 return vn_reference_lookup_or_insert_for_pieces
1744 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1749 /* 4) Assignment from an SSA name which definition we may be able
1750 to access pieces from. */
1751 else if (ref
->size
== maxsize
1752 && is_gimple_reg_type (vr
->type
)
1753 && gimple_assign_single_p (def_stmt
)
1754 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1756 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1757 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1758 if (is_gimple_assign (def_stmt2
)
1759 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1760 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1761 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1764 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1765 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1766 &offset2
, &size2
, &maxsize2
);
1767 off
= offset
- offset2
;
1769 && maxsize2
== size2
1770 && operand_equal_p (base
, base2
, 0)
1771 && offset2
<= offset
1772 && offset2
+ size2
>= offset
+ maxsize
)
1774 tree val
= NULL_TREE
;
1776 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1777 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1780 val
= gimple_assign_rhs1 (def_stmt2
);
1781 else if (off
== elsz
)
1782 val
= gimple_assign_rhs2 (def_stmt2
);
1784 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1787 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1788 unsigned i
= off
/ elsz
;
1789 if (i
< CONSTRUCTOR_NELTS (ctor
))
1791 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1792 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1794 if (TREE_CODE (TREE_TYPE (elt
->value
))
1801 return vn_reference_lookup_or_insert_for_pieces
1802 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1807 /* 5) For aggregate copies translate the reference through them if
1808 the copy kills ref. */
1809 else if (vn_walk_kind
== VN_WALKREWRITE
1810 && gimple_assign_single_p (def_stmt
)
1811 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1812 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1813 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1816 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1818 auto_vec
<vn_reference_op_s
> rhs
;
1819 vn_reference_op_t vro
;
1825 /* See if the assignment kills REF. */
1826 base2
= ao_ref_base (&lhs_ref
);
1827 offset2
= lhs_ref
.offset
;
1828 size2
= lhs_ref
.size
;
1829 maxsize2
= lhs_ref
.max_size
;
1831 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1833 || offset2
+ size2
< offset
+ maxsize
)
1836 /* Find the common base of ref and the lhs. lhs_ops already
1837 contains valueized operands for the lhs. */
1838 i
= vr
->operands
.length () - 1;
1839 j
= lhs_ops
.length () - 1;
1840 while (j
>= 0 && i
>= 0
1841 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1847 /* ??? The innermost op should always be a MEM_REF and we already
1848 checked that the assignment to the lhs kills vr. Thus for
1849 aggregate copies using char[] types the vn_reference_op_eq
1850 may fail when comparing types for compatibility. But we really
1851 don't care here - further lookups with the rewritten operands
1852 will simply fail if we messed up types too badly. */
1853 if (j
== 0 && i
>= 0
1854 && lhs_ops
[0].opcode
== MEM_REF
1855 && lhs_ops
[0].off
!= -1
1856 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1859 /* i now points to the first additional op.
1860 ??? LHS may not be completely contained in VR, one or more
1861 VIEW_CONVERT_EXPRs could be in its way. We could at least
1862 try handling outermost VIEW_CONVERT_EXPRs. */
1866 /* Now re-write REF to be based on the rhs of the assignment. */
1867 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1868 /* We need to pre-pend vr->operands[0..i] to rhs. */
1869 vec
<vn_reference_op_s
> old
= vr
->operands
;
1870 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1872 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1873 if (old
== shared_lookup_references
)
1874 shared_lookup_references
= vr
->operands
;
1877 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1878 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1879 vr
->operands
[i
+ 1 + j
] = *vro
;
1880 vr
->operands
= valueize_refs (vr
->operands
);
1881 if (old
== shared_lookup_references
)
1882 shared_lookup_references
= vr
->operands
;
1883 vr
->hashcode
= vn_reference_compute_hash (vr
);
1885 /* Adjust *ref from the new operands. */
1886 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1888 /* This can happen with bitfields. */
1889 if (ref
->size
!= r
.size
)
1893 /* Do not update last seen VUSE after translating. */
1894 last_vuse_ptr
= NULL
;
1896 /* Keep looking for the adjusted *REF / VR pair. */
1900 /* 6) For memcpy copies translate the reference through them if
1901 the copy kills ref. */
1902 else if (vn_walk_kind
== VN_WALKREWRITE
1903 && is_gimple_reg_type (vr
->type
)
1904 /* ??? Handle BCOPY as well. */
1905 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1906 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1907 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1908 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1909 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1910 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1911 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1912 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
1916 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1917 vn_reference_op_s op
;
1921 /* Only handle non-variable, addressable refs. */
1922 if (ref
->size
!= maxsize
1923 || offset
% BITS_PER_UNIT
!= 0
1924 || ref
->size
% BITS_PER_UNIT
!= 0)
1927 /* Extract a pointer base and an offset for the destination. */
1928 lhs
= gimple_call_arg (def_stmt
, 0);
1930 if (TREE_CODE (lhs
) == SSA_NAME
)
1931 lhs
= SSA_VAL (lhs
);
1932 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1934 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1938 if (TREE_CODE (tem
) == MEM_REF
1939 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1941 lhs
= TREE_OPERAND (tem
, 0);
1942 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1944 else if (DECL_P (tem
))
1945 lhs
= build_fold_addr_expr (tem
);
1949 if (TREE_CODE (lhs
) != SSA_NAME
1950 && TREE_CODE (lhs
) != ADDR_EXPR
)
1953 /* Extract a pointer base and an offset for the source. */
1954 rhs
= gimple_call_arg (def_stmt
, 1);
1956 if (TREE_CODE (rhs
) == SSA_NAME
)
1957 rhs
= SSA_VAL (rhs
);
1958 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1960 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1964 if (TREE_CODE (tem
) == MEM_REF
1965 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1967 rhs
= TREE_OPERAND (tem
, 0);
1968 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1970 else if (DECL_P (tem
))
1971 rhs
= build_fold_addr_expr (tem
);
1975 if (TREE_CODE (rhs
) != SSA_NAME
1976 && TREE_CODE (rhs
) != ADDR_EXPR
)
1979 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
1981 /* The bases of the destination and the references have to agree. */
1982 if ((TREE_CODE (base
) != MEM_REF
1984 || (TREE_CODE (base
) == MEM_REF
1985 && (TREE_OPERAND (base
, 0) != lhs
1986 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
1988 && (TREE_CODE (lhs
) != ADDR_EXPR
1989 || TREE_OPERAND (lhs
, 0) != base
)))
1992 /* And the access has to be contained within the memcpy destination. */
1993 at
= offset
/ BITS_PER_UNIT
;
1994 if (TREE_CODE (base
) == MEM_REF
)
1995 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
1997 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
2000 /* Make room for 2 operands in the new reference. */
2001 if (vr
->operands
.length () < 2)
2003 vec
<vn_reference_op_s
> old
= vr
->operands
;
2004 vr
->operands
.safe_grow_cleared (2);
2005 if (old
== shared_lookup_references
2006 && vr
->operands
!= old
)
2007 shared_lookup_references
= vr
->operands
;
2010 vr
->operands
.truncate (2);
2012 /* The looked-through reference is a simple MEM_REF. */
2013 memset (&op
, 0, sizeof (op
));
2015 op
.opcode
= MEM_REF
;
2016 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
2017 op
.off
= at
- lhs_offset
+ rhs_offset
;
2018 vr
->operands
[0] = op
;
2019 op
.type
= TREE_TYPE (rhs
);
2020 op
.opcode
= TREE_CODE (rhs
);
2023 vr
->operands
[1] = op
;
2024 vr
->hashcode
= vn_reference_compute_hash (vr
);
2026 /* Adjust *ref from the new operands. */
2027 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2029 /* This can happen with bitfields. */
2030 if (ref
->size
!= r
.size
)
2034 /* Do not update last seen VUSE after translating. */
2035 last_vuse_ptr
= NULL
;
2037 /* Keep looking for the adjusted *REF / VR pair. */
2041 /* Bail out and stop walking. */
2045 /* Lookup a reference operation by it's parts, in the current hash table.
2046 Returns the resulting value number if it exists in the hash table,
2047 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2048 vn_reference_t stored in the hashtable if something is found. */
2051 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2052 vec
<vn_reference_op_s
> operands
,
2053 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2055 struct vn_reference_s vr1
;
2063 vr1
.vuse
= vuse_ssa_val (vuse
);
2064 shared_lookup_references
.truncate (0);
2065 shared_lookup_references
.safe_grow (operands
.length ());
2066 memcpy (shared_lookup_references
.address (),
2067 operands
.address (),
2068 sizeof (vn_reference_op_s
)
2069 * operands
.length ());
2070 vr1
.operands
= operands
= shared_lookup_references
2071 = valueize_refs (shared_lookup_references
);
2074 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2075 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2078 vn_reference_lookup_1 (&vr1
, vnresult
);
2080 && kind
!= VN_NOWALK
2084 vn_walk_kind
= kind
;
2085 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2087 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2088 vn_reference_lookup_2
,
2089 vn_reference_lookup_3
, &vr1
);
2090 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2094 return (*vnresult
)->result
;
2099 /* Lookup OP in the current hash table, and return the resulting value
2100 number if it exists in the hash table. Return NULL_TREE if it does
2101 not exist in the hash table or if the result field of the structure
2102 was NULL.. VNRESULT will be filled in with the vn_reference_t
2103 stored in the hashtable if one exists. */
2106 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2107 vn_reference_t
*vnresult
)
2109 vec
<vn_reference_op_s
> operands
;
2110 struct vn_reference_s vr1
;
2112 bool valuezied_anything
;
2117 vr1
.vuse
= vuse_ssa_val (vuse
);
2118 vr1
.operands
= operands
2119 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2120 vr1
.type
= TREE_TYPE (op
);
2121 vr1
.set
= get_alias_set (op
);
2122 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2123 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2126 if (kind
!= VN_NOWALK
2129 vn_reference_t wvnresult
;
2131 /* Make sure to use a valueized reference if we valueized anything.
2132 Otherwise preserve the full reference for advanced TBAA. */
2133 if (!valuezied_anything
2134 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2136 ao_ref_init (&r
, op
);
2137 vn_walk_kind
= kind
;
2139 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2140 vn_reference_lookup_2
,
2141 vn_reference_lookup_3
, &vr1
);
2142 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2146 *vnresult
= wvnresult
;
2147 return wvnresult
->result
;
2153 return vn_reference_lookup_1 (&vr1
, vnresult
);
2156 /* Lookup CALL in the current hash table and return the entry in
2157 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2160 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
2166 tree vuse
= gimple_vuse (call
);
2168 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2169 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
2170 vr
->type
= gimple_expr_type (call
);
2172 vr
->hashcode
= vn_reference_compute_hash (vr
);
2173 vn_reference_lookup_1 (vr
, vnresult
);
2176 /* Insert OP into the current hash table with a value number of
2177 RESULT, and return the resulting reference structure we created. */
2179 static vn_reference_t
2180 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2182 vn_reference_s
**slot
;
2186 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2187 if (TREE_CODE (result
) == SSA_NAME
)
2188 vr1
->value_id
= VN_INFO (result
)->value_id
;
2190 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2191 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2192 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2193 vr1
->type
= TREE_TYPE (op
);
2194 vr1
->set
= get_alias_set (op
);
2195 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2196 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2197 vr1
->result_vdef
= vdef
;
2199 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2202 /* Because we lookup stores using vuses, and value number failures
2203 using the vdefs (see visit_reference_op_store for how and why),
2204 it's possible that on failure we may try to insert an already
2205 inserted store. This is not wrong, there is no ssa name for a
2206 store that we could use as a differentiator anyway. Thus, unlike
2207 the other lookup functions, you cannot gcc_assert (!*slot)
2210 /* But free the old slot in case of a collision. */
2212 free_reference (*slot
);
2218 /* Insert a reference by it's pieces into the current hash table with
2219 a value number of RESULT. Return the resulting reference
2220 structure we created. */
2223 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2224 vec
<vn_reference_op_s
> operands
,
2225 tree result
, unsigned int value_id
)
2228 vn_reference_s
**slot
;
2231 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2232 vr1
->value_id
= value_id
;
2233 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2234 vr1
->operands
= valueize_refs (operands
);
2237 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2238 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2239 result
= SSA_VAL (result
);
2240 vr1
->result
= result
;
2242 slot
= current_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2245 /* At this point we should have all the things inserted that we have
2246 seen before, and we should never try inserting something that
2248 gcc_assert (!*slot
);
2250 free_reference (*slot
);
2256 /* Compute and return the hash value for nary operation VBO1. */
2259 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2261 inchash::hash hstate
;
2264 for (i
= 0; i
< vno1
->length
; ++i
)
2265 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2266 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2268 if (vno1
->length
== 2
2269 && commutative_tree_code (vno1
->opcode
)
2270 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2272 tree temp
= vno1
->op
[0];
2273 vno1
->op
[0] = vno1
->op
[1];
2277 hstate
.add_int (vno1
->opcode
);
2278 for (i
= 0; i
< vno1
->length
; ++i
)
2279 inchash::add_expr (vno1
->op
[i
], hstate
);
2281 return hstate
.end ();
2284 /* Compare nary operations VNO1 and VNO2 and return true if they are
2288 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2292 if (vno1
->hashcode
!= vno2
->hashcode
)
2295 if (vno1
->length
!= vno2
->length
)
2298 if (vno1
->opcode
!= vno2
->opcode
2299 || !types_compatible_p (vno1
->type
, vno2
->type
))
2302 for (i
= 0; i
< vno1
->length
; ++i
)
2303 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2309 /* Initialize VNO from the pieces provided. */
2312 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2313 enum tree_code code
, tree type
, tree
*ops
)
2316 vno
->length
= length
;
2318 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2321 /* Initialize VNO from OP. */
2324 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2328 vno
->opcode
= TREE_CODE (op
);
2329 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2330 vno
->type
= TREE_TYPE (op
);
2331 for (i
= 0; i
< vno
->length
; ++i
)
2332 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2335 /* Return the number of operands for a vn_nary ops structure from STMT. */
2338 vn_nary_length_from_stmt (gimple stmt
)
2340 switch (gimple_assign_rhs_code (stmt
))
2344 case VIEW_CONVERT_EXPR
:
2351 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2354 return gimple_num_ops (stmt
) - 1;
2358 /* Initialize VNO from STMT. */
2361 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2365 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2366 vno
->type
= gimple_expr_type (stmt
);
2367 switch (vno
->opcode
)
2371 case VIEW_CONVERT_EXPR
:
2373 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2378 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2379 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2380 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2384 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2385 for (i
= 0; i
< vno
->length
; ++i
)
2386 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2390 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2391 vno
->length
= gimple_num_ops (stmt
) - 1;
2392 for (i
= 0; i
< vno
->length
; ++i
)
2393 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2397 /* Compute the hashcode for VNO and look for it in the hash table;
2398 return the resulting value number if it exists in the hash table.
2399 Return NULL_TREE if it does not exist in the hash table or if the
2400 result field of the operation is NULL. VNRESULT will contain the
2401 vn_nary_op_t from the hashtable if it exists. */
2404 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2406 vn_nary_op_s
**slot
;
2411 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2412 slot
= current_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2414 if (!slot
&& current_info
== optimistic_info
)
2415 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
,
2421 return (*slot
)->result
;
2424 /* Lookup a n-ary operation by its pieces and return the resulting value
2425 number if it exists in the hash table. Return NULL_TREE if it does
2426 not exist in the hash table or if the result field of the operation
2427 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2431 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2432 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2434 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2435 sizeof_vn_nary_op (length
));
2436 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2437 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2440 /* Lookup OP in the current hash table, and return the resulting value
2441 number if it exists in the hash table. Return NULL_TREE if it does
2442 not exist in the hash table or if the result field of the operation
2443 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2447 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2450 = XALLOCAVAR (struct vn_nary_op_s
,
2451 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2452 init_vn_nary_op_from_op (vno1
, op
);
2453 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2456 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2457 value number if it exists in the hash table. Return NULL_TREE if
2458 it does not exist in the hash table. VNRESULT will contain the
2459 vn_nary_op_t from the hashtable if it exists. */
2462 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2465 = XALLOCAVAR (struct vn_nary_op_s
,
2466 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2467 init_vn_nary_op_from_stmt (vno1
, stmt
);
2468 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2471 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2474 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2476 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2479 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2483 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2485 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2486 ¤t_info
->nary_obstack
);
2488 vno1
->value_id
= value_id
;
2489 vno1
->length
= length
;
2490 vno1
->result
= result
;
2495 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2496 VNO->HASHCODE first. */
2499 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
2502 vn_nary_op_s
**slot
;
2505 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2507 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2508 gcc_assert (!*slot
);
2514 /* Insert a n-ary operation into the current hash table using it's
2515 pieces. Return the vn_nary_op_t structure we created and put in
2519 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2520 tree type
, tree
*ops
,
2521 tree result
, unsigned int value_id
)
2523 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2524 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2525 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2528 /* Insert OP into the current hash table with a value number of
2529 RESULT. Return the vn_nary_op_t structure we created and put in
2533 vn_nary_op_insert (tree op
, tree result
)
2535 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2538 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2539 init_vn_nary_op_from_op (vno1
, op
);
2540 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2543 /* Insert the rhs of STMT into the current hash table with a value number of
2547 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2550 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2551 result
, VN_INFO (result
)->value_id
);
2552 init_vn_nary_op_from_stmt (vno1
, stmt
);
2553 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2556 /* Compute a hashcode for PHI operation VP1 and return it. */
2558 static inline hashval_t
2559 vn_phi_compute_hash (vn_phi_t vp1
)
2561 inchash::hash
hstate (vp1
->block
->index
);
2566 /* If all PHI arguments are constants we need to distinguish
2567 the PHI node via its type. */
2569 hstate
.merge_hash (vn_hash_type (type
));
2571 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2573 if (phi1op
== VN_TOP
)
2575 inchash::add_expr (phi1op
, hstate
);
2578 return hstate
.end ();
2581 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2584 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2586 if (vp1
->hashcode
!= vp2
->hashcode
)
2589 if (vp1
->block
== vp2
->block
)
2594 /* If the PHI nodes do not have compatible types
2595 they are not the same. */
2596 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2599 /* Any phi in the same block will have it's arguments in the
2600 same edge order, because of how we store phi nodes. */
2601 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2603 tree phi2op
= vp2
->phiargs
[i
];
2604 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2606 if (!expressions_equal_p (phi1op
, phi2op
))
2614 static vec
<tree
> shared_lookup_phiargs
;
2616 /* Lookup PHI in the current hash table, and return the resulting
2617 value number if it exists in the hash table. Return NULL_TREE if
2618 it does not exist in the hash table. */
2621 vn_phi_lookup (gimple phi
)
2624 struct vn_phi_s vp1
;
2627 shared_lookup_phiargs
.truncate (0);
2629 /* Canonicalize the SSA_NAME's to their value number. */
2630 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2632 tree def
= PHI_ARG_DEF (phi
, i
);
2633 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2634 shared_lookup_phiargs
.safe_push (def
);
2636 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2637 vp1
.phiargs
= shared_lookup_phiargs
;
2638 vp1
.block
= gimple_bb (phi
);
2639 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2640 slot
= current_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2642 if (!slot
&& current_info
== optimistic_info
)
2643 slot
= valid_info
->phis
->find_slot_with_hash (&vp1
, vp1
.hashcode
,
2647 return (*slot
)->result
;
2650 /* Insert PHI into the current hash table with a value number of
2654 vn_phi_insert (gimple phi
, tree result
)
2657 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2659 vec
<tree
> args
= vNULL
;
2661 /* Canonicalize the SSA_NAME's to their value number. */
2662 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2664 tree def
= PHI_ARG_DEF (phi
, i
);
2665 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2666 args
.safe_push (def
);
2668 vp1
->value_id
= VN_INFO (result
)->value_id
;
2669 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2670 vp1
->phiargs
= args
;
2671 vp1
->block
= gimple_bb (phi
);
2672 vp1
->result
= result
;
2673 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2675 slot
= current_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2677 /* Because we iterate over phi operations more than once, it's
2678 possible the slot might already exist here, hence no assert.*/
2684 /* Print set of components in strongly connected component SCC to OUT. */
2687 print_scc (FILE *out
, vec
<tree
> scc
)
2692 fprintf (out
, "SCC consists of:");
2693 FOR_EACH_VEC_ELT (scc
, i
, var
)
2696 print_generic_expr (out
, var
, 0);
2698 fprintf (out
, "\n");
2701 /* Set the value number of FROM to TO, return true if it has changed
2705 set_ssa_val_to (tree from
, tree to
)
2707 tree currval
= SSA_VAL (from
);
2708 HOST_WIDE_INT toff
, coff
;
2710 /* The only thing we allow as value numbers are ssa_names
2711 and invariants. So assert that here. We don't allow VN_TOP
2712 as visiting a stmt should produce a value-number other than
2714 ??? Still VN_TOP can happen for unreachable code, so force
2715 it to varying in that case. Not all code is prepared to
2716 get VN_TOP on valueization. */
2719 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2720 fprintf (dump_file
, "Forcing value number to varying on "
2721 "receiving VN_TOP\n");
2725 gcc_assert (to
!= NULL_TREE
2726 && (TREE_CODE (to
) == SSA_NAME
2727 || is_gimple_min_invariant (to
)));
2731 if (currval
== from
)
2733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2735 fprintf (dump_file
, "Not changing value number of ");
2736 print_generic_expr (dump_file
, from
, 0);
2737 fprintf (dump_file
, " from VARYING to ");
2738 print_generic_expr (dump_file
, to
, 0);
2739 fprintf (dump_file
, "\n");
2743 else if (TREE_CODE (to
) == SSA_NAME
2744 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2750 fprintf (dump_file
, "Setting value number of ");
2751 print_generic_expr (dump_file
, from
, 0);
2752 fprintf (dump_file
, " to ");
2753 print_generic_expr (dump_file
, to
, 0);
2757 && !operand_equal_p (currval
, to
, 0)
2758 /* ??? For addresses involving volatile objects or types operand_equal_p
2759 does not reliably detect ADDR_EXPRs as equal. We know we are only
2760 getting invariant gimple addresses here, so can use
2761 get_addr_base_and_unit_offset to do this comparison. */
2762 && !(TREE_CODE (currval
) == ADDR_EXPR
2763 && TREE_CODE (to
) == ADDR_EXPR
2764 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2765 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2768 VN_INFO (from
)->valnum
= to
;
2769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2770 fprintf (dump_file
, " (changed)\n");
2773 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2774 fprintf (dump_file
, "\n");
2778 /* Mark as processed all the definitions in the defining stmt of USE, or
2782 mark_use_processed (tree use
)
2786 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2788 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2790 VN_INFO (use
)->use_processed
= true;
2794 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2796 tree def
= DEF_FROM_PTR (defp
);
2798 VN_INFO (def
)->use_processed
= true;
2802 /* Set all definitions in STMT to value number to themselves.
2803 Return true if a value number changed. */
2806 defs_to_varying (gimple stmt
)
2808 bool changed
= false;
2812 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2814 tree def
= DEF_FROM_PTR (defp
);
2815 changed
|= set_ssa_val_to (def
, def
);
2820 static bool expr_has_constants (tree expr
);
2822 /* Visit a copy between LHS and RHS, return true if the value number
2826 visit_copy (tree lhs
, tree rhs
)
2828 /* The copy may have a more interesting constant filled expression
2829 (we don't, since we know our RHS is just an SSA name). */
2830 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2831 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2833 /* And finally valueize. */
2834 rhs
= SSA_VAL (rhs
);
2836 return set_ssa_val_to (lhs
, rhs
);
2839 /* Visit a nary operator RHS, value number it, and return true if the
2840 value number of LHS has changed as a result. */
2843 visit_nary_op (tree lhs
, gimple stmt
)
2845 bool changed
= false;
2846 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2849 changed
= set_ssa_val_to (lhs
, result
);
2852 changed
= set_ssa_val_to (lhs
, lhs
);
2853 vn_nary_op_insert_stmt (stmt
, lhs
);
2859 /* Visit a call STMT storing into LHS. Return true if the value number
2860 of the LHS has changed as a result. */
2863 visit_reference_op_call (tree lhs
, gcall
*stmt
)
2865 bool changed
= false;
2866 struct vn_reference_s vr1
;
2867 vn_reference_t vnresult
= NULL
;
2868 tree vdef
= gimple_vdef (stmt
);
2870 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2871 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2874 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
2877 if (vnresult
->result_vdef
&& vdef
)
2878 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2880 if (!vnresult
->result
&& lhs
)
2881 vnresult
->result
= lhs
;
2883 if (vnresult
->result
&& lhs
)
2885 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2887 if (VN_INFO (vnresult
->result
)->has_constants
)
2888 VN_INFO (lhs
)->has_constants
= true;
2894 vn_reference_s
**slot
;
2896 changed
|= set_ssa_val_to (vdef
, vdef
);
2898 changed
|= set_ssa_val_to (lhs
, lhs
);
2899 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2900 vr2
->vuse
= vr1
.vuse
;
2901 /* As we are not walking the virtual operand chain we know the
2902 shared_lookup_references are still original so we can re-use
2904 vr2
->operands
= vr1
.operands
.copy ();
2905 vr2
->type
= vr1
.type
;
2907 vr2
->hashcode
= vr1
.hashcode
;
2909 vr2
->result_vdef
= vdef
;
2910 slot
= current_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
2912 gcc_assert (!*slot
);
2919 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2920 and return true if the value number of the LHS has changed as a result. */
2923 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2925 bool changed
= false;
2929 last_vuse
= gimple_vuse (stmt
);
2930 last_vuse_ptr
= &last_vuse
;
2931 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2932 default_vn_walk_kind
, NULL
);
2933 last_vuse_ptr
= NULL
;
2935 /* We handle type-punning through unions by value-numbering based
2936 on offset and size of the access. Be prepared to handle a
2937 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2939 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2941 /* We will be setting the value number of lhs to the value number
2942 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2943 So first simplify and lookup this expression to see if it
2944 is already available. */
2945 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2946 if ((CONVERT_EXPR_P (val
)
2947 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2948 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2950 tree tem
= vn_get_expr_for (TREE_OPERAND (val
, 0));
2951 if ((CONVERT_EXPR_P (tem
)
2952 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2953 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2954 TREE_TYPE (val
), tem
)))
2958 if (!is_gimple_min_invariant (val
)
2959 && TREE_CODE (val
) != SSA_NAME
)
2960 result
= vn_nary_op_lookup (val
, NULL
);
2961 /* If the expression is not yet available, value-number lhs to
2962 a new SSA_NAME we create. */
2965 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2967 /* Initialize value-number information properly. */
2968 VN_INFO_GET (result
)->valnum
= result
;
2969 VN_INFO (result
)->value_id
= get_next_value_id ();
2970 VN_INFO (result
)->expr
= val
;
2971 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2972 VN_INFO (result
)->needs_insertion
= true;
2973 /* As all "inserted" statements are singleton SCCs, insert
2974 to the valid table. This is strictly needed to
2975 avoid re-generating new value SSA_NAMEs for the same
2976 expression during SCC iteration over and over (the
2977 optimistic table gets cleared after each iteration).
2978 We do not need to insert into the optimistic table, as
2979 lookups there will fall back to the valid table. */
2980 if (current_info
== optimistic_info
)
2982 current_info
= valid_info
;
2983 vn_nary_op_insert (val
, result
);
2984 current_info
= optimistic_info
;
2987 vn_nary_op_insert (val
, result
);
2988 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2990 fprintf (dump_file
, "Inserting name ");
2991 print_generic_expr (dump_file
, result
, 0);
2992 fprintf (dump_file
, " for expression ");
2993 print_generic_expr (dump_file
, val
, 0);
2994 fprintf (dump_file
, "\n");
3001 changed
= set_ssa_val_to (lhs
, result
);
3002 if (TREE_CODE (result
) == SSA_NAME
3003 && VN_INFO (result
)->has_constants
)
3005 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
3006 VN_INFO (lhs
)->has_constants
= true;
3011 changed
= set_ssa_val_to (lhs
, lhs
);
3012 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
3019 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3020 and return true if the value number of the LHS has changed as a result. */
3023 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
3025 bool changed
= false;
3026 vn_reference_t vnresult
= NULL
;
3027 tree result
, assign
;
3028 bool resultsame
= false;
3029 tree vuse
= gimple_vuse (stmt
);
3030 tree vdef
= gimple_vdef (stmt
);
3032 /* First we want to lookup using the *vuses* from the store and see
3033 if there the last store to this location with the same address
3036 The vuses represent the memory state before the store. If the
3037 memory state, address, and value of the store is the same as the
3038 last store to this location, then this store will produce the
3039 same memory state as that store.
3041 In this case the vdef versions for this store are value numbered to those
3042 vuse versions, since they represent the same memory state after
3045 Otherwise, the vdefs for the store are used when inserting into
3046 the table, since the store generates a new memory state. */
3048 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
3052 if (TREE_CODE (result
) == SSA_NAME
)
3053 result
= SSA_VAL (result
);
3054 if (TREE_CODE (op
) == SSA_NAME
)
3056 resultsame
= expressions_equal_p (result
, op
);
3059 if ((!result
|| !resultsame
)
3060 /* Only perform the following when being called from PRE
3061 which embeds tail merging. */
3062 && default_vn_walk_kind
== VN_WALK
)
3064 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3065 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
3068 VN_INFO (vdef
)->use_processed
= true;
3069 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3073 if (!result
|| !resultsame
)
3075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3077 fprintf (dump_file
, "No store match\n");
3078 fprintf (dump_file
, "Value numbering store ");
3079 print_generic_expr (dump_file
, lhs
, 0);
3080 fprintf (dump_file
, " to ");
3081 print_generic_expr (dump_file
, op
, 0);
3082 fprintf (dump_file
, "\n");
3084 /* Have to set value numbers before insert, since insert is
3085 going to valueize the references in-place. */
3088 changed
|= set_ssa_val_to (vdef
, vdef
);
3091 /* Do not insert structure copies into the tables. */
3092 if (is_gimple_min_invariant (op
)
3093 || is_gimple_reg (op
))
3094 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3096 /* Only perform the following when being called from PRE
3097 which embeds tail merging. */
3098 if (default_vn_walk_kind
== VN_WALK
)
3100 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3101 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3106 /* We had a match, so value number the vdef to have the value
3107 number of the vuse it came from. */
3109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3110 fprintf (dump_file
, "Store matched earlier value,"
3111 "value numbering store vdefs to matching vuses.\n");
3113 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3119 /* Visit and value number PHI, return true if the value number
3123 visit_phi (gimple phi
)
3125 bool changed
= false;
3127 tree sameval
= VN_TOP
;
3128 bool allsame
= true;
3130 /* TODO: We could check for this in init_sccvn, and replace this
3131 with a gcc_assert. */
3132 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3133 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3135 /* See if all non-TOP arguments have the same value. TOP is
3136 equivalent to everything, so we can ignore it. */
3139 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3140 if (e
->flags
& EDGE_EXECUTABLE
)
3142 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3144 if (TREE_CODE (def
) == SSA_NAME
)
3145 def
= SSA_VAL (def
);
3148 if (sameval
== VN_TOP
)
3154 if (!expressions_equal_p (def
, sameval
))
3162 /* If all value numbered to the same value, the phi node has that
3165 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3167 /* Otherwise, see if it is equivalent to a phi node in this block. */
3168 result
= vn_phi_lookup (phi
);
3170 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3173 vn_phi_insert (phi
, PHI_RESULT (phi
));
3174 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3175 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3176 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3182 /* Return true if EXPR contains constants. */
3185 expr_has_constants (tree expr
)
3187 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3190 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3193 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3194 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3195 /* Constants inside reference ops are rarely interesting, but
3196 it can take a lot of looking to find them. */
3198 case tcc_declaration
:
3201 return is_gimple_min_invariant (expr
);
3206 /* Return true if STMT contains constants. */
3209 stmt_has_constants (gimple stmt
)
3213 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3216 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3218 case GIMPLE_TERNARY_RHS
:
3219 tem
= gimple_assign_rhs3 (stmt
);
3220 if (TREE_CODE (tem
) == SSA_NAME
)
3221 tem
= SSA_VAL (tem
);
3222 if (is_gimple_min_invariant (tem
))
3226 case GIMPLE_BINARY_RHS
:
3227 tem
= gimple_assign_rhs2 (stmt
);
3228 if (TREE_CODE (tem
) == SSA_NAME
)
3229 tem
= SSA_VAL (tem
);
3230 if (is_gimple_min_invariant (tem
))
3234 case GIMPLE_SINGLE_RHS
:
3235 /* Constants inside reference ops are rarely interesting, but
3236 it can take a lot of looking to find them. */
3237 case GIMPLE_UNARY_RHS
:
3238 tem
= gimple_assign_rhs1 (stmt
);
3239 if (TREE_CODE (tem
) == SSA_NAME
)
3240 tem
= SSA_VAL (tem
);
3241 return is_gimple_min_invariant (tem
);
3249 /* Simplify the binary expression RHS, and return the result if
3253 simplify_binary_expression (gimple stmt
)
3255 tree result
= NULL_TREE
;
3256 tree op0
= gimple_assign_rhs1 (stmt
);
3257 tree op1
= gimple_assign_rhs2 (stmt
);
3258 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3260 /* This will not catch every single case we could combine, but will
3261 catch those with constants. The goal here is to simultaneously
3262 combine constants between expressions, but avoid infinite
3263 expansion of expressions during simplification. */
3264 op0
= vn_valueize (op0
);
3265 if (TREE_CODE (op0
) == SSA_NAME
3266 && (VN_INFO (op0
)->has_constants
3267 || TREE_CODE_CLASS (code
) == tcc_comparison
3268 || code
== COMPLEX_EXPR
))
3269 op0
= vn_get_expr_for (op0
);
3271 op1
= vn_valueize (op1
);
3272 if (TREE_CODE (op1
) == SSA_NAME
3273 && (VN_INFO (op1
)->has_constants
3274 || code
== COMPLEX_EXPR
))
3275 op1
= vn_get_expr_for (op1
);
3277 /* Pointer plus constant can be represented as invariant address.
3278 Do so to allow further propatation, see also tree forwprop. */
3279 if (code
== POINTER_PLUS_EXPR
3280 && tree_fits_uhwi_p (op1
)
3281 && TREE_CODE (op0
) == ADDR_EXPR
3282 && is_gimple_min_invariant (op0
))
3283 return build_invariant_address (TREE_TYPE (op0
),
3284 TREE_OPERAND (op0
, 0),
3285 tree_to_uhwi (op1
));
3287 /* Avoid folding if nothing changed. */
3288 if (op0
== gimple_assign_rhs1 (stmt
)
3289 && op1
== gimple_assign_rhs2 (stmt
))
3292 fold_defer_overflow_warnings ();
3294 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3296 STRIP_USELESS_TYPE_CONVERSION (result
);
3298 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3301 /* Make sure result is not a complex expression consisting
3302 of operators of operators (IE (a + b) + (a + c))
3303 Otherwise, we will end up with unbounded expressions if
3304 fold does anything at all. */
3305 if (result
&& valid_gimple_rhs_p (result
))
3311 /* Simplify the unary expression RHS, and return the result if
3315 simplify_unary_expression (gassign
*stmt
)
3317 tree result
= NULL_TREE
;
3318 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3319 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3321 /* We handle some tcc_reference codes here that are all
3322 GIMPLE_ASSIGN_SINGLE codes. */
3323 if (code
== REALPART_EXPR
3324 || code
== IMAGPART_EXPR
3325 || code
== VIEW_CONVERT_EXPR
3326 || code
== BIT_FIELD_REF
)
3327 op0
= TREE_OPERAND (op0
, 0);
3330 op0
= vn_valueize (op0
);
3331 if (TREE_CODE (op0
) == SSA_NAME
)
3333 if (VN_INFO (op0
)->has_constants
)
3334 op0
= vn_get_expr_for (op0
);
3335 else if (CONVERT_EXPR_CODE_P (code
)
3336 || code
== REALPART_EXPR
3337 || code
== IMAGPART_EXPR
3338 || code
== VIEW_CONVERT_EXPR
3339 || code
== BIT_FIELD_REF
)
3341 /* We want to do tree-combining on conversion-like expressions.
3342 Make sure we feed only SSA_NAMEs or constants to fold though. */
3343 tree tem
= vn_get_expr_for (op0
);
3344 if (UNARY_CLASS_P (tem
)
3345 || BINARY_CLASS_P (tem
)
3346 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3347 || TREE_CODE (tem
) == SSA_NAME
3348 || TREE_CODE (tem
) == CONSTRUCTOR
3349 || is_gimple_min_invariant (tem
))
3354 /* Avoid folding if nothing changed, but remember the expression. */
3355 if (op0
== orig_op0
)
3358 if (code
== BIT_FIELD_REF
)
3360 tree rhs
= gimple_assign_rhs1 (stmt
);
3361 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3362 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3365 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3368 STRIP_USELESS_TYPE_CONVERSION (result
);
3369 if (valid_gimple_rhs_p (result
))
3376 /* Try to simplify RHS using equivalences and constant folding. */
3379 try_to_simplify (gassign
*stmt
)
3381 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3384 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3385 in this case, there is no point in doing extra work. */
3386 if (code
== SSA_NAME
)
3389 /* First try constant folding based on our current lattice. */
3390 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3392 && (TREE_CODE (tem
) == SSA_NAME
3393 || is_gimple_min_invariant (tem
)))
3396 /* If that didn't work try combining multiple statements. */
3397 switch (TREE_CODE_CLASS (code
))
3400 /* Fallthrough for some unary codes that can operate on registers. */
3401 if (!(code
== REALPART_EXPR
3402 || code
== IMAGPART_EXPR
3403 || code
== VIEW_CONVERT_EXPR
3404 || code
== BIT_FIELD_REF
))
3406 /* We could do a little more with unary ops, if they expand
3407 into binary ops, but it's debatable whether it is worth it. */
3409 return simplify_unary_expression (stmt
);
3411 case tcc_comparison
:
3413 return simplify_binary_expression (stmt
);
3422 /* Visit and value number USE, return true if the value number
3426 visit_use (tree use
)
3428 bool changed
= false;
3429 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3431 mark_use_processed (use
);
3433 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3434 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3435 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3437 fprintf (dump_file
, "Value numbering ");
3438 print_generic_expr (dump_file
, use
, 0);
3439 fprintf (dump_file
, " stmt = ");
3440 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3443 /* Handle uninitialized uses. */
3444 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3445 changed
= set_ssa_val_to (use
, use
);
3448 if (gimple_code (stmt
) == GIMPLE_PHI
)
3449 changed
= visit_phi (stmt
);
3450 else if (gimple_has_volatile_ops (stmt
))
3451 changed
= defs_to_varying (stmt
);
3452 else if (is_gimple_assign (stmt
))
3454 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3455 tree lhs
= gimple_assign_lhs (stmt
);
3456 tree rhs1
= gimple_assign_rhs1 (stmt
);
3459 /* Shortcut for copies. Simplifying copies is pointless,
3460 since we copy the expression and value they represent. */
3461 if (code
== SSA_NAME
3462 && TREE_CODE (lhs
) == SSA_NAME
)
3464 changed
= visit_copy (lhs
, rhs1
);
3467 simplified
= try_to_simplify (as_a
<gassign
*> (stmt
));
3470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3472 fprintf (dump_file
, "RHS ");
3473 print_gimple_expr (dump_file
, stmt
, 0, 0);
3474 fprintf (dump_file
, " simplified to ");
3475 print_generic_expr (dump_file
, simplified
, 0);
3476 if (TREE_CODE (lhs
) == SSA_NAME
)
3477 fprintf (dump_file
, " has constants %d\n",
3478 expr_has_constants (simplified
));
3480 fprintf (dump_file
, "\n");
3483 /* Setting value numbers to constants will occasionally
3484 screw up phi congruence because constants are not
3485 uniquely associated with a single ssa name that can be
3488 && is_gimple_min_invariant (simplified
)
3489 && TREE_CODE (lhs
) == SSA_NAME
)
3491 VN_INFO (lhs
)->expr
= simplified
;
3492 VN_INFO (lhs
)->has_constants
= true;
3493 changed
= set_ssa_val_to (lhs
, simplified
);
3497 && TREE_CODE (simplified
) == SSA_NAME
3498 && TREE_CODE (lhs
) == SSA_NAME
)
3500 changed
= visit_copy (lhs
, simplified
);
3503 else if (simplified
)
3505 if (TREE_CODE (lhs
) == SSA_NAME
)
3507 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3508 /* We have to unshare the expression or else
3509 valuizing may change the IL stream. */
3510 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3513 else if (stmt_has_constants (stmt
)
3514 && TREE_CODE (lhs
) == SSA_NAME
)
3515 VN_INFO (lhs
)->has_constants
= true;
3516 else if (TREE_CODE (lhs
) == SSA_NAME
)
3518 /* We reset expr and constantness here because we may
3519 have been value numbering optimistically, and
3520 iterating. They may become non-constant in this case,
3521 even if they were optimistically constant. */
3523 VN_INFO (lhs
)->has_constants
= false;
3524 VN_INFO (lhs
)->expr
= NULL_TREE
;
3527 if ((TREE_CODE (lhs
) == SSA_NAME
3528 /* We can substitute SSA_NAMEs that are live over
3529 abnormal edges with their constant value. */
3530 && !(gimple_assign_copy_p (stmt
)
3531 && is_gimple_min_invariant (rhs1
))
3533 && is_gimple_min_invariant (simplified
))
3534 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3535 /* Stores or copies from SSA_NAMEs that are live over
3536 abnormal edges are a problem. */
3537 || (code
== SSA_NAME
3538 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3539 changed
= defs_to_varying (stmt
);
3540 else if (REFERENCE_CLASS_P (lhs
)
3542 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3543 else if (TREE_CODE (lhs
) == SSA_NAME
)
3545 if ((gimple_assign_copy_p (stmt
)
3546 && is_gimple_min_invariant (rhs1
))
3548 && is_gimple_min_invariant (simplified
)))
3550 VN_INFO (lhs
)->has_constants
= true;
3552 changed
= set_ssa_val_to (lhs
, simplified
);
3554 changed
= set_ssa_val_to (lhs
, rhs1
);
3558 /* First try to lookup the simplified expression. */
3561 enum gimple_rhs_class rhs_class
;
3564 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3565 if ((rhs_class
== GIMPLE_UNARY_RHS
3566 || rhs_class
== GIMPLE_BINARY_RHS
3567 || rhs_class
== GIMPLE_TERNARY_RHS
)
3568 && valid_gimple_rhs_p (simplified
))
3570 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3573 changed
= set_ssa_val_to (lhs
, result
);
3579 /* Otherwise visit the original statement. */
3580 switch (vn_get_stmt_kind (stmt
))
3583 changed
= visit_nary_op (lhs
, stmt
);
3586 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3589 changed
= defs_to_varying (stmt
);
3595 changed
= defs_to_varying (stmt
);
3597 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
3599 tree lhs
= gimple_call_lhs (stmt
);
3600 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3602 /* Try constant folding based on our current lattice. */
3603 tree simplified
= gimple_fold_stmt_to_constant_1 (stmt
,
3607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3609 fprintf (dump_file
, "call ");
3610 print_gimple_expr (dump_file
, stmt
, 0, 0);
3611 fprintf (dump_file
, " simplified to ");
3612 print_generic_expr (dump_file
, simplified
, 0);
3613 if (TREE_CODE (lhs
) == SSA_NAME
)
3614 fprintf (dump_file
, " has constants %d\n",
3615 expr_has_constants (simplified
));
3617 fprintf (dump_file
, "\n");
3620 /* Setting value numbers to constants will occasionally
3621 screw up phi congruence because constants are not
3622 uniquely associated with a single ssa name that can be
3625 && is_gimple_min_invariant (simplified
))
3627 VN_INFO (lhs
)->expr
= simplified
;
3628 VN_INFO (lhs
)->has_constants
= true;
3629 changed
= set_ssa_val_to (lhs
, simplified
);
3630 if (gimple_vdef (stmt
))
3631 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3632 gimple_vuse (stmt
));
3636 && TREE_CODE (simplified
) == SSA_NAME
)
3638 changed
= visit_copy (lhs
, simplified
);
3639 if (gimple_vdef (stmt
))
3640 changed
|= set_ssa_val_to (gimple_vdef (stmt
),
3641 gimple_vuse (stmt
));
3646 if (stmt_has_constants (stmt
))
3647 VN_INFO (lhs
)->has_constants
= true;
3650 /* We reset expr and constantness here because we may
3651 have been value numbering optimistically, and
3652 iterating. They may become non-constant in this case,
3653 even if they were optimistically constant. */
3654 VN_INFO (lhs
)->has_constants
= false;
3655 VN_INFO (lhs
)->expr
= NULL_TREE
;
3658 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3660 changed
= defs_to_varying (stmt
);
3666 if (!gimple_call_internal_p (stmt
)
3667 && (/* Calls to the same function with the same vuse
3668 and the same operands do not necessarily return the same
3669 value, unless they're pure or const. */
3670 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3671 /* If calls have a vdef, subsequent calls won't have
3672 the same incoming vuse. So, if 2 calls with vdef have the
3673 same vuse, we know they're not subsequent.
3674 We can value number 2 calls to the same function with the
3675 same vuse and the same operands which are not subsequent
3676 the same, because there is no code in the program that can
3677 compare the 2 values... */
3678 || (gimple_vdef (stmt
)
3679 /* ... unless the call returns a pointer which does
3680 not alias with anything else. In which case the
3681 information that the values are distinct are encoded
3683 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
3684 /* Only perform the following when being called from PRE
3685 which embeds tail merging. */
3686 && default_vn_walk_kind
== VN_WALK
)))
3687 changed
= visit_reference_op_call (lhs
, call_stmt
);
3689 changed
= defs_to_varying (stmt
);
3692 changed
= defs_to_varying (stmt
);
3698 /* Compare two operands by reverse postorder index */
3701 compare_ops (const void *pa
, const void *pb
)
3703 const tree opa
= *((const tree
*)pa
);
3704 const tree opb
= *((const tree
*)pb
);
3705 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3706 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3710 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3711 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3712 else if (gimple_nop_p (opstmta
))
3714 else if (gimple_nop_p (opstmtb
))
3717 bba
= gimple_bb (opstmta
);
3718 bbb
= gimple_bb (opstmtb
);
3721 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3729 if (gimple_code (opstmta
) == GIMPLE_PHI
3730 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3731 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3732 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3734 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3736 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3737 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3739 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3741 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3744 /* Sort an array containing members of a strongly connected component
3745 SCC so that the members are ordered by RPO number.
3746 This means that when the sort is complete, iterating through the
3747 array will give you the members in RPO order. */
3750 sort_scc (vec
<tree
> scc
)
3752 scc
.qsort (compare_ops
);
3755 /* Insert the no longer used nary ONARY to the hash INFO. */
3758 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3760 size_t size
= sizeof_vn_nary_op (onary
->length
);
3761 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3762 &info
->nary_obstack
);
3763 memcpy (nary
, onary
, size
);
3764 vn_nary_op_insert_into (nary
, info
->nary
, false);
3767 /* Insert the no longer used phi OPHI to the hash INFO. */
3770 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3772 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3774 memcpy (phi
, ophi
, sizeof (*phi
));
3775 ophi
->phiargs
.create (0);
3776 slot
= info
->phis
->find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3777 gcc_assert (!*slot
);
3781 /* Insert the no longer used reference OREF to the hash INFO. */
3784 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3787 vn_reference_s
**slot
;
3788 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3789 memcpy (ref
, oref
, sizeof (*ref
));
3790 oref
->operands
.create (0);
3791 slot
= info
->references
->find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3793 free_reference (*slot
);
3797 /* Process a strongly connected component in the SSA graph. */
3800 process_scc (vec
<tree
> scc
)
3804 unsigned int iterations
= 0;
3805 bool changed
= true;
3806 vn_nary_op_iterator_type hin
;
3807 vn_phi_iterator_type hip
;
3808 vn_reference_iterator_type hir
;
3813 /* If the SCC has a single member, just visit it. */
3814 if (scc
.length () == 1)
3817 if (VN_INFO (use
)->use_processed
)
3819 /* We need to make sure it doesn't form a cycle itself, which can
3820 happen for self-referential PHI nodes. In that case we would
3821 end up inserting an expression with VN_TOP operands into the
3822 valid table which makes us derive bogus equivalences later.
3823 The cheapest way to check this is to assume it for all PHI nodes. */
3824 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3825 /* Fallthru to iteration. */ ;
3833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3834 print_scc (dump_file
, scc
);
3836 /* Iterate over the SCC with the optimistic table until it stops
3838 current_info
= optimistic_info
;
3843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3844 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3845 /* As we are value-numbering optimistically we have to
3846 clear the expression tables and the simplified expressions
3847 in each iteration until we converge. */
3848 optimistic_info
->nary
->empty ();
3849 optimistic_info
->phis
->empty ();
3850 optimistic_info
->references
->empty ();
3851 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3852 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3853 empty_alloc_pool (optimistic_info
->phis_pool
);
3854 empty_alloc_pool (optimistic_info
->references_pool
);
3855 FOR_EACH_VEC_ELT (scc
, i
, var
)
3856 VN_INFO (var
)->expr
= NULL_TREE
;
3857 FOR_EACH_VEC_ELT (scc
, i
, var
)
3858 changed
|= visit_use (var
);
3861 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3862 fprintf (dump_file
, "Processing SCC needed %d iterations\n", iterations
);
3863 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3865 /* Finally, copy the contents of the no longer used optimistic
3866 table to the valid table. */
3867 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3868 copy_nary (nary
, valid_info
);
3869 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3870 copy_phi (phi
, valid_info
);
3871 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info
->references
,
3872 ref
, vn_reference_t
, hir
)
3873 copy_reference (ref
, valid_info
);
3875 current_info
= valid_info
;
3879 /* Pop the components of the found SCC for NAME off the SCC stack
3880 and process them. Returns true if all went well, false if
3881 we run into resource limits. */
3884 extract_and_process_scc_for_name (tree name
)
3889 /* Found an SCC, pop the components off the SCC stack and
3893 x
= sccstack
.pop ();
3895 VN_INFO (x
)->on_sccstack
= false;
3897 } while (x
!= name
);
3899 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3901 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3904 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3905 "SCC size %u exceeding %u\n", scc
.length (),
3906 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3911 if (scc
.length () > 1)
3919 /* Depth first search on NAME to discover and process SCC's in the SSA
3921 Execution of this algorithm relies on the fact that the SCC's are
3922 popped off the stack in topological order.
3923 Returns true if successful, false if we stopped processing SCC's due
3924 to resource constraints. */
3929 vec
<ssa_op_iter
> itervec
= vNULL
;
3930 vec
<tree
> namevec
= vNULL
;
3931 use_operand_p usep
= NULL
;
3938 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3939 VN_INFO (name
)->visited
= true;
3940 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3942 sccstack
.safe_push (name
);
3943 VN_INFO (name
)->on_sccstack
= true;
3944 defstmt
= SSA_NAME_DEF_STMT (name
);
3946 /* Recursively DFS on our operands, looking for SCC's. */
3947 if (!gimple_nop_p (defstmt
))
3949 /* Push a new iterator. */
3950 if (gphi
*phi
= dyn_cast
<gphi
*> (defstmt
))
3951 usep
= op_iter_init_phiuse (&iter
, phi
, SSA_OP_ALL_USES
);
3953 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3956 clear_and_done_ssa_iter (&iter
);
3960 /* If we are done processing uses of a name, go up the stack
3961 of iterators and process SCCs as we found them. */
3962 if (op_iter_done (&iter
))
3964 /* See if we found an SCC. */
3965 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3966 if (!extract_and_process_scc_for_name (name
))
3973 /* Check if we are done. */
3974 if (namevec
.is_empty ())
3981 /* Restore the last use walker and continue walking there. */
3983 name
= namevec
.pop ();
3984 memcpy (&iter
, &itervec
.last (),
3985 sizeof (ssa_op_iter
));
3987 goto continue_walking
;
3990 use
= USE_FROM_PTR (usep
);
3992 /* Since we handle phi nodes, we will sometimes get
3993 invariants in the use expression. */
3994 if (TREE_CODE (use
) == SSA_NAME
)
3996 if (! (VN_INFO (use
)->visited
))
3998 /* Recurse by pushing the current use walking state on
3999 the stack and starting over. */
4000 itervec
.safe_push (iter
);
4001 namevec
.safe_push (name
);
4006 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
4007 VN_INFO (use
)->low
);
4009 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
4010 && VN_INFO (use
)->on_sccstack
)
4012 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
4013 VN_INFO (name
)->low
);
4017 usep
= op_iter_next_use (&iter
);
4021 /* Allocate a value number table. */
4024 allocate_vn_table (vn_tables_t table
)
4026 table
->phis
= new vn_phi_table_type (23);
4027 table
->nary
= new vn_nary_op_table_type (23);
4028 table
->references
= new vn_reference_table_type (23);
4030 gcc_obstack_init (&table
->nary_obstack
);
4031 table
->phis_pool
= create_alloc_pool ("VN phis",
4032 sizeof (struct vn_phi_s
),
4034 table
->references_pool
= create_alloc_pool ("VN references",
4035 sizeof (struct vn_reference_s
),
4039 /* Free a value number table. */
4042 free_vn_table (vn_tables_t table
)
4048 delete table
->references
;
4049 table
->references
= NULL
;
4050 obstack_free (&table
->nary_obstack
, NULL
);
4051 free_alloc_pool (table
->phis_pool
);
4052 free_alloc_pool (table
->references_pool
);
4060 int *rpo_numbers_temp
;
4062 calculate_dominance_info (CDI_DOMINATORS
);
4063 sccstack
.create (0);
4064 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
4066 constant_value_ids
= BITMAP_ALLOC (NULL
);
4071 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
4072 /* VEC_alloc doesn't actually grow it to the right size, it just
4073 preallocates the space to do so. */
4074 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
4075 gcc_obstack_init (&vn_ssa_aux_obstack
);
4077 shared_lookup_phiargs
.create (0);
4078 shared_lookup_references
.create (0);
4079 rpo_numbers
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
4081 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
4082 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
4084 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4085 the i'th block in RPO order is bb. We want to map bb's to RPO
4086 numbers, so we need to rearrange this array. */
4087 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
4088 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
4090 XDELETE (rpo_numbers_temp
);
4092 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
4094 /* Create the VN_INFO structures, and initialize value numbers to
4096 for (i
= 0; i
< num_ssa_names
; i
++)
4098 tree name
= ssa_name (i
);
4101 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4102 VN_INFO (name
)->expr
= NULL_TREE
;
4103 VN_INFO (name
)->value_id
= 0;
4107 renumber_gimple_stmt_uids ();
4109 /* Create the valid and optimistic value numbering tables. */
4110 valid_info
= XCNEW (struct vn_tables_s
);
4111 allocate_vn_table (valid_info
);
4112 optimistic_info
= XCNEW (struct vn_tables_s
);
4113 allocate_vn_table (optimistic_info
);
4121 delete constant_to_value_id
;
4122 constant_to_value_id
= NULL
;
4123 BITMAP_FREE (constant_value_ids
);
4124 shared_lookup_phiargs
.release ();
4125 shared_lookup_references
.release ();
4126 XDELETEVEC (rpo_numbers
);
4128 for (i
= 0; i
< num_ssa_names
; i
++)
4130 tree name
= ssa_name (i
);
4132 && VN_INFO (name
)->needs_insertion
)
4133 release_ssa_name (name
);
4135 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4136 vn_ssa_aux_table
.release ();
4138 sccstack
.release ();
4139 free_vn_table (valid_info
);
4140 XDELETE (valid_info
);
4141 free_vn_table (optimistic_info
);
4142 XDELETE (optimistic_info
);
4145 /* Set *ID according to RESULT. */
4148 set_value_id_for_result (tree result
, unsigned int *id
)
4150 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4151 *id
= VN_INFO (result
)->value_id
;
4152 else if (result
&& is_gimple_min_invariant (result
))
4153 *id
= get_or_alloc_constant_value_id (result
);
4155 *id
= get_next_value_id ();
4158 /* Set the value ids in the valid hash tables. */
4161 set_hashtable_value_ids (void)
4163 vn_nary_op_iterator_type hin
;
4164 vn_phi_iterator_type hip
;
4165 vn_reference_iterator_type hir
;
4170 /* Now set the value ids of the things we had put in the hash
4173 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4174 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4176 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4177 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4179 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4181 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4184 class cond_dom_walker
: public dom_walker
4187 cond_dom_walker () : dom_walker (CDI_DOMINATORS
), fail (false) {}
4189 virtual void before_dom_children (basic_block
);
4195 cond_dom_walker::before_dom_children (basic_block bb
)
4203 /* If any of the predecessor edges that do not come from blocks dominated
4204 by us are still marked as possibly executable consider this block
4206 bool reachable
= bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
);
4207 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4208 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
4209 reachable
|= (e
->flags
& EDGE_EXECUTABLE
);
4211 /* If the block is not reachable all outgoing edges are not
4215 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4216 fprintf (dump_file
, "Marking all outgoing edges of unreachable "
4217 "BB %d as not executable\n", bb
->index
);
4219 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4220 e
->flags
&= ~EDGE_EXECUTABLE
;
4224 gimple stmt
= last_stmt (bb
);
4228 enum gimple_code code
= gimple_code (stmt
);
4229 if (code
!= GIMPLE_COND
4230 && code
!= GIMPLE_SWITCH
4231 && code
!= GIMPLE_GOTO
)
4234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4236 fprintf (dump_file
, "Value-numbering operands of stmt ending BB %d: ",
4238 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4241 /* Value-number the last stmts SSA uses. */
4244 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
4245 if (VN_INFO (op
)->visited
== false
4252 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4253 if value-numbering can prove they are not reachable. Handling
4254 computed gotos is also possible. */
4260 tree lhs
= gimple_cond_lhs (stmt
);
4261 tree rhs
= gimple_cond_rhs (stmt
);
4262 /* Work hard in computing the condition and take into account
4263 the valueization of the defining stmt. */
4264 if (TREE_CODE (lhs
) == SSA_NAME
)
4265 lhs
= vn_get_expr_for (lhs
);
4266 if (TREE_CODE (rhs
) == SSA_NAME
)
4267 rhs
= vn_get_expr_for (rhs
);
4268 val
= fold_binary (gimple_cond_code (stmt
),
4269 boolean_type_node
, lhs
, rhs
);
4273 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
4276 val
= gimple_goto_dest (stmt
);
4284 edge taken
= find_taken_edge (bb
, vn_valueize (val
));
4288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4289 fprintf (dump_file
, "Marking all edges out of BB %d but (%d -> %d) as "
4290 "not executable\n", bb
->index
, bb
->index
, taken
->dest
->index
);
4292 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4294 e
->flags
&= ~EDGE_EXECUTABLE
;
4297 /* Do SCCVN. Returns true if it finished, false if we bailed out
4298 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4299 how we use the alias oracle walking during the VN process. */
4302 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4308 default_vn_walk_kind
= default_vn_walk_kind_
;
4311 current_info
= valid_info
;
4313 for (param
= DECL_ARGUMENTS (current_function_decl
);
4315 param
= DECL_CHAIN (param
))
4317 tree def
= ssa_default_def (cfun
, param
);
4320 VN_INFO (def
)->visited
= true;
4321 VN_INFO (def
)->valnum
= def
;
4325 /* Mark all edges as possibly executable. */
4326 FOR_ALL_BB_FN (bb
, cfun
)
4330 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4331 e
->flags
|= EDGE_EXECUTABLE
;
4334 /* Walk all blocks in dominator order, value-numbering the last stmts
4335 SSA uses and decide whether outgoing edges are not executable. */
4336 cond_dom_walker walker
;
4337 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4344 /* Value-number remaining SSA names. */
4345 for (i
= 1; i
< num_ssa_names
; ++i
)
4347 tree name
= ssa_name (i
);
4349 && VN_INFO (name
)->visited
== false
4350 && !has_zero_uses (name
))
4358 /* Initialize the value ids. */
4360 for (i
= 1; i
< num_ssa_names
; ++i
)
4362 tree name
= ssa_name (i
);
4366 info
= VN_INFO (name
);
4367 if (info
->valnum
== name
4368 || info
->valnum
== VN_TOP
)
4369 info
->value_id
= get_next_value_id ();
4370 else if (is_gimple_min_invariant (info
->valnum
))
4371 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4375 for (i
= 1; i
< num_ssa_names
; ++i
)
4377 tree name
= ssa_name (i
);
4381 info
= VN_INFO (name
);
4382 if (TREE_CODE (info
->valnum
) == SSA_NAME
4383 && info
->valnum
!= name
4384 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4385 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4388 set_hashtable_value_ids ();
4390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4392 fprintf (dump_file
, "Value numbers:\n");
4393 for (i
= 0; i
< num_ssa_names
; i
++)
4395 tree name
= ssa_name (i
);
4397 && VN_INFO (name
)->visited
4398 && SSA_VAL (name
) != name
)
4400 print_generic_expr (dump_file
, name
, 0);
4401 fprintf (dump_file
, " = ");
4402 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4403 fprintf (dump_file
, "\n");
4411 /* Return the maximum value id we have ever seen. */
4414 get_max_value_id (void)
4416 return next_value_id
;
4419 /* Return the next unique value id. */
4422 get_next_value_id (void)
4424 return next_value_id
++;
4428 /* Compare two expressions E1 and E2 and return true if they are equal. */
4431 expressions_equal_p (tree e1
, tree e2
)
4433 /* The obvious case. */
4437 /* If only one of them is null, they cannot be equal. */
4441 /* Now perform the actual comparison. */
4442 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4443 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4450 /* Return true if the nary operation NARY may trap. This is a copy
4451 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4454 vn_nary_may_trap (vn_nary_op_t nary
)
4457 tree rhs2
= NULL_TREE
;
4458 bool honor_nans
= false;
4459 bool honor_snans
= false;
4460 bool fp_operation
= false;
4461 bool honor_trapv
= false;
4465 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4466 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4467 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4470 fp_operation
= FLOAT_TYPE_P (type
);
4473 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4474 honor_snans
= flag_signaling_nans
!= 0;
4476 else if (INTEGRAL_TYPE_P (type
)
4477 && TYPE_OVERFLOW_TRAPS (type
))
4480 if (nary
->length
>= 2)
4482 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4484 honor_nans
, honor_snans
, rhs2
,
4490 for (i
= 0; i
< nary
->length
; ++i
)
4491 if (tree_could_trap_p (nary
->op
[i
]))