1 /* SCC value numbering for trees
2 Copyright (C) 2006-2013 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "stor-layout.h"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "tree-inline.h"
32 #include "gimple-ssa.h"
33 #include "tree-phinodes.h"
34 #include "ssa-iterators.h"
35 #include "stringpool.h"
36 #include "tree-ssanames.h"
41 #include "hash-table.h"
42 #include "alloc-pool.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-sccvn.h"
49 /* This algorithm is based on the SCC algorithm presented by Keith
50 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
51 (http://citeseer.ist.psu.edu/41805.html). In
52 straight line code, it is equivalent to a regular hash based value
53 numbering that is performed in reverse postorder.
55 For code with cycles, there are two alternatives, both of which
56 require keeping the hashtables separate from the actual list of
57 value numbers for SSA names.
59 1. Iterate value numbering in an RPO walk of the blocks, removing
60 all the entries from the hashtable after each iteration (but
61 keeping the SSA name->value number mapping between iterations).
62 Iterate until it does not change.
64 2. Perform value numbering as part of an SCC walk on the SSA graph,
65 iterating only the cycles in the SSA graph until they do not change
66 (using a separate, optimistic hashtable for value numbering the SCC
69 The second is not just faster in practice (because most SSA graph
70 cycles do not involve all the variables in the graph), it also has
73 One of these nice properties is that when we pop an SCC off the
74 stack, we are guaranteed to have processed all the operands coming from
75 *outside of that SCC*, so we do not need to do anything special to
76 ensure they have value numbers.
78 Another nice property is that the SCC walk is done as part of a DFS
79 of the SSA graph, which makes it easy to perform combining and
80 simplifying operations at the same time.
82 The code below is deliberately written in a way that makes it easy
83 to separate the SCC walk from the other work it does.
85 In order to propagate constants through the code, we track which
86 expressions contain constants, and use those while folding. In
87 theory, we could also track expressions whose value numbers are
88 replaced, in case we end up folding based on expression
91 In order to value number memory, we assign value numbers to vuses.
92 This enables us to note that, for example, stores to the same
93 address of the same value from the same starting memory states are
97 1. We can iterate only the changing portions of the SCC's, but
98 I have not seen an SCC big enough for this to be a win.
99 2. If you differentiate between phi nodes for loops and phi nodes
100 for if-then-else, you can properly consider phi nodes in different
101 blocks for equivalence.
102 3. We could value number vuses in more cases, particularly, whole
107 /* vn_nary_op hashtable helpers. */
109 struct vn_nary_op_hasher
: typed_noop_remove
<vn_nary_op_s
>
111 typedef vn_nary_op_s value_type
;
112 typedef vn_nary_op_s compare_type
;
113 static inline hashval_t
hash (const value_type
*);
114 static inline bool equal (const value_type
*, const compare_type
*);
117 /* Return the computed hashcode for nary operation P1. */
120 vn_nary_op_hasher::hash (const value_type
*vno1
)
122 return vno1
->hashcode
;
125 /* Compare nary operations P1 and P2 and return true if they are
129 vn_nary_op_hasher::equal (const value_type
*vno1
, const compare_type
*vno2
)
131 return vn_nary_op_eq (vno1
, vno2
);
134 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
135 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
138 /* vn_phi hashtable helpers. */
141 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
145 typedef vn_phi_s value_type
;
146 typedef vn_phi_s compare_type
;
147 static inline hashval_t
hash (const value_type
*);
148 static inline bool equal (const value_type
*, const compare_type
*);
149 static inline void remove (value_type
*);
152 /* Return the computed hashcode for phi operation P1. */
155 vn_phi_hasher::hash (const value_type
*vp1
)
157 return vp1
->hashcode
;
160 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
163 vn_phi_hasher::equal (const value_type
*vp1
, const compare_type
*vp2
)
165 return vn_phi_eq (vp1
, vp2
);
168 /* Free a phi operation structure VP. */
171 vn_phi_hasher::remove (value_type
*phi
)
173 phi
->phiargs
.release ();
176 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
177 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
180 /* Compare two reference operands P1 and P2 for equality. Return true if
181 they are equal, and false otherwise. */
184 vn_reference_op_eq (const void *p1
, const void *p2
)
186 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
187 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
189 return (vro1
->opcode
== vro2
->opcode
190 /* We do not care for differences in type qualification. */
191 && (vro1
->type
== vro2
->type
192 || (vro1
->type
&& vro2
->type
193 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
194 TYPE_MAIN_VARIANT (vro2
->type
))))
195 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
196 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
197 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
200 /* Free a reference operation structure VP. */
203 free_reference (vn_reference_s
*vr
)
205 vr
->operands
.release ();
209 /* vn_reference hashtable helpers. */
211 struct vn_reference_hasher
213 typedef vn_reference_s value_type
;
214 typedef vn_reference_s compare_type
;
215 static inline hashval_t
hash (const value_type
*);
216 static inline bool equal (const value_type
*, const compare_type
*);
217 static inline void remove (value_type
*);
220 /* Return the hashcode for a given reference operation P1. */
223 vn_reference_hasher::hash (const value_type
*vr1
)
225 return vr1
->hashcode
;
229 vn_reference_hasher::equal (const value_type
*v
, const compare_type
*c
)
231 return vn_reference_eq (v
, c
);
235 vn_reference_hasher::remove (value_type
*v
)
240 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
241 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
244 /* The set of hashtables and alloc_pool's for their items. */
246 typedef struct vn_tables_s
248 vn_nary_op_table_type nary
;
249 vn_phi_table_type phis
;
250 vn_reference_table_type references
;
251 struct obstack nary_obstack
;
252 alloc_pool phis_pool
;
253 alloc_pool references_pool
;
257 /* vn_constant hashtable helpers. */
259 struct vn_constant_hasher
: typed_free_remove
<vn_constant_s
>
261 typedef vn_constant_s value_type
;
262 typedef vn_constant_s compare_type
;
263 static inline hashval_t
hash (const value_type
*);
264 static inline bool equal (const value_type
*, const compare_type
*);
267 /* Hash table hash function for vn_constant_t. */
270 vn_constant_hasher::hash (const value_type
*vc1
)
272 return vc1
->hashcode
;
275 /* Hash table equality function for vn_constant_t. */
278 vn_constant_hasher::equal (const value_type
*vc1
, const compare_type
*vc2
)
280 if (vc1
->hashcode
!= vc2
->hashcode
)
283 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
286 static hash_table
<vn_constant_hasher
> constant_to_value_id
;
287 static bitmap constant_value_ids
;
290 /* Valid hashtables storing information we have proven to be
293 static vn_tables_t valid_info
;
295 /* Optimistic hashtables storing information we are making assumptions about
296 during iterations. */
298 static vn_tables_t optimistic_info
;
300 /* Pointer to the set of hashtables that is currently being used.
301 Should always point to either the optimistic_info, or the
304 static vn_tables_t current_info
;
307 /* Reverse post order index for each basic block. */
309 static int *rpo_numbers
;
311 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
313 /* This represents the top of the VN lattice, which is the universal
318 /* Unique counter for our value ids. */
320 static unsigned int next_value_id
;
322 /* Next DFS number and the stack for strongly connected component
325 static unsigned int next_dfs_num
;
326 static vec
<tree
> sccstack
;
330 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
331 are allocated on an obstack for locality reasons, and to free them
332 without looping over the vec. */
334 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
335 static struct obstack vn_ssa_aux_obstack
;
337 /* Return the value numbering information for a given SSA name. */
342 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
343 gcc_checking_assert (res
);
347 /* Set the value numbering info for a given SSA name to a given
351 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
353 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
356 /* Initialize the value numbering info for a given SSA name.
357 This should be called just once for every SSA name. */
360 VN_INFO_GET (tree name
)
362 vn_ssa_aux_t newinfo
;
364 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
365 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
366 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
367 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
368 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
373 /* Get the representative expression for the SSA_NAME NAME. Returns
374 the representative SSA_NAME if there is no expression associated with it. */
377 vn_get_expr_for (tree name
)
379 vn_ssa_aux_t vn
= VN_INFO (name
);
381 tree expr
= NULL_TREE
;
384 if (vn
->valnum
== VN_TOP
)
387 /* If the value-number is a constant it is the representative
389 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
392 /* Get to the information of the value of this SSA_NAME. */
393 vn
= VN_INFO (vn
->valnum
);
395 /* If the value-number is a constant it is the representative
397 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
400 /* Else if we have an expression, return it. */
401 if (vn
->expr
!= NULL_TREE
)
404 /* Otherwise use the defining statement to build the expression. */
405 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
407 /* If the value number is not an assignment use it directly. */
408 if (!is_gimple_assign (def_stmt
))
411 /* FIXME tuples. This is incomplete and likely will miss some
413 code
= gimple_assign_rhs_code (def_stmt
);
414 switch (TREE_CODE_CLASS (code
))
417 if ((code
== REALPART_EXPR
418 || code
== IMAGPART_EXPR
419 || code
== VIEW_CONVERT_EXPR
)
420 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
422 expr
= fold_build1 (code
,
423 gimple_expr_type (def_stmt
),
424 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
428 expr
= fold_build1 (code
,
429 gimple_expr_type (def_stmt
),
430 gimple_assign_rhs1 (def_stmt
));
434 expr
= fold_build2 (code
,
435 gimple_expr_type (def_stmt
),
436 gimple_assign_rhs1 (def_stmt
),
437 gimple_assign_rhs2 (def_stmt
));
440 case tcc_exceptional
:
441 if (code
== CONSTRUCTOR
443 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
444 expr
= gimple_assign_rhs1 (def_stmt
);
449 if (expr
== NULL_TREE
)
452 /* Cache the expression. */
458 /* Return the vn_kind the expression computed by the stmt should be
462 vn_get_stmt_kind (gimple stmt
)
464 switch (gimple_code (stmt
))
472 enum tree_code code
= gimple_assign_rhs_code (stmt
);
473 tree rhs1
= gimple_assign_rhs1 (stmt
);
474 switch (get_gimple_rhs_class (code
))
476 case GIMPLE_UNARY_RHS
:
477 case GIMPLE_BINARY_RHS
:
478 case GIMPLE_TERNARY_RHS
:
480 case GIMPLE_SINGLE_RHS
:
481 switch (TREE_CODE_CLASS (code
))
484 /* VOP-less references can go through unary case. */
485 if ((code
== REALPART_EXPR
486 || code
== IMAGPART_EXPR
487 || code
== VIEW_CONVERT_EXPR
488 || code
== BIT_FIELD_REF
)
489 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
493 case tcc_declaration
:
500 if (code
== ADDR_EXPR
)
501 return (is_gimple_min_invariant (rhs1
)
502 ? VN_CONSTANT
: VN_REFERENCE
);
503 else if (code
== CONSTRUCTOR
)
516 /* Lookup a value id for CONSTANT and return it. If it does not
520 get_constant_value_id (tree constant
)
522 vn_constant_s
**slot
;
523 struct vn_constant_s vc
;
525 vc
.hashcode
= vn_hash_constant_with_type (constant
);
526 vc
.constant
= constant
;
527 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, NO_INSERT
);
529 return (*slot
)->value_id
;
533 /* Lookup a value id for CONSTANT, and if it does not exist, create a
534 new one and return it. If it does exist, return it. */
537 get_or_alloc_constant_value_id (tree constant
)
539 vn_constant_s
**slot
;
540 struct vn_constant_s vc
;
543 vc
.hashcode
= vn_hash_constant_with_type (constant
);
544 vc
.constant
= constant
;
545 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, INSERT
);
547 return (*slot
)->value_id
;
549 vcp
= XNEW (struct vn_constant_s
);
550 vcp
->hashcode
= vc
.hashcode
;
551 vcp
->constant
= constant
;
552 vcp
->value_id
= get_next_value_id ();
554 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
555 return vcp
->value_id
;
558 /* Return true if V is a value id for a constant. */
561 value_id_constant_p (unsigned int v
)
563 return bitmap_bit_p (constant_value_ids
, v
);
566 /* Compute the hash for a reference operand VRO1. */
569 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
571 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
573 result
= iterative_hash_expr (vro1
->op0
, result
);
575 result
= iterative_hash_expr (vro1
->op1
, result
);
577 result
= iterative_hash_expr (vro1
->op2
, result
);
581 /* Compute a hash for the reference operation VR1 and return it. */
584 vn_reference_compute_hash (const vn_reference_t vr1
)
586 hashval_t result
= 0;
588 vn_reference_op_t vro
;
589 HOST_WIDE_INT off
= -1;
592 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
594 if (vro
->opcode
== MEM_REF
)
596 else if (vro
->opcode
!= ADDR_EXPR
)
608 result
= iterative_hash_hashval_t (off
, result
);
611 && vro
->opcode
== ADDR_EXPR
)
615 tree op
= TREE_OPERAND (vro
->op0
, 0);
616 result
= iterative_hash_hashval_t (TREE_CODE (op
), result
);
617 result
= iterative_hash_expr (op
, result
);
621 result
= vn_reference_op_compute_hash (vro
, result
);
625 result
+= SSA_NAME_VERSION (vr1
->vuse
);
630 /* Return true if reference operations VR1 and VR2 are equivalent. This
631 means they have the same set of operands and vuses. */
634 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
638 if (vr1
->hashcode
!= vr2
->hashcode
)
641 /* Early out if this is not a hash collision. */
642 if (vr1
->hashcode
!= vr2
->hashcode
)
645 /* The VOP needs to be the same. */
646 if (vr1
->vuse
!= vr2
->vuse
)
649 /* If the operands are the same we are done. */
650 if (vr1
->operands
== vr2
->operands
)
653 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
656 if (INTEGRAL_TYPE_P (vr1
->type
)
657 && INTEGRAL_TYPE_P (vr2
->type
))
659 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
662 else if (INTEGRAL_TYPE_P (vr1
->type
)
663 && (TYPE_PRECISION (vr1
->type
)
664 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
666 else if (INTEGRAL_TYPE_P (vr2
->type
)
667 && (TYPE_PRECISION (vr2
->type
)
668 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
675 HOST_WIDE_INT off1
= 0, off2
= 0;
676 vn_reference_op_t vro1
, vro2
;
677 vn_reference_op_s tem1
, tem2
;
678 bool deref1
= false, deref2
= false;
679 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
681 if (vro1
->opcode
== MEM_REF
)
687 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
689 if (vro2
->opcode
== MEM_REF
)
697 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
699 memset (&tem1
, 0, sizeof (tem1
));
700 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
701 tem1
.type
= TREE_TYPE (tem1
.op0
);
702 tem1
.opcode
= TREE_CODE (tem1
.op0
);
706 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
708 memset (&tem2
, 0, sizeof (tem2
));
709 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
710 tem2
.type
= TREE_TYPE (tem2
.op0
);
711 tem2
.opcode
= TREE_CODE (tem2
.op0
);
715 if (deref1
!= deref2
)
717 if (!vn_reference_op_eq (vro1
, vro2
))
722 while (vr1
->operands
.length () != i
723 || vr2
->operands
.length () != j
);
728 /* Copy the operations present in load/store REF into RESULT, a vector of
729 vn_reference_op_s's. */
732 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
734 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
736 vn_reference_op_s temp
;
740 memset (&temp
, 0, sizeof (temp
));
741 temp
.type
= TREE_TYPE (ref
);
742 temp
.opcode
= TREE_CODE (ref
);
743 temp
.op0
= TMR_INDEX (ref
);
744 temp
.op1
= TMR_STEP (ref
);
745 temp
.op2
= TMR_OFFSET (ref
);
747 result
->quick_push (temp
);
749 memset (&temp
, 0, sizeof (temp
));
750 temp
.type
= NULL_TREE
;
751 temp
.opcode
= ERROR_MARK
;
752 temp
.op0
= TMR_INDEX2 (ref
);
754 result
->quick_push (temp
);
756 memset (&temp
, 0, sizeof (temp
));
757 temp
.type
= NULL_TREE
;
758 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
759 temp
.op0
= TMR_BASE (ref
);
761 result
->quick_push (temp
);
765 /* For non-calls, store the information that makes up the address. */
769 vn_reference_op_s temp
;
771 memset (&temp
, 0, sizeof (temp
));
772 temp
.type
= TREE_TYPE (ref
);
773 temp
.opcode
= TREE_CODE (ref
);
779 temp
.op0
= TREE_OPERAND (ref
, 1);
782 temp
.op0
= TREE_OPERAND (ref
, 1);
786 /* The base address gets its own vn_reference_op_s structure. */
787 temp
.op0
= TREE_OPERAND (ref
, 1);
788 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 1)))
789 temp
.off
= tree_to_shwi (TREE_OPERAND (ref
, 1));
792 /* Record bits and position. */
793 temp
.op0
= TREE_OPERAND (ref
, 1);
794 temp
.op1
= TREE_OPERAND (ref
, 2);
797 /* The field decl is enough to unambiguously specify the field,
798 a matching type is not necessary and a mismatching type
799 is always a spurious difference. */
800 temp
.type
= NULL_TREE
;
801 temp
.op0
= TREE_OPERAND (ref
, 1);
802 temp
.op1
= TREE_OPERAND (ref
, 2);
804 tree this_offset
= component_ref_field_offset (ref
);
806 && TREE_CODE (this_offset
) == INTEGER_CST
)
808 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
809 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
812 = tree_to_double_int (this_offset
)
813 + tree_to_double_int (bit_offset
)
814 .rshift (BITS_PER_UNIT
== 8
815 ? 3 : exact_log2 (BITS_PER_UNIT
));
817 /* Probibit value-numbering zero offset components
818 of addresses the same before the pass folding
819 __builtin_object_size had a chance to run
820 (checking cfun->after_inlining does the
822 && (TREE_CODE (orig
) != ADDR_EXPR
824 || cfun
->after_inlining
))
830 case ARRAY_RANGE_REF
:
832 /* Record index as operand. */
833 temp
.op0
= TREE_OPERAND (ref
, 1);
834 /* Always record lower bounds and element size. */
835 temp
.op1
= array_ref_low_bound (ref
);
836 temp
.op2
= array_ref_element_size (ref
);
837 if (TREE_CODE (temp
.op0
) == INTEGER_CST
838 && TREE_CODE (temp
.op1
) == INTEGER_CST
839 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
841 double_int off
= tree_to_double_int (temp
.op0
);
842 off
+= -tree_to_double_int (temp
.op1
);
843 off
*= tree_to_double_int (temp
.op2
);
844 if (off
.fits_shwi ())
849 if (DECL_HARD_REGISTER (ref
))
858 /* Canonicalize decls to MEM[&decl] which is what we end up with
859 when valueizing MEM[ptr] with ptr = &decl. */
860 temp
.opcode
= MEM_REF
;
861 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
863 result
->safe_push (temp
);
864 temp
.opcode
= ADDR_EXPR
;
865 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
866 temp
.type
= TREE_TYPE (temp
.op0
);
880 if (is_gimple_min_invariant (ref
))
886 /* These are only interesting for their operands, their
887 existence, and their type. They will never be the last
888 ref in the chain of references (IE they require an
889 operand), so we don't have to put anything
890 for op* as it will be handled by the iteration */
892 case VIEW_CONVERT_EXPR
:
896 /* This is only interesting for its constant offset. */
897 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
902 result
->safe_push (temp
);
904 if (REFERENCE_CLASS_P (ref
)
905 || TREE_CODE (ref
) == MODIFY_EXPR
906 || TREE_CODE (ref
) == WITH_SIZE_EXPR
907 || (TREE_CODE (ref
) == ADDR_EXPR
908 && !is_gimple_min_invariant (ref
)))
909 ref
= TREE_OPERAND (ref
, 0);
915 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
916 operands in *OPS, the reference alias set SET and the reference type TYPE.
917 Return true if something useful was produced. */
920 ao_ref_init_from_vn_reference (ao_ref
*ref
,
921 alias_set_type set
, tree type
,
922 vec
<vn_reference_op_s
> ops
)
924 vn_reference_op_t op
;
926 tree base
= NULL_TREE
;
928 HOST_WIDE_INT offset
= 0;
929 HOST_WIDE_INT max_size
;
930 HOST_WIDE_INT size
= -1;
931 tree size_tree
= NULL_TREE
;
932 alias_set_type base_alias_set
= -1;
934 /* First get the final access size from just the outermost expression. */
936 if (op
->opcode
== COMPONENT_REF
)
937 size_tree
= DECL_SIZE (op
->op0
);
938 else if (op
->opcode
== BIT_FIELD_REF
)
942 enum machine_mode mode
= TYPE_MODE (type
);
944 size_tree
= TYPE_SIZE (type
);
946 size
= GET_MODE_BITSIZE (mode
);
948 if (size_tree
!= NULL_TREE
)
950 if (!tree_fits_uhwi_p (size_tree
))
953 size
= tree_to_uhwi (size_tree
);
956 /* Initially, maxsize is the same as the accessed element size.
957 In the following it will only grow (or become -1). */
960 /* Compute cumulative bit-offset for nested component-refs and array-refs,
961 and find the ultimate containing object. */
962 FOR_EACH_VEC_ELT (ops
, i
, op
)
966 /* These may be in the reference ops, but we cannot do anything
967 sensible with them here. */
969 /* Apart from ADDR_EXPR arguments to MEM_REF. */
970 if (base
!= NULL_TREE
971 && TREE_CODE (base
) == MEM_REF
973 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
975 vn_reference_op_t pop
= &ops
[i
-1];
976 base
= TREE_OPERAND (op
->op0
, 0);
983 offset
+= pop
->off
* BITS_PER_UNIT
;
991 /* Record the base objects. */
993 base_alias_set
= get_deref_alias_set (op
->op0
);
994 *op0_p
= build2 (MEM_REF
, op
->type
,
996 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1007 /* And now the usual component-reference style ops. */
1009 offset
+= tree_to_shwi (op
->op1
);
1014 tree field
= op
->op0
;
1015 /* We do not have a complete COMPONENT_REF tree here so we
1016 cannot use component_ref_field_offset. Do the interesting
1020 || !tree_fits_uhwi_p (DECL_FIELD_OFFSET (field
)))
1024 offset
+= (tree_to_uhwi (DECL_FIELD_OFFSET (field
))
1026 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
1031 case ARRAY_RANGE_REF
:
1033 /* We recorded the lower bound and the element size. */
1034 if (!tree_fits_shwi_p (op
->op0
)
1035 || !tree_fits_shwi_p (op
->op1
)
1036 || !tree_fits_shwi_p (op
->op2
))
1040 HOST_WIDE_INT hindex
= tree_to_shwi (op
->op0
);
1041 hindex
-= tree_to_shwi (op
->op1
);
1042 hindex
*= tree_to_shwi (op
->op2
);
1043 hindex
*= BITS_PER_UNIT
;
1055 case VIEW_CONVERT_EXPR
:
1072 if (base
== NULL_TREE
)
1075 ref
->ref
= NULL_TREE
;
1077 ref
->offset
= offset
;
1079 ref
->max_size
= max_size
;
1080 ref
->ref_alias_set
= set
;
1081 if (base_alias_set
!= -1)
1082 ref
->base_alias_set
= base_alias_set
;
1084 ref
->base_alias_set
= get_alias_set (base
);
1085 /* We discount volatiles from value-numbering elsewhere. */
1086 ref
->volatile_p
= false;
1091 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1092 vn_reference_op_s's. */
1095 copy_reference_ops_from_call (gimple call
,
1096 vec
<vn_reference_op_s
> *result
)
1098 vn_reference_op_s temp
;
1100 tree lhs
= gimple_call_lhs (call
);
1102 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1103 different. By adding the lhs here in the vector, we ensure that the
1104 hashcode is different, guaranteeing a different value number. */
1105 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1107 memset (&temp
, 0, sizeof (temp
));
1108 temp
.opcode
= MODIFY_EXPR
;
1109 temp
.type
= TREE_TYPE (lhs
);
1112 result
->safe_push (temp
);
1115 /* Copy the type, opcode, function being called and static chain. */
1116 memset (&temp
, 0, sizeof (temp
));
1117 temp
.type
= gimple_call_return_type (call
);
1118 temp
.opcode
= CALL_EXPR
;
1119 temp
.op0
= gimple_call_fn (call
);
1120 temp
.op1
= gimple_call_chain (call
);
1122 result
->safe_push (temp
);
1124 /* Copy the call arguments. As they can be references as well,
1125 just chain them together. */
1126 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1128 tree callarg
= gimple_call_arg (call
, i
);
1129 copy_reference_ops_from_ref (callarg
, result
);
1133 /* Create a vector of vn_reference_op_s structures from CALL, a
1134 call statement. The vector is not shared. */
1136 static vec
<vn_reference_op_s
>
1137 create_reference_ops_from_call (gimple call
)
1139 vec
<vn_reference_op_s
> result
= vNULL
;
1141 copy_reference_ops_from_call (call
, &result
);
1145 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1146 *I_P to point to the last element of the replacement. */
1148 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1151 unsigned int i
= *i_p
;
1152 vn_reference_op_t op
= &(*ops
)[i
];
1153 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1155 HOST_WIDE_INT addr_offset
= 0;
1157 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1158 from .foo.bar to the preceding MEM_REF offset and replace the
1159 address with &OBJ. */
1160 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1162 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1163 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1165 double_int off
= tree_to_double_int (mem_op
->op0
);
1166 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1167 off
+= double_int::from_shwi (addr_offset
);
1168 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1169 op
->op0
= build_fold_addr_expr (addr_base
);
1170 if (tree_fits_shwi_p (mem_op
->op0
))
1171 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1177 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1178 *I_P to point to the last element of the replacement. */
1180 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1183 unsigned int i
= *i_p
;
1184 vn_reference_op_t op
= &(*ops
)[i
];
1185 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1187 enum tree_code code
;
1190 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1191 if (!is_gimple_assign (def_stmt
))
1194 code
= gimple_assign_rhs_code (def_stmt
);
1195 if (code
!= ADDR_EXPR
1196 && code
!= POINTER_PLUS_EXPR
)
1199 off
= tree_to_double_int (mem_op
->op0
);
1200 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1202 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1203 from .foo.bar to the preceding MEM_REF offset and replace the
1204 address with &OBJ. */
1205 if (code
== ADDR_EXPR
)
1207 tree addr
, addr_base
;
1208 HOST_WIDE_INT addr_offset
;
1210 addr
= gimple_assign_rhs1 (def_stmt
);
1211 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1214 || TREE_CODE (addr_base
) != MEM_REF
)
1217 off
+= double_int::from_shwi (addr_offset
);
1218 off
+= mem_ref_offset (addr_base
);
1219 op
->op0
= TREE_OPERAND (addr_base
, 0);
1224 ptr
= gimple_assign_rhs1 (def_stmt
);
1225 ptroff
= gimple_assign_rhs2 (def_stmt
);
1226 if (TREE_CODE (ptr
) != SSA_NAME
1227 || TREE_CODE (ptroff
) != INTEGER_CST
)
1230 off
+= tree_to_double_int (ptroff
);
1234 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1235 if (tree_fits_shwi_p (mem_op
->op0
))
1236 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1239 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1240 op
->op0
= SSA_VAL (op
->op0
);
1241 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1242 op
->opcode
= TREE_CODE (op
->op0
);
1245 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1246 vn_reference_maybe_forwprop_address (ops
, i_p
);
1247 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1248 vn_reference_fold_indirect (ops
, i_p
);
1251 /* Optimize the reference REF to a constant if possible or return
1252 NULL_TREE if not. */
1255 fully_constant_vn_reference_p (vn_reference_t ref
)
1257 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1258 vn_reference_op_t op
;
1260 /* Try to simplify the translated expression if it is
1261 a call to a builtin function with at most two arguments. */
1263 if (op
->opcode
== CALL_EXPR
1264 && TREE_CODE (op
->op0
) == ADDR_EXPR
1265 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1266 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1267 && operands
.length () >= 2
1268 && operands
.length () <= 3)
1270 vn_reference_op_t arg0
, arg1
= NULL
;
1271 bool anyconst
= false;
1272 arg0
= &operands
[1];
1273 if (operands
.length () > 2)
1274 arg1
= &operands
[2];
1275 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1276 || (arg0
->opcode
== ADDR_EXPR
1277 && is_gimple_min_invariant (arg0
->op0
)))
1280 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1281 || (arg1
->opcode
== ADDR_EXPR
1282 && is_gimple_min_invariant (arg1
->op0
))))
1286 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1289 arg1
? arg1
->op0
: NULL
);
1291 && TREE_CODE (folded
) == NOP_EXPR
)
1292 folded
= TREE_OPERAND (folded
, 0);
1294 && is_gimple_min_invariant (folded
))
1299 /* Simplify reads from constant strings. */
1300 else if (op
->opcode
== ARRAY_REF
1301 && TREE_CODE (op
->op0
) == INTEGER_CST
1302 && integer_zerop (op
->op1
)
1303 && operands
.length () == 2)
1305 vn_reference_op_t arg0
;
1306 arg0
= &operands
[1];
1307 if (arg0
->opcode
== STRING_CST
1308 && (TYPE_MODE (op
->type
)
1309 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1310 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1311 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1312 && tree_int_cst_sgn (op
->op0
) >= 0
1313 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1314 return build_int_cst_type (op
->type
,
1315 (TREE_STRING_POINTER (arg0
->op0
)
1316 [TREE_INT_CST_LOW (op
->op0
)]));
1322 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1323 structures into their value numbers. This is done in-place, and
1324 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1325 whether any operands were valueized. */
1327 static vec
<vn_reference_op_s
>
1328 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1330 vn_reference_op_t vro
;
1333 *valueized_anything
= false;
1335 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1337 if (vro
->opcode
== SSA_NAME
1338 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1340 tree tem
= SSA_VAL (vro
->op0
);
1341 if (tem
!= vro
->op0
)
1343 *valueized_anything
= true;
1346 /* If it transforms from an SSA_NAME to a constant, update
1348 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1349 vro
->opcode
= TREE_CODE (vro
->op0
);
1351 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1353 tree tem
= SSA_VAL (vro
->op1
);
1354 if (tem
!= vro
->op1
)
1356 *valueized_anything
= true;
1360 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1362 tree tem
= SSA_VAL (vro
->op2
);
1363 if (tem
!= vro
->op2
)
1365 *valueized_anything
= true;
1369 /* If it transforms from an SSA_NAME to an address, fold with
1370 a preceding indirect reference. */
1373 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1374 && orig
[i
- 1].opcode
== MEM_REF
)
1375 vn_reference_fold_indirect (&orig
, &i
);
1377 && vro
->opcode
== SSA_NAME
1378 && orig
[i
- 1].opcode
== MEM_REF
)
1379 vn_reference_maybe_forwprop_address (&orig
, &i
);
1380 /* If it transforms a non-constant ARRAY_REF into a constant
1381 one, adjust the constant offset. */
1382 else if (vro
->opcode
== ARRAY_REF
1384 && TREE_CODE (vro
->op0
) == INTEGER_CST
1385 && TREE_CODE (vro
->op1
) == INTEGER_CST
1386 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1388 double_int off
= tree_to_double_int (vro
->op0
);
1389 off
+= -tree_to_double_int (vro
->op1
);
1390 off
*= tree_to_double_int (vro
->op2
);
1391 if (off
.fits_shwi ())
1399 static vec
<vn_reference_op_s
>
1400 valueize_refs (vec
<vn_reference_op_s
> orig
)
1403 return valueize_refs_1 (orig
, &tem
);
1406 static vec
<vn_reference_op_s
> shared_lookup_references
;
1408 /* Create a vector of vn_reference_op_s structures from REF, a
1409 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1410 this function. *VALUEIZED_ANYTHING will specify whether any
1411 operands were valueized. */
1413 static vec
<vn_reference_op_s
>
1414 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1418 shared_lookup_references
.truncate (0);
1419 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1420 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1421 valueized_anything
);
1422 return shared_lookup_references
;
1425 /* Create a vector of vn_reference_op_s structures from CALL, a
1426 call statement. The vector is shared among all callers of
1429 static vec
<vn_reference_op_s
>
1430 valueize_shared_reference_ops_from_call (gimple call
)
1434 shared_lookup_references
.truncate (0);
1435 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1436 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1437 return shared_lookup_references
;
1440 /* Lookup a SCCVN reference operation VR in the current hash table.
1441 Returns the resulting value number if it exists in the hash table,
1442 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1443 vn_reference_t stored in the hashtable if something is found. */
1446 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1448 vn_reference_s
**slot
;
1451 hash
= vr
->hashcode
;
1452 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1453 if (!slot
&& current_info
== optimistic_info
)
1454 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1458 *vnresult
= (vn_reference_t
)*slot
;
1459 return ((vn_reference_t
)*slot
)->result
;
1465 static tree
*last_vuse_ptr
;
1466 static vn_lookup_kind vn_walk_kind
;
1467 static vn_lookup_kind default_vn_walk_kind
;
1469 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1470 with the current VUSE and performs the expression lookup. */
1473 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1474 unsigned int cnt
, void *vr_
)
1476 vn_reference_t vr
= (vn_reference_t
)vr_
;
1477 vn_reference_s
**slot
;
1480 /* This bounds the stmt walks we perform on reference lookups
1481 to O(1) instead of O(N) where N is the number of dominating
1483 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1487 *last_vuse_ptr
= vuse
;
1489 /* Fixup vuse and hash. */
1491 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1492 vr
->vuse
= SSA_VAL (vuse
);
1494 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1496 hash
= vr
->hashcode
;
1497 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1498 if (!slot
&& current_info
== optimistic_info
)
1499 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1506 /* Lookup an existing or insert a new vn_reference entry into the
1507 value table for the VUSE, SET, TYPE, OPERANDS reference which
1508 has the value VALUE which is either a constant or an SSA name. */
1510 static vn_reference_t
1511 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1514 vec
<vn_reference_op_s
,
1518 struct vn_reference_s vr1
;
1519 vn_reference_t result
;
1522 vr1
.operands
= operands
;
1525 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1526 if (vn_reference_lookup_1 (&vr1
, &result
))
1528 if (TREE_CODE (value
) == SSA_NAME
)
1529 value_id
= VN_INFO (value
)->value_id
;
1531 value_id
= get_or_alloc_constant_value_id (value
);
1532 return vn_reference_insert_pieces (vuse
, set
, type
,
1533 operands
.copy (), value
, value_id
);
1536 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1537 from the statement defining VUSE and if not successful tries to
1538 translate *REFP and VR_ through an aggregate copy at the definition
1542 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
)
1544 vn_reference_t vr
= (vn_reference_t
)vr_
;
1545 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1547 HOST_WIDE_INT offset
, maxsize
;
1548 static vec
<vn_reference_op_s
>
1551 bool lhs_ref_ok
= false;
1553 /* First try to disambiguate after value-replacing in the definitions LHS. */
1554 if (is_gimple_assign (def_stmt
))
1556 vec
<vn_reference_op_s
> tem
;
1557 tree lhs
= gimple_assign_lhs (def_stmt
);
1558 bool valueized_anything
= false;
1559 /* Avoid re-allocation overhead. */
1560 lhs_ops
.truncate (0);
1561 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1563 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1564 gcc_assert (lhs_ops
== tem
);
1565 if (valueized_anything
)
1567 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1568 get_alias_set (lhs
),
1569 TREE_TYPE (lhs
), lhs_ops
);
1571 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1576 ao_ref_init (&lhs_ref
, lhs
);
1581 base
= ao_ref_base (ref
);
1582 offset
= ref
->offset
;
1583 maxsize
= ref
->max_size
;
1585 /* If we cannot constrain the size of the reference we cannot
1586 test if anything kills it. */
1590 /* We can't deduce anything useful from clobbers. */
1591 if (gimple_clobber_p (def_stmt
))
1594 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1595 from that definition.
1597 if (is_gimple_reg_type (vr
->type
)
1598 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1599 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1600 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1601 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1603 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1605 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1606 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1607 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1608 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1609 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1611 && operand_equal_p (base
, base2
, 0)
1612 && offset2
<= offset
1613 && offset2
+ size2
>= offset
+ maxsize
)
1615 tree val
= build_zero_cst (vr
->type
);
1616 return vn_reference_lookup_or_insert_for_pieces
1617 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1621 /* 2) Assignment from an empty CONSTRUCTOR. */
1622 else if (is_gimple_reg_type (vr
->type
)
1623 && gimple_assign_single_p (def_stmt
)
1624 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1625 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1628 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1629 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1630 &offset2
, &size2
, &maxsize2
);
1632 && operand_equal_p (base
, base2
, 0)
1633 && offset2
<= offset
1634 && offset2
+ size2
>= offset
+ maxsize
)
1636 tree val
= build_zero_cst (vr
->type
);
1637 return vn_reference_lookup_or_insert_for_pieces
1638 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1642 /* 3) Assignment from a constant. We can use folds native encode/interpret
1643 routines to extract the assigned bits. */
1644 else if (vn_walk_kind
== VN_WALKREWRITE
1645 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1646 && ref
->size
== maxsize
1647 && maxsize
% BITS_PER_UNIT
== 0
1648 && offset
% BITS_PER_UNIT
== 0
1649 && is_gimple_reg_type (vr
->type
)
1650 && gimple_assign_single_p (def_stmt
)
1651 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1654 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1655 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1656 &offset2
, &size2
, &maxsize2
);
1658 && maxsize2
== size2
1659 && size2
% BITS_PER_UNIT
== 0
1660 && offset2
% BITS_PER_UNIT
== 0
1661 && operand_equal_p (base
, base2
, 0)
1662 && offset2
<= offset
1663 && offset2
+ size2
>= offset
+ maxsize
)
1665 /* We support up to 512-bit values (for V8DFmode). */
1666 unsigned char buffer
[64];
1669 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1670 buffer
, sizeof (buffer
));
1673 tree val
= native_interpret_expr (vr
->type
,
1675 + ((offset
- offset2
)
1677 ref
->size
/ BITS_PER_UNIT
);
1679 return vn_reference_lookup_or_insert_for_pieces
1680 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1685 /* 4) Assignment from an SSA name which definition we may be able
1686 to access pieces from. */
1687 else if (ref
->size
== maxsize
1688 && is_gimple_reg_type (vr
->type
)
1689 && gimple_assign_single_p (def_stmt
)
1690 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1692 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1693 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1694 if (is_gimple_assign (def_stmt2
)
1695 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1696 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1697 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1700 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1701 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1702 &offset2
, &size2
, &maxsize2
);
1703 off
= offset
- offset2
;
1705 && maxsize2
== size2
1706 && operand_equal_p (base
, base2
, 0)
1707 && offset2
<= offset
1708 && offset2
+ size2
>= offset
+ maxsize
)
1710 tree val
= NULL_TREE
;
1712 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1713 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1716 val
= gimple_assign_rhs1 (def_stmt2
);
1717 else if (off
== elsz
)
1718 val
= gimple_assign_rhs2 (def_stmt2
);
1720 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1723 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1724 unsigned i
= off
/ elsz
;
1725 if (i
< CONSTRUCTOR_NELTS (ctor
))
1727 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1728 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1730 if (TREE_CODE (TREE_TYPE (elt
->value
))
1737 return vn_reference_lookup_or_insert_for_pieces
1738 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1743 /* 5) For aggregate copies translate the reference through them if
1744 the copy kills ref. */
1745 else if (vn_walk_kind
== VN_WALKREWRITE
1746 && gimple_assign_single_p (def_stmt
)
1747 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1748 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1749 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1752 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1754 auto_vec
<vn_reference_op_s
> rhs
;
1755 vn_reference_op_t vro
;
1761 /* See if the assignment kills REF. */
1762 base2
= ao_ref_base (&lhs_ref
);
1763 offset2
= lhs_ref
.offset
;
1764 size2
= lhs_ref
.size
;
1765 maxsize2
= lhs_ref
.max_size
;
1767 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1769 || offset2
+ size2
< offset
+ maxsize
)
1772 /* Find the common base of ref and the lhs. lhs_ops already
1773 contains valueized operands for the lhs. */
1774 i
= vr
->operands
.length () - 1;
1775 j
= lhs_ops
.length () - 1;
1776 while (j
>= 0 && i
>= 0
1777 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1783 /* ??? The innermost op should always be a MEM_REF and we already
1784 checked that the assignment to the lhs kills vr. Thus for
1785 aggregate copies using char[] types the vn_reference_op_eq
1786 may fail when comparing types for compatibility. But we really
1787 don't care here - further lookups with the rewritten operands
1788 will simply fail if we messed up types too badly. */
1789 if (j
== 0 && i
>= 0
1790 && lhs_ops
[0].opcode
== MEM_REF
1791 && lhs_ops
[0].off
!= -1
1792 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1795 /* i now points to the first additional op.
1796 ??? LHS may not be completely contained in VR, one or more
1797 VIEW_CONVERT_EXPRs could be in its way. We could at least
1798 try handling outermost VIEW_CONVERT_EXPRs. */
1802 /* Now re-write REF to be based on the rhs of the assignment. */
1803 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1804 /* We need to pre-pend vr->operands[0..i] to rhs. */
1805 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1807 vec
<vn_reference_op_s
> old
= vr
->operands
;
1808 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1809 if (old
== shared_lookup_references
1810 && vr
->operands
!= old
)
1811 shared_lookup_references
= vNULL
;
1814 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1815 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1816 vr
->operands
[i
+ 1 + j
] = *vro
;
1817 vr
->operands
= valueize_refs (vr
->operands
);
1818 vr
->hashcode
= vn_reference_compute_hash (vr
);
1820 /* Adjust *ref from the new operands. */
1821 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1823 /* This can happen with bitfields. */
1824 if (ref
->size
!= r
.size
)
1828 /* Do not update last seen VUSE after translating. */
1829 last_vuse_ptr
= NULL
;
1831 /* Keep looking for the adjusted *REF / VR pair. */
1835 /* 6) For memcpy copies translate the reference through them if
1836 the copy kills ref. */
1837 else if (vn_walk_kind
== VN_WALKREWRITE
1838 && is_gimple_reg_type (vr
->type
)
1839 /* ??? Handle BCOPY as well. */
1840 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1841 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1842 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1843 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1844 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1845 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1846 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1847 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
1851 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1852 vn_reference_op_s op
;
1856 /* Only handle non-variable, addressable refs. */
1857 if (ref
->size
!= maxsize
1858 || offset
% BITS_PER_UNIT
!= 0
1859 || ref
->size
% BITS_PER_UNIT
!= 0)
1862 /* Extract a pointer base and an offset for the destination. */
1863 lhs
= gimple_call_arg (def_stmt
, 0);
1865 if (TREE_CODE (lhs
) == SSA_NAME
)
1866 lhs
= SSA_VAL (lhs
);
1867 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1869 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1873 if (TREE_CODE (tem
) == MEM_REF
1874 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1876 lhs
= TREE_OPERAND (tem
, 0);
1877 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1879 else if (DECL_P (tem
))
1880 lhs
= build_fold_addr_expr (tem
);
1884 if (TREE_CODE (lhs
) != SSA_NAME
1885 && TREE_CODE (lhs
) != ADDR_EXPR
)
1888 /* Extract a pointer base and an offset for the source. */
1889 rhs
= gimple_call_arg (def_stmt
, 1);
1891 if (TREE_CODE (rhs
) == SSA_NAME
)
1892 rhs
= SSA_VAL (rhs
);
1893 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1895 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1899 if (TREE_CODE (tem
) == MEM_REF
1900 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1902 rhs
= TREE_OPERAND (tem
, 0);
1903 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1905 else if (DECL_P (tem
))
1906 rhs
= build_fold_addr_expr (tem
);
1910 if (TREE_CODE (rhs
) != SSA_NAME
1911 && TREE_CODE (rhs
) != ADDR_EXPR
)
1914 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
1916 /* The bases of the destination and the references have to agree. */
1917 if ((TREE_CODE (base
) != MEM_REF
1919 || (TREE_CODE (base
) == MEM_REF
1920 && (TREE_OPERAND (base
, 0) != lhs
1921 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
1923 && (TREE_CODE (lhs
) != ADDR_EXPR
1924 || TREE_OPERAND (lhs
, 0) != base
)))
1927 /* And the access has to be contained within the memcpy destination. */
1928 at
= offset
/ BITS_PER_UNIT
;
1929 if (TREE_CODE (base
) == MEM_REF
)
1930 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
1932 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1935 /* Make room for 2 operands in the new reference. */
1936 if (vr
->operands
.length () < 2)
1938 vec
<vn_reference_op_s
> old
= vr
->operands
;
1939 vr
->operands
.safe_grow_cleared (2);
1940 if (old
== shared_lookup_references
1941 && vr
->operands
!= old
)
1942 shared_lookup_references
.create (0);
1945 vr
->operands
.truncate (2);
1947 /* The looked-through reference is a simple MEM_REF. */
1948 memset (&op
, 0, sizeof (op
));
1950 op
.opcode
= MEM_REF
;
1951 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
1952 op
.off
= at
- lhs_offset
+ rhs_offset
;
1953 vr
->operands
[0] = op
;
1954 op
.type
= TREE_TYPE (rhs
);
1955 op
.opcode
= TREE_CODE (rhs
);
1958 vr
->operands
[1] = op
;
1959 vr
->hashcode
= vn_reference_compute_hash (vr
);
1961 /* Adjust *ref from the new operands. */
1962 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1964 /* This can happen with bitfields. */
1965 if (ref
->size
!= r
.size
)
1969 /* Do not update last seen VUSE after translating. */
1970 last_vuse_ptr
= NULL
;
1972 /* Keep looking for the adjusted *REF / VR pair. */
1976 /* Bail out and stop walking. */
1980 /* Lookup a reference operation by it's parts, in the current hash table.
1981 Returns the resulting value number if it exists in the hash table,
1982 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1983 vn_reference_t stored in the hashtable if something is found. */
1986 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
1987 vec
<vn_reference_op_s
> operands
,
1988 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
1990 struct vn_reference_s vr1
;
1998 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1999 shared_lookup_references
.truncate (0);
2000 shared_lookup_references
.safe_grow (operands
.length ());
2001 memcpy (shared_lookup_references
.address (),
2002 operands
.address (),
2003 sizeof (vn_reference_op_s
)
2004 * operands
.length ());
2005 vr1
.operands
= operands
= shared_lookup_references
2006 = valueize_refs (shared_lookup_references
);
2009 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2010 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2013 vn_reference_lookup_1 (&vr1
, vnresult
);
2015 && kind
!= VN_NOWALK
2019 vn_walk_kind
= kind
;
2020 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2022 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2023 vn_reference_lookup_2
,
2024 vn_reference_lookup_3
, &vr1
);
2025 if (vr1
.operands
!= operands
)
2026 vr1
.operands
.release ();
2030 return (*vnresult
)->result
;
2035 /* Lookup OP in the current hash table, and return the resulting value
2036 number if it exists in the hash table. Return NULL_TREE if it does
2037 not exist in the hash table or if the result field of the structure
2038 was NULL.. VNRESULT will be filled in with the vn_reference_t
2039 stored in the hashtable if one exists. */
2042 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2043 vn_reference_t
*vnresult
)
2045 vec
<vn_reference_op_s
> operands
;
2046 struct vn_reference_s vr1
;
2048 bool valuezied_anything
;
2053 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2054 vr1
.operands
= operands
2055 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2056 vr1
.type
= TREE_TYPE (op
);
2057 vr1
.set
= get_alias_set (op
);
2058 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2059 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2062 if (kind
!= VN_NOWALK
2065 vn_reference_t wvnresult
;
2067 /* Make sure to use a valueized reference if we valueized anything.
2068 Otherwise preserve the full reference for advanced TBAA. */
2069 if (!valuezied_anything
2070 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2072 ao_ref_init (&r
, op
);
2073 vn_walk_kind
= kind
;
2075 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2076 vn_reference_lookup_2
,
2077 vn_reference_lookup_3
, &vr1
);
2078 if (vr1
.operands
!= operands
)
2079 vr1
.operands
.release ();
2083 *vnresult
= wvnresult
;
2084 return wvnresult
->result
;
2090 return vn_reference_lookup_1 (&vr1
, vnresult
);
2094 /* Insert OP into the current hash table with a value number of
2095 RESULT, and return the resulting reference structure we created. */
2098 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2100 vn_reference_s
**slot
;
2104 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2105 if (TREE_CODE (result
) == SSA_NAME
)
2106 vr1
->value_id
= VN_INFO (result
)->value_id
;
2108 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2109 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2110 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2111 vr1
->type
= TREE_TYPE (op
);
2112 vr1
->set
= get_alias_set (op
);
2113 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2114 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2115 vr1
->result_vdef
= vdef
;
2117 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2120 /* Because we lookup stores using vuses, and value number failures
2121 using the vdefs (see visit_reference_op_store for how and why),
2122 it's possible that on failure we may try to insert an already
2123 inserted store. This is not wrong, there is no ssa name for a
2124 store that we could use as a differentiator anyway. Thus, unlike
2125 the other lookup functions, you cannot gcc_assert (!*slot)
2128 /* But free the old slot in case of a collision. */
2130 free_reference (*slot
);
2136 /* Insert a reference by it's pieces into the current hash table with
2137 a value number of RESULT. Return the resulting reference
2138 structure we created. */
2141 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2142 vec
<vn_reference_op_s
> operands
,
2143 tree result
, unsigned int value_id
)
2146 vn_reference_s
**slot
;
2149 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2150 vr1
->value_id
= value_id
;
2151 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2152 vr1
->operands
= valueize_refs (operands
);
2155 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2156 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2157 result
= SSA_VAL (result
);
2158 vr1
->result
= result
;
2160 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2163 /* At this point we should have all the things inserted that we have
2164 seen before, and we should never try inserting something that
2166 gcc_assert (!*slot
);
2168 free_reference (*slot
);
2174 /* Compute and return the hash value for nary operation VBO1. */
2177 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2182 for (i
= 0; i
< vno1
->length
; ++i
)
2183 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2184 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2186 if (vno1
->length
== 2
2187 && commutative_tree_code (vno1
->opcode
)
2188 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2190 tree temp
= vno1
->op
[0];
2191 vno1
->op
[0] = vno1
->op
[1];
2195 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2196 for (i
= 0; i
< vno1
->length
; ++i
)
2197 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2202 /* Compare nary operations VNO1 and VNO2 and return true if they are
2206 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2210 if (vno1
->hashcode
!= vno2
->hashcode
)
2213 if (vno1
->length
!= vno2
->length
)
2216 if (vno1
->opcode
!= vno2
->opcode
2217 || !types_compatible_p (vno1
->type
, vno2
->type
))
2220 for (i
= 0; i
< vno1
->length
; ++i
)
2221 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2227 /* Initialize VNO from the pieces provided. */
2230 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2231 enum tree_code code
, tree type
, tree
*ops
)
2234 vno
->length
= length
;
2236 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2239 /* Initialize VNO from OP. */
2242 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2246 vno
->opcode
= TREE_CODE (op
);
2247 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2248 vno
->type
= TREE_TYPE (op
);
2249 for (i
= 0; i
< vno
->length
; ++i
)
2250 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2253 /* Return the number of operands for a vn_nary ops structure from STMT. */
2256 vn_nary_length_from_stmt (gimple stmt
)
2258 switch (gimple_assign_rhs_code (stmt
))
2262 case VIEW_CONVERT_EXPR
:
2269 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2272 return gimple_num_ops (stmt
) - 1;
2276 /* Initialize VNO from STMT. */
2279 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2283 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2284 vno
->type
= gimple_expr_type (stmt
);
2285 switch (vno
->opcode
)
2289 case VIEW_CONVERT_EXPR
:
2291 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2296 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2297 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2298 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2302 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2303 for (i
= 0; i
< vno
->length
; ++i
)
2304 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2308 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2309 vno
->length
= gimple_num_ops (stmt
) - 1;
2310 for (i
= 0; i
< vno
->length
; ++i
)
2311 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2315 /* Compute the hashcode for VNO and look for it in the hash table;
2316 return the resulting value number if it exists in the hash table.
2317 Return NULL_TREE if it does not exist in the hash table or if the
2318 result field of the operation is NULL. VNRESULT will contain the
2319 vn_nary_op_t from the hashtable if it exists. */
2322 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2324 vn_nary_op_s
**slot
;
2329 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2330 slot
= current_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2331 if (!slot
&& current_info
== optimistic_info
)
2332 slot
= valid_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2337 return (*slot
)->result
;
2340 /* Lookup a n-ary operation by its pieces and return the resulting value
2341 number if it exists in the hash table. Return NULL_TREE if it does
2342 not exist in the hash table or if the result field of the operation
2343 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2347 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2348 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2350 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2351 sizeof_vn_nary_op (length
));
2352 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2353 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2356 /* Lookup OP in the current hash table, and return the resulting value
2357 number if it exists in the hash table. Return NULL_TREE if it does
2358 not exist in the hash table or if the result field of the operation
2359 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2363 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2366 = XALLOCAVAR (struct vn_nary_op_s
,
2367 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2368 init_vn_nary_op_from_op (vno1
, op
);
2369 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2372 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2373 value number if it exists in the hash table. Return NULL_TREE if
2374 it does not exist in the hash table. VNRESULT will contain the
2375 vn_nary_op_t from the hashtable if it exists. */
2378 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2381 = XALLOCAVAR (struct vn_nary_op_s
,
2382 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2383 init_vn_nary_op_from_stmt (vno1
, stmt
);
2384 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2387 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2390 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2392 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2395 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2399 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2401 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2402 ¤t_info
->nary_obstack
);
2404 vno1
->value_id
= value_id
;
2405 vno1
->length
= length
;
2406 vno1
->result
= result
;
2411 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2412 VNO->HASHCODE first. */
2415 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type table
,
2418 vn_nary_op_s
**slot
;
2421 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2423 slot
= table
.find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2424 gcc_assert (!*slot
);
2430 /* Insert a n-ary operation into the current hash table using it's
2431 pieces. Return the vn_nary_op_t structure we created and put in
2435 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2436 tree type
, tree
*ops
,
2437 tree result
, unsigned int value_id
)
2439 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2440 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2441 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2444 /* Insert OP into the current hash table with a value number of
2445 RESULT. Return the vn_nary_op_t structure we created and put in
2449 vn_nary_op_insert (tree op
, tree result
)
2451 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2454 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2455 init_vn_nary_op_from_op (vno1
, op
);
2456 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2459 /* Insert the rhs of STMT into the current hash table with a value number of
2463 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2466 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2467 result
, VN_INFO (result
)->value_id
);
2468 init_vn_nary_op_from_stmt (vno1
, stmt
);
2469 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2472 /* Compute a hashcode for PHI operation VP1 and return it. */
2474 static inline hashval_t
2475 vn_phi_compute_hash (vn_phi_t vp1
)
2482 result
= vp1
->block
->index
;
2484 /* If all PHI arguments are constants we need to distinguish
2485 the PHI node via its type. */
2487 result
+= vn_hash_type (type
);
2489 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2491 if (phi1op
== VN_TOP
)
2493 result
= iterative_hash_expr (phi1op
, result
);
2499 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2502 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2504 if (vp1
->hashcode
!= vp2
->hashcode
)
2507 if (vp1
->block
== vp2
->block
)
2512 /* If the PHI nodes do not have compatible types
2513 they are not the same. */
2514 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2517 /* Any phi in the same block will have it's arguments in the
2518 same edge order, because of how we store phi nodes. */
2519 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2521 tree phi2op
= vp2
->phiargs
[i
];
2522 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2524 if (!expressions_equal_p (phi1op
, phi2op
))
2532 static vec
<tree
> shared_lookup_phiargs
;
2534 /* Lookup PHI in the current hash table, and return the resulting
2535 value number if it exists in the hash table. Return NULL_TREE if
2536 it does not exist in the hash table. */
2539 vn_phi_lookup (gimple phi
)
2542 struct vn_phi_s vp1
;
2545 shared_lookup_phiargs
.truncate (0);
2547 /* Canonicalize the SSA_NAME's to their value number. */
2548 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2550 tree def
= PHI_ARG_DEF (phi
, i
);
2551 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2552 shared_lookup_phiargs
.safe_push (def
);
2554 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2555 vp1
.phiargs
= shared_lookup_phiargs
;
2556 vp1
.block
= gimple_bb (phi
);
2557 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2558 slot
= current_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2559 if (!slot
&& current_info
== optimistic_info
)
2560 slot
= valid_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2563 return (*slot
)->result
;
2566 /* Insert PHI into the current hash table with a value number of
2570 vn_phi_insert (gimple phi
, tree result
)
2573 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2575 vec
<tree
> args
= vNULL
;
2577 /* Canonicalize the SSA_NAME's to their value number. */
2578 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2580 tree def
= PHI_ARG_DEF (phi
, i
);
2581 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2582 args
.safe_push (def
);
2584 vp1
->value_id
= VN_INFO (result
)->value_id
;
2585 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2586 vp1
->phiargs
= args
;
2587 vp1
->block
= gimple_bb (phi
);
2588 vp1
->result
= result
;
2589 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2591 slot
= current_info
->phis
.find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2593 /* Because we iterate over phi operations more than once, it's
2594 possible the slot might already exist here, hence no assert.*/
2600 /* Print set of components in strongly connected component SCC to OUT. */
2603 print_scc (FILE *out
, vec
<tree
> scc
)
2608 fprintf (out
, "SCC consists of:");
2609 FOR_EACH_VEC_ELT (scc
, i
, var
)
2612 print_generic_expr (out
, var
, 0);
2614 fprintf (out
, "\n");
2617 /* Set the value number of FROM to TO, return true if it has changed
2621 set_ssa_val_to (tree from
, tree to
)
2623 tree currval
= SSA_VAL (from
);
2624 HOST_WIDE_INT toff
, coff
;
2628 if (currval
== from
)
2630 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2632 fprintf (dump_file
, "Not changing value number of ");
2633 print_generic_expr (dump_file
, from
, 0);
2634 fprintf (dump_file
, " from VARYING to ");
2635 print_generic_expr (dump_file
, to
, 0);
2636 fprintf (dump_file
, "\n");
2640 else if (TREE_CODE (to
) == SSA_NAME
2641 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2645 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2646 and invariants. So assert that here. */
2647 gcc_assert (to
!= NULL_TREE
2649 || TREE_CODE (to
) == SSA_NAME
2650 || is_gimple_min_invariant (to
)));
2652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2654 fprintf (dump_file
, "Setting value number of ");
2655 print_generic_expr (dump_file
, from
, 0);
2656 fprintf (dump_file
, " to ");
2657 print_generic_expr (dump_file
, to
, 0);
2661 && !operand_equal_p (currval
, to
, 0)
2662 /* ??? For addresses involving volatile objects or types operand_equal_p
2663 does not reliably detect ADDR_EXPRs as equal. We know we are only
2664 getting invariant gimple addresses here, so can use
2665 get_addr_base_and_unit_offset to do this comparison. */
2666 && !(TREE_CODE (currval
) == ADDR_EXPR
2667 && TREE_CODE (to
) == ADDR_EXPR
2668 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2669 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2672 VN_INFO (from
)->valnum
= to
;
2673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2674 fprintf (dump_file
, " (changed)\n");
2677 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2678 fprintf (dump_file
, "\n");
2682 /* Mark as processed all the definitions in the defining stmt of USE, or
2686 mark_use_processed (tree use
)
2690 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2692 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2694 VN_INFO (use
)->use_processed
= true;
2698 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2700 tree def
= DEF_FROM_PTR (defp
);
2702 VN_INFO (def
)->use_processed
= true;
2706 /* Set all definitions in STMT to value number to themselves.
2707 Return true if a value number changed. */
2710 defs_to_varying (gimple stmt
)
2712 bool changed
= false;
2716 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2718 tree def
= DEF_FROM_PTR (defp
);
2719 changed
|= set_ssa_val_to (def
, def
);
2724 static bool expr_has_constants (tree expr
);
2725 static tree
valueize_expr (tree expr
);
2727 /* Visit a copy between LHS and RHS, return true if the value number
2731 visit_copy (tree lhs
, tree rhs
)
2733 /* The copy may have a more interesting constant filled expression
2734 (we don't, since we know our RHS is just an SSA name). */
2735 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2736 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2738 /* And finally valueize. */
2739 rhs
= SSA_VAL (rhs
);
2741 return set_ssa_val_to (lhs
, rhs
);
2744 /* Visit a nary operator RHS, value number it, and return true if the
2745 value number of LHS has changed as a result. */
2748 visit_nary_op (tree lhs
, gimple stmt
)
2750 bool changed
= false;
2751 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2754 changed
= set_ssa_val_to (lhs
, result
);
2757 changed
= set_ssa_val_to (lhs
, lhs
);
2758 vn_nary_op_insert_stmt (stmt
, lhs
);
2764 /* Visit a call STMT storing into LHS. Return true if the value number
2765 of the LHS has changed as a result. */
2768 visit_reference_op_call (tree lhs
, gimple stmt
)
2770 bool changed
= false;
2771 struct vn_reference_s vr1
;
2772 vn_reference_t vnresult
= NULL
;
2773 tree vuse
= gimple_vuse (stmt
);
2774 tree vdef
= gimple_vdef (stmt
);
2776 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2777 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2780 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2781 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2782 vr1
.type
= gimple_expr_type (stmt
);
2784 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2785 vn_reference_lookup_1 (&vr1
, &vnresult
);
2789 if (vnresult
->result_vdef
)
2790 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2792 if (!vnresult
->result
&& lhs
)
2793 vnresult
->result
= lhs
;
2795 if (vnresult
->result
&& lhs
)
2797 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2799 if (VN_INFO (vnresult
->result
)->has_constants
)
2800 VN_INFO (lhs
)->has_constants
= true;
2805 vn_reference_s
**slot
;
2808 changed
|= set_ssa_val_to (vdef
, vdef
);
2810 changed
|= set_ssa_val_to (lhs
, lhs
);
2811 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2812 vr2
->vuse
= vr1
.vuse
;
2813 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2814 vr2
->type
= vr1
.type
;
2816 vr2
->hashcode
= vr1
.hashcode
;
2818 vr2
->result_vdef
= vdef
;
2819 slot
= current_info
->references
.find_slot_with_hash (vr2
, vr2
->hashcode
,
2822 free_reference (*slot
);
2829 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2830 and return true if the value number of the LHS has changed as a result. */
2833 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2835 bool changed
= false;
2839 last_vuse
= gimple_vuse (stmt
);
2840 last_vuse_ptr
= &last_vuse
;
2841 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2842 default_vn_walk_kind
, NULL
);
2843 last_vuse_ptr
= NULL
;
2845 /* If we have a VCE, try looking up its operand as it might be stored in
2846 a different type. */
2847 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2848 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2849 default_vn_walk_kind
, NULL
);
2851 /* We handle type-punning through unions by value-numbering based
2852 on offset and size of the access. Be prepared to handle a
2853 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2855 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2857 /* We will be setting the value number of lhs to the value number
2858 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2859 So first simplify and lookup this expression to see if it
2860 is already available. */
2861 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2862 if ((CONVERT_EXPR_P (val
)
2863 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2864 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2866 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2867 if ((CONVERT_EXPR_P (tem
)
2868 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2869 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2870 TREE_TYPE (val
), tem
)))
2874 if (!is_gimple_min_invariant (val
)
2875 && TREE_CODE (val
) != SSA_NAME
)
2876 result
= vn_nary_op_lookup (val
, NULL
);
2877 /* If the expression is not yet available, value-number lhs to
2878 a new SSA_NAME we create. */
2881 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2883 /* Initialize value-number information properly. */
2884 VN_INFO_GET (result
)->valnum
= result
;
2885 VN_INFO (result
)->value_id
= get_next_value_id ();
2886 VN_INFO (result
)->expr
= val
;
2887 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2888 VN_INFO (result
)->needs_insertion
= true;
2889 /* As all "inserted" statements are singleton SCCs, insert
2890 to the valid table. This is strictly needed to
2891 avoid re-generating new value SSA_NAMEs for the same
2892 expression during SCC iteration over and over (the
2893 optimistic table gets cleared after each iteration).
2894 We do not need to insert into the optimistic table, as
2895 lookups there will fall back to the valid table. */
2896 if (current_info
== optimistic_info
)
2898 current_info
= valid_info
;
2899 vn_nary_op_insert (val
, result
);
2900 current_info
= optimistic_info
;
2903 vn_nary_op_insert (val
, result
);
2904 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2906 fprintf (dump_file
, "Inserting name ");
2907 print_generic_expr (dump_file
, result
, 0);
2908 fprintf (dump_file
, " for expression ");
2909 print_generic_expr (dump_file
, val
, 0);
2910 fprintf (dump_file
, "\n");
2917 changed
= set_ssa_val_to (lhs
, result
);
2918 if (TREE_CODE (result
) == SSA_NAME
2919 && VN_INFO (result
)->has_constants
)
2921 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2922 VN_INFO (lhs
)->has_constants
= true;
2927 changed
= set_ssa_val_to (lhs
, lhs
);
2928 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
2935 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2936 and return true if the value number of the LHS has changed as a result. */
2939 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2941 bool changed
= false;
2942 vn_reference_t vnresult
= NULL
;
2943 tree result
, assign
;
2944 bool resultsame
= false;
2945 tree vuse
= gimple_vuse (stmt
);
2946 tree vdef
= gimple_vdef (stmt
);
2948 /* First we want to lookup using the *vuses* from the store and see
2949 if there the last store to this location with the same address
2952 The vuses represent the memory state before the store. If the
2953 memory state, address, and value of the store is the same as the
2954 last store to this location, then this store will produce the
2955 same memory state as that store.
2957 In this case the vdef versions for this store are value numbered to those
2958 vuse versions, since they represent the same memory state after
2961 Otherwise, the vdefs for the store are used when inserting into
2962 the table, since the store generates a new memory state. */
2964 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
2968 if (TREE_CODE (result
) == SSA_NAME
)
2969 result
= SSA_VAL (result
);
2970 if (TREE_CODE (op
) == SSA_NAME
)
2972 resultsame
= expressions_equal_p (result
, op
);
2975 if (!result
|| !resultsame
)
2977 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2978 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
2981 VN_INFO (vdef
)->use_processed
= true;
2982 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2986 if (!result
|| !resultsame
)
2988 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2990 fprintf (dump_file
, "No store match\n");
2991 fprintf (dump_file
, "Value numbering store ");
2992 print_generic_expr (dump_file
, lhs
, 0);
2993 fprintf (dump_file
, " to ");
2994 print_generic_expr (dump_file
, op
, 0);
2995 fprintf (dump_file
, "\n");
2997 /* Have to set value numbers before insert, since insert is
2998 going to valueize the references in-place. */
3001 changed
|= set_ssa_val_to (vdef
, vdef
);
3004 /* Do not insert structure copies into the tables. */
3005 if (is_gimple_min_invariant (op
)
3006 || is_gimple_reg (op
))
3007 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3009 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3010 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3014 /* We had a match, so value number the vdef to have the value
3015 number of the vuse it came from. */
3017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3018 fprintf (dump_file
, "Store matched earlier value,"
3019 "value numbering store vdefs to matching vuses.\n");
3021 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3027 /* Visit and value number PHI, return true if the value number
3031 visit_phi (gimple phi
)
3033 bool changed
= false;
3035 tree sameval
= VN_TOP
;
3036 bool allsame
= true;
3039 /* TODO: We could check for this in init_sccvn, and replace this
3040 with a gcc_assert. */
3041 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3042 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3044 /* See if all non-TOP arguments have the same value. TOP is
3045 equivalent to everything, so we can ignore it. */
3046 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3048 tree def
= PHI_ARG_DEF (phi
, i
);
3050 if (TREE_CODE (def
) == SSA_NAME
)
3051 def
= SSA_VAL (def
);
3054 if (sameval
== VN_TOP
)
3060 if (!expressions_equal_p (def
, sameval
))
3068 /* If all value numbered to the same value, the phi node has that
3072 if (is_gimple_min_invariant (sameval
))
3074 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
3075 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3079 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3080 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3083 if (TREE_CODE (sameval
) == SSA_NAME
)
3084 return visit_copy (PHI_RESULT (phi
), sameval
);
3086 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3089 /* Otherwise, see if it is equivalent to a phi node in this block. */
3090 result
= vn_phi_lookup (phi
);
3093 if (TREE_CODE (result
) == SSA_NAME
)
3094 changed
= visit_copy (PHI_RESULT (phi
), result
);
3096 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3100 vn_phi_insert (phi
, PHI_RESULT (phi
));
3101 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3102 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3103 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3109 /* Return true if EXPR contains constants. */
3112 expr_has_constants (tree expr
)
3114 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3117 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3120 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3121 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3122 /* Constants inside reference ops are rarely interesting, but
3123 it can take a lot of looking to find them. */
3125 case tcc_declaration
:
3128 return is_gimple_min_invariant (expr
);
3133 /* Return true if STMT contains constants. */
3136 stmt_has_constants (gimple stmt
)
3140 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3143 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3145 case GIMPLE_TERNARY_RHS
:
3146 tem
= gimple_assign_rhs3 (stmt
);
3147 if (TREE_CODE (tem
) == SSA_NAME
)
3148 tem
= SSA_VAL (tem
);
3149 if (is_gimple_min_invariant (tem
))
3153 case GIMPLE_BINARY_RHS
:
3154 tem
= gimple_assign_rhs2 (stmt
);
3155 if (TREE_CODE (tem
) == SSA_NAME
)
3156 tem
= SSA_VAL (tem
);
3157 if (is_gimple_min_invariant (tem
))
3161 case GIMPLE_SINGLE_RHS
:
3162 /* Constants inside reference ops are rarely interesting, but
3163 it can take a lot of looking to find them. */
3164 case GIMPLE_UNARY_RHS
:
3165 tem
= gimple_assign_rhs1 (stmt
);
3166 if (TREE_CODE (tem
) == SSA_NAME
)
3167 tem
= SSA_VAL (tem
);
3168 return is_gimple_min_invariant (tem
);
3176 /* Replace SSA_NAMES in expr with their value numbers, and return the
3178 This is performed in place. */
3181 valueize_expr (tree expr
)
3183 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3186 TREE_OPERAND (expr
, 1) = vn_valueize (TREE_OPERAND (expr
, 1));
3189 TREE_OPERAND (expr
, 0) = vn_valueize (TREE_OPERAND (expr
, 0));
3196 /* Simplify the binary expression RHS, and return the result if
3200 simplify_binary_expression (gimple stmt
)
3202 tree result
= NULL_TREE
;
3203 tree op0
= gimple_assign_rhs1 (stmt
);
3204 tree op1
= gimple_assign_rhs2 (stmt
);
3205 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3207 /* This will not catch every single case we could combine, but will
3208 catch those with constants. The goal here is to simultaneously
3209 combine constants between expressions, but avoid infinite
3210 expansion of expressions during simplification. */
3211 if (TREE_CODE (op0
) == SSA_NAME
)
3213 if (VN_INFO (op0
)->has_constants
3214 || TREE_CODE_CLASS (code
) == tcc_comparison
3215 || code
== COMPLEX_EXPR
)
3216 op0
= valueize_expr (vn_get_expr_for (op0
));
3218 op0
= vn_valueize (op0
);
3221 if (TREE_CODE (op1
) == SSA_NAME
)
3223 if (VN_INFO (op1
)->has_constants
3224 || code
== COMPLEX_EXPR
)
3225 op1
= valueize_expr (vn_get_expr_for (op1
));
3227 op1
= vn_valueize (op1
);
3230 /* Pointer plus constant can be represented as invariant address.
3231 Do so to allow further propatation, see also tree forwprop. */
3232 if (code
== POINTER_PLUS_EXPR
3233 && tree_fits_uhwi_p (op1
)
3234 && TREE_CODE (op0
) == ADDR_EXPR
3235 && is_gimple_min_invariant (op0
))
3236 return build_invariant_address (TREE_TYPE (op0
),
3237 TREE_OPERAND (op0
, 0),
3238 tree_to_uhwi (op1
));
3240 /* Avoid folding if nothing changed. */
3241 if (op0
== gimple_assign_rhs1 (stmt
)
3242 && op1
== gimple_assign_rhs2 (stmt
))
3245 fold_defer_overflow_warnings ();
3247 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3249 STRIP_USELESS_TYPE_CONVERSION (result
);
3251 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3254 /* Make sure result is not a complex expression consisting
3255 of operators of operators (IE (a + b) + (a + c))
3256 Otherwise, we will end up with unbounded expressions if
3257 fold does anything at all. */
3258 if (result
&& valid_gimple_rhs_p (result
))
3264 /* Simplify the unary expression RHS, and return the result if
3268 simplify_unary_expression (gimple stmt
)
3270 tree result
= NULL_TREE
;
3271 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3272 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3274 /* We handle some tcc_reference codes here that are all
3275 GIMPLE_ASSIGN_SINGLE codes. */
3276 if (code
== REALPART_EXPR
3277 || code
== IMAGPART_EXPR
3278 || code
== VIEW_CONVERT_EXPR
3279 || code
== BIT_FIELD_REF
)
3280 op0
= TREE_OPERAND (op0
, 0);
3282 if (TREE_CODE (op0
) != SSA_NAME
)
3286 if (VN_INFO (op0
)->has_constants
)
3287 op0
= valueize_expr (vn_get_expr_for (op0
));
3288 else if (CONVERT_EXPR_CODE_P (code
)
3289 || code
== REALPART_EXPR
3290 || code
== IMAGPART_EXPR
3291 || code
== VIEW_CONVERT_EXPR
3292 || code
== BIT_FIELD_REF
)
3294 /* We want to do tree-combining on conversion-like expressions.
3295 Make sure we feed only SSA_NAMEs or constants to fold though. */
3296 tree tem
= valueize_expr (vn_get_expr_for (op0
));
3297 if (UNARY_CLASS_P (tem
)
3298 || BINARY_CLASS_P (tem
)
3299 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3300 || TREE_CODE (tem
) == SSA_NAME
3301 || TREE_CODE (tem
) == CONSTRUCTOR
3302 || is_gimple_min_invariant (tem
))
3306 /* Avoid folding if nothing changed, but remember the expression. */
3307 if (op0
== orig_op0
)
3310 if (code
== BIT_FIELD_REF
)
3312 tree rhs
= gimple_assign_rhs1 (stmt
);
3313 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3314 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3317 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3320 STRIP_USELESS_TYPE_CONVERSION (result
);
3321 if (valid_gimple_rhs_p (result
))
3328 /* Try to simplify RHS using equivalences and constant folding. */
3331 try_to_simplify (gimple stmt
)
3333 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3336 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3337 in this case, there is no point in doing extra work. */
3338 if (code
== SSA_NAME
)
3341 /* First try constant folding based on our current lattice. */
3342 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3344 && (TREE_CODE (tem
) == SSA_NAME
3345 || is_gimple_min_invariant (tem
)))
3348 /* If that didn't work try combining multiple statements. */
3349 switch (TREE_CODE_CLASS (code
))
3352 /* Fallthrough for some unary codes that can operate on registers. */
3353 if (!(code
== REALPART_EXPR
3354 || code
== IMAGPART_EXPR
3355 || code
== VIEW_CONVERT_EXPR
3356 || code
== BIT_FIELD_REF
))
3358 /* We could do a little more with unary ops, if they expand
3359 into binary ops, but it's debatable whether it is worth it. */
3361 return simplify_unary_expression (stmt
);
3363 case tcc_comparison
:
3365 return simplify_binary_expression (stmt
);
3374 /* Visit and value number USE, return true if the value number
3378 visit_use (tree use
)
3380 bool changed
= false;
3381 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3383 mark_use_processed (use
);
3385 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3386 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3387 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3389 fprintf (dump_file
, "Value numbering ");
3390 print_generic_expr (dump_file
, use
, 0);
3391 fprintf (dump_file
, " stmt = ");
3392 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3395 /* Handle uninitialized uses. */
3396 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3397 changed
= set_ssa_val_to (use
, use
);
3400 if (gimple_code (stmt
) == GIMPLE_PHI
)
3401 changed
= visit_phi (stmt
);
3402 else if (gimple_has_volatile_ops (stmt
))
3403 changed
= defs_to_varying (stmt
);
3404 else if (is_gimple_assign (stmt
))
3406 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3407 tree lhs
= gimple_assign_lhs (stmt
);
3408 tree rhs1
= gimple_assign_rhs1 (stmt
);
3411 /* Shortcut for copies. Simplifying copies is pointless,
3412 since we copy the expression and value they represent. */
3413 if (code
== SSA_NAME
3414 && TREE_CODE (lhs
) == SSA_NAME
)
3416 changed
= visit_copy (lhs
, rhs1
);
3419 simplified
= try_to_simplify (stmt
);
3422 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3424 fprintf (dump_file
, "RHS ");
3425 print_gimple_expr (dump_file
, stmt
, 0, 0);
3426 fprintf (dump_file
, " simplified to ");
3427 print_generic_expr (dump_file
, simplified
, 0);
3428 if (TREE_CODE (lhs
) == SSA_NAME
)
3429 fprintf (dump_file
, " has constants %d\n",
3430 expr_has_constants (simplified
));
3432 fprintf (dump_file
, "\n");
3435 /* Setting value numbers to constants will occasionally
3436 screw up phi congruence because constants are not
3437 uniquely associated with a single ssa name that can be
3440 && is_gimple_min_invariant (simplified
)
3441 && TREE_CODE (lhs
) == SSA_NAME
)
3443 VN_INFO (lhs
)->expr
= simplified
;
3444 VN_INFO (lhs
)->has_constants
= true;
3445 changed
= set_ssa_val_to (lhs
, simplified
);
3449 && TREE_CODE (simplified
) == SSA_NAME
3450 && TREE_CODE (lhs
) == SSA_NAME
)
3452 changed
= visit_copy (lhs
, simplified
);
3455 else if (simplified
)
3457 if (TREE_CODE (lhs
) == SSA_NAME
)
3459 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3460 /* We have to unshare the expression or else
3461 valuizing may change the IL stream. */
3462 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3465 else if (stmt_has_constants (stmt
)
3466 && TREE_CODE (lhs
) == SSA_NAME
)
3467 VN_INFO (lhs
)->has_constants
= true;
3468 else if (TREE_CODE (lhs
) == SSA_NAME
)
3470 /* We reset expr and constantness here because we may
3471 have been value numbering optimistically, and
3472 iterating. They may become non-constant in this case,
3473 even if they were optimistically constant. */
3475 VN_INFO (lhs
)->has_constants
= false;
3476 VN_INFO (lhs
)->expr
= NULL_TREE
;
3479 if ((TREE_CODE (lhs
) == SSA_NAME
3480 /* We can substitute SSA_NAMEs that are live over
3481 abnormal edges with their constant value. */
3482 && !(gimple_assign_copy_p (stmt
)
3483 && is_gimple_min_invariant (rhs1
))
3485 && is_gimple_min_invariant (simplified
))
3486 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3487 /* Stores or copies from SSA_NAMEs that are live over
3488 abnormal edges are a problem. */
3489 || (code
== SSA_NAME
3490 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3491 changed
= defs_to_varying (stmt
);
3492 else if (REFERENCE_CLASS_P (lhs
)
3494 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3495 else if (TREE_CODE (lhs
) == SSA_NAME
)
3497 if ((gimple_assign_copy_p (stmt
)
3498 && is_gimple_min_invariant (rhs1
))
3500 && is_gimple_min_invariant (simplified
)))
3502 VN_INFO (lhs
)->has_constants
= true;
3504 changed
= set_ssa_val_to (lhs
, simplified
);
3506 changed
= set_ssa_val_to (lhs
, rhs1
);
3510 /* First try to lookup the simplified expression. */
3513 enum gimple_rhs_class rhs_class
;
3516 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3517 if ((rhs_class
== GIMPLE_UNARY_RHS
3518 || rhs_class
== GIMPLE_BINARY_RHS
3519 || rhs_class
== GIMPLE_TERNARY_RHS
)
3520 && valid_gimple_rhs_p (simplified
))
3522 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3525 changed
= set_ssa_val_to (lhs
, result
);
3531 /* Otherwise visit the original statement. */
3532 switch (vn_get_stmt_kind (stmt
))
3535 changed
= visit_nary_op (lhs
, stmt
);
3538 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3541 changed
= defs_to_varying (stmt
);
3547 changed
= defs_to_varying (stmt
);
3549 else if (is_gimple_call (stmt
))
3551 tree lhs
= gimple_call_lhs (stmt
);
3553 /* ??? We could try to simplify calls. */
3555 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3557 if (stmt_has_constants (stmt
))
3558 VN_INFO (lhs
)->has_constants
= true;
3561 /* We reset expr and constantness here because we may
3562 have been value numbering optimistically, and
3563 iterating. They may become non-constant in this case,
3564 even if they were optimistically constant. */
3565 VN_INFO (lhs
)->has_constants
= false;
3566 VN_INFO (lhs
)->expr
= NULL_TREE
;
3569 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3571 changed
= defs_to_varying (stmt
);
3576 if (!gimple_call_internal_p (stmt
)
3577 && (/* Calls to the same function with the same vuse
3578 and the same operands do not necessarily return the same
3579 value, unless they're pure or const. */
3580 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3581 /* If calls have a vdef, subsequent calls won't have
3582 the same incoming vuse. So, if 2 calls with vdef have the
3583 same vuse, we know they're not subsequent.
3584 We can value number 2 calls to the same function with the
3585 same vuse and the same operands which are not subsequent
3586 the same, because there is no code in the program that can
3587 compare the 2 values... */
3588 || (gimple_vdef (stmt
)
3589 /* ... unless the call returns a pointer which does
3590 not alias with anything else. In which case the
3591 information that the values are distinct are encoded
3593 && !(gimple_call_return_flags (stmt
) & ERF_NOALIAS
))))
3594 changed
= visit_reference_op_call (lhs
, stmt
);
3596 changed
= defs_to_varying (stmt
);
3599 changed
= defs_to_varying (stmt
);
3605 /* Compare two operands by reverse postorder index */
3608 compare_ops (const void *pa
, const void *pb
)
3610 const tree opa
= *((const tree
*)pa
);
3611 const tree opb
= *((const tree
*)pb
);
3612 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3613 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3617 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3618 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3619 else if (gimple_nop_p (opstmta
))
3621 else if (gimple_nop_p (opstmtb
))
3624 bba
= gimple_bb (opstmta
);
3625 bbb
= gimple_bb (opstmtb
);
3628 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3636 if (gimple_code (opstmta
) == GIMPLE_PHI
3637 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3638 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3639 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3641 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3643 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3644 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3646 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3648 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3651 /* Sort an array containing members of a strongly connected component
3652 SCC so that the members are ordered by RPO number.
3653 This means that when the sort is complete, iterating through the
3654 array will give you the members in RPO order. */
3657 sort_scc (vec
<tree
> scc
)
3659 scc
.qsort (compare_ops
);
3662 /* Insert the no longer used nary ONARY to the hash INFO. */
3665 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3667 size_t size
= sizeof_vn_nary_op (onary
->length
);
3668 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3669 &info
->nary_obstack
);
3670 memcpy (nary
, onary
, size
);
3671 vn_nary_op_insert_into (nary
, info
->nary
, false);
3674 /* Insert the no longer used phi OPHI to the hash INFO. */
3677 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3679 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3681 memcpy (phi
, ophi
, sizeof (*phi
));
3682 ophi
->phiargs
.create (0);
3683 slot
= info
->phis
.find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3684 gcc_assert (!*slot
);
3688 /* Insert the no longer used reference OREF to the hash INFO. */
3691 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3694 vn_reference_s
**slot
;
3695 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3696 memcpy (ref
, oref
, sizeof (*ref
));
3697 oref
->operands
.create (0);
3698 slot
= info
->references
.find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3700 free_reference (*slot
);
3704 /* Process a strongly connected component in the SSA graph. */
3707 process_scc (vec
<tree
> scc
)
3711 unsigned int iterations
= 0;
3712 bool changed
= true;
3713 vn_nary_op_iterator_type hin
;
3714 vn_phi_iterator_type hip
;
3715 vn_reference_iterator_type hir
;
3720 /* If the SCC has a single member, just visit it. */
3721 if (scc
.length () == 1)
3724 if (VN_INFO (use
)->use_processed
)
3726 /* We need to make sure it doesn't form a cycle itself, which can
3727 happen for self-referential PHI nodes. In that case we would
3728 end up inserting an expression with VN_TOP operands into the
3729 valid table which makes us derive bogus equivalences later.
3730 The cheapest way to check this is to assume it for all PHI nodes. */
3731 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3732 /* Fallthru to iteration. */ ;
3740 /* Iterate over the SCC with the optimistic table until it stops
3742 current_info
= optimistic_info
;
3747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3748 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3749 /* As we are value-numbering optimistically we have to
3750 clear the expression tables and the simplified expressions
3751 in each iteration until we converge. */
3752 optimistic_info
->nary
.empty ();
3753 optimistic_info
->phis
.empty ();
3754 optimistic_info
->references
.empty ();
3755 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3756 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3757 empty_alloc_pool (optimistic_info
->phis_pool
);
3758 empty_alloc_pool (optimistic_info
->references_pool
);
3759 FOR_EACH_VEC_ELT (scc
, i
, var
)
3760 VN_INFO (var
)->expr
= NULL_TREE
;
3761 FOR_EACH_VEC_ELT (scc
, i
, var
)
3762 changed
|= visit_use (var
);
3765 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3767 /* Finally, copy the contents of the no longer used optimistic
3768 table to the valid table. */
3769 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3770 copy_nary (nary
, valid_info
);
3771 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3772 copy_phi (phi
, valid_info
);
3773 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->references
,
3774 ref
, vn_reference_t
, hir
)
3775 copy_reference (ref
, valid_info
);
3777 current_info
= valid_info
;
3781 /* Pop the components of the found SCC for NAME off the SCC stack
3782 and process them. Returns true if all went well, false if
3783 we run into resource limits. */
3786 extract_and_process_scc_for_name (tree name
)
3791 /* Found an SCC, pop the components off the SCC stack and
3795 x
= sccstack
.pop ();
3797 VN_INFO (x
)->on_sccstack
= false;
3799 } while (x
!= name
);
3801 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3803 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3806 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3807 "SCC size %u exceeding %u\n", scc
.length (),
3808 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3813 if (scc
.length () > 1)
3816 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3817 print_scc (dump_file
, scc
);
3824 /* Depth first search on NAME to discover and process SCC's in the SSA
3826 Execution of this algorithm relies on the fact that the SCC's are
3827 popped off the stack in topological order.
3828 Returns true if successful, false if we stopped processing SCC's due
3829 to resource constraints. */
3834 vec
<ssa_op_iter
> itervec
= vNULL
;
3835 vec
<tree
> namevec
= vNULL
;
3836 use_operand_p usep
= NULL
;
3843 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3844 VN_INFO (name
)->visited
= true;
3845 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3847 sccstack
.safe_push (name
);
3848 VN_INFO (name
)->on_sccstack
= true;
3849 defstmt
= SSA_NAME_DEF_STMT (name
);
3851 /* Recursively DFS on our operands, looking for SCC's. */
3852 if (!gimple_nop_p (defstmt
))
3854 /* Push a new iterator. */
3855 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3856 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3858 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3861 clear_and_done_ssa_iter (&iter
);
3865 /* If we are done processing uses of a name, go up the stack
3866 of iterators and process SCCs as we found them. */
3867 if (op_iter_done (&iter
))
3869 /* See if we found an SCC. */
3870 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3871 if (!extract_and_process_scc_for_name (name
))
3878 /* Check if we are done. */
3879 if (namevec
.is_empty ())
3886 /* Restore the last use walker and continue walking there. */
3888 name
= namevec
.pop ();
3889 memcpy (&iter
, &itervec
.last (),
3890 sizeof (ssa_op_iter
));
3892 goto continue_walking
;
3895 use
= USE_FROM_PTR (usep
);
3897 /* Since we handle phi nodes, we will sometimes get
3898 invariants in the use expression. */
3899 if (TREE_CODE (use
) == SSA_NAME
)
3901 if (! (VN_INFO (use
)->visited
))
3903 /* Recurse by pushing the current use walking state on
3904 the stack and starting over. */
3905 itervec
.safe_push (iter
);
3906 namevec
.safe_push (name
);
3911 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3912 VN_INFO (use
)->low
);
3914 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3915 && VN_INFO (use
)->on_sccstack
)
3917 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3918 VN_INFO (name
)->low
);
3922 usep
= op_iter_next_use (&iter
);
3926 /* Allocate a value number table. */
3929 allocate_vn_table (vn_tables_t table
)
3931 table
->phis
.create (23);
3932 table
->nary
.create (23);
3933 table
->references
.create (23);
3935 gcc_obstack_init (&table
->nary_obstack
);
3936 table
->phis_pool
= create_alloc_pool ("VN phis",
3937 sizeof (struct vn_phi_s
),
3939 table
->references_pool
= create_alloc_pool ("VN references",
3940 sizeof (struct vn_reference_s
),
3944 /* Free a value number table. */
3947 free_vn_table (vn_tables_t table
)
3949 table
->phis
.dispose ();
3950 table
->nary
.dispose ();
3951 table
->references
.dispose ();
3952 obstack_free (&table
->nary_obstack
, NULL
);
3953 free_alloc_pool (table
->phis_pool
);
3954 free_alloc_pool (table
->references_pool
);
3962 int *rpo_numbers_temp
;
3964 calculate_dominance_info (CDI_DOMINATORS
);
3965 sccstack
.create (0);
3966 constant_to_value_id
.create (23);
3968 constant_value_ids
= BITMAP_ALLOC (NULL
);
3973 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
3974 /* VEC_alloc doesn't actually grow it to the right size, it just
3975 preallocates the space to do so. */
3976 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
3977 gcc_obstack_init (&vn_ssa_aux_obstack
);
3979 shared_lookup_phiargs
.create (0);
3980 shared_lookup_references
.create (0);
3981 rpo_numbers
= XNEWVEC (int, last_basic_block
);
3983 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
3984 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
3986 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3987 the i'th block in RPO order is bb. We want to map bb's to RPO
3988 numbers, so we need to rearrange this array. */
3989 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
3990 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
3992 XDELETE (rpo_numbers_temp
);
3994 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
3996 /* Create the VN_INFO structures, and initialize value numbers to
3998 for (i
= 0; i
< num_ssa_names
; i
++)
4000 tree name
= ssa_name (i
);
4003 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4004 VN_INFO (name
)->expr
= NULL_TREE
;
4005 VN_INFO (name
)->value_id
= 0;
4009 renumber_gimple_stmt_uids ();
4011 /* Create the valid and optimistic value numbering tables. */
4012 valid_info
= XCNEW (struct vn_tables_s
);
4013 allocate_vn_table (valid_info
);
4014 optimistic_info
= XCNEW (struct vn_tables_s
);
4015 allocate_vn_table (optimistic_info
);
4023 constant_to_value_id
.dispose ();
4024 BITMAP_FREE (constant_value_ids
);
4025 shared_lookup_phiargs
.release ();
4026 shared_lookup_references
.release ();
4027 XDELETEVEC (rpo_numbers
);
4029 for (i
= 0; i
< num_ssa_names
; i
++)
4031 tree name
= ssa_name (i
);
4033 && VN_INFO (name
)->needs_insertion
)
4034 release_ssa_name (name
);
4036 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4037 vn_ssa_aux_table
.release ();
4039 sccstack
.release ();
4040 free_vn_table (valid_info
);
4041 XDELETE (valid_info
);
4042 free_vn_table (optimistic_info
);
4043 XDELETE (optimistic_info
);
4046 /* Set *ID according to RESULT. */
4049 set_value_id_for_result (tree result
, unsigned int *id
)
4051 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4052 *id
= VN_INFO (result
)->value_id
;
4053 else if (result
&& is_gimple_min_invariant (result
))
4054 *id
= get_or_alloc_constant_value_id (result
);
4056 *id
= get_next_value_id ();
4059 /* Set the value ids in the valid hash tables. */
4062 set_hashtable_value_ids (void)
4064 vn_nary_op_iterator_type hin
;
4065 vn_phi_iterator_type hip
;
4066 vn_reference_iterator_type hir
;
4071 /* Now set the value ids of the things we had put in the hash
4074 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4075 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4077 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->phis
, vp
, vn_phi_t
, hip
)
4078 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4080 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->references
, vr
, vn_reference_t
, hir
)
4081 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4084 /* Do SCCVN. Returns true if it finished, false if we bailed out
4085 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4086 how we use the alias oracle walking during the VN process. */
4089 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4094 default_vn_walk_kind
= default_vn_walk_kind_
;
4097 current_info
= valid_info
;
4099 for (param
= DECL_ARGUMENTS (current_function_decl
);
4101 param
= DECL_CHAIN (param
))
4103 tree def
= ssa_default_def (cfun
, param
);
4105 VN_INFO (def
)->valnum
= def
;
4108 for (i
= 1; i
< num_ssa_names
; ++i
)
4110 tree name
= ssa_name (i
);
4112 && VN_INFO (name
)->visited
== false
4113 && !has_zero_uses (name
))
4121 /* Initialize the value ids. */
4123 for (i
= 1; i
< num_ssa_names
; ++i
)
4125 tree name
= ssa_name (i
);
4129 info
= VN_INFO (name
);
4130 if (info
->valnum
== name
4131 || info
->valnum
== VN_TOP
)
4132 info
->value_id
= get_next_value_id ();
4133 else if (is_gimple_min_invariant (info
->valnum
))
4134 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4138 for (i
= 1; i
< num_ssa_names
; ++i
)
4140 tree name
= ssa_name (i
);
4144 info
= VN_INFO (name
);
4145 if (TREE_CODE (info
->valnum
) == SSA_NAME
4146 && info
->valnum
!= name
4147 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4148 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4151 set_hashtable_value_ids ();
4153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4155 fprintf (dump_file
, "Value numbers:\n");
4156 for (i
= 0; i
< num_ssa_names
; i
++)
4158 tree name
= ssa_name (i
);
4160 && VN_INFO (name
)->visited
4161 && SSA_VAL (name
) != name
)
4163 print_generic_expr (dump_file
, name
, 0);
4164 fprintf (dump_file
, " = ");
4165 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4166 fprintf (dump_file
, "\n");
4174 /* Return the maximum value id we have ever seen. */
4177 get_max_value_id (void)
4179 return next_value_id
;
4182 /* Return the next unique value id. */
4185 get_next_value_id (void)
4187 return next_value_id
++;
4191 /* Compare two expressions E1 and E2 and return true if they are equal. */
4194 expressions_equal_p (tree e1
, tree e2
)
4196 /* The obvious case. */
4200 /* If only one of them is null, they cannot be equal. */
4204 /* Now perform the actual comparison. */
4205 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4206 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4213 /* Return true if the nary operation NARY may trap. This is a copy
4214 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4217 vn_nary_may_trap (vn_nary_op_t nary
)
4220 tree rhs2
= NULL_TREE
;
4221 bool honor_nans
= false;
4222 bool honor_snans
= false;
4223 bool fp_operation
= false;
4224 bool honor_trapv
= false;
4228 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4229 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4230 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4233 fp_operation
= FLOAT_TYPE_P (type
);
4236 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4237 honor_snans
= flag_signaling_nans
!= 0;
4239 else if (INTEGRAL_TYPE_P (type
)
4240 && TYPE_OVERFLOW_TRAPS (type
))
4243 if (nary
->length
>= 2)
4245 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4247 honor_nans
, honor_snans
, rhs2
,
4253 for (i
= 0; i
< nary
->length
; ++i
)
4254 if (tree_could_trap_p (nary
->op
[i
]))