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 "basic-block.h"
27 #include "gimple-pretty-print.h"
28 #include "tree-inline.h"
32 #include "hash-table.h"
33 #include "alloc-pool.h"
38 #include "tree-ssa-propagate.h"
39 #include "tree-ssa-sccvn.h"
41 /* This algorithm is based on the SCC algorithm presented by Keith
42 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
43 (http://citeseer.ist.psu.edu/41805.html). In
44 straight line code, it is equivalent to a regular hash based value
45 numbering that is performed in reverse postorder.
47 For code with cycles, there are two alternatives, both of which
48 require keeping the hashtables separate from the actual list of
49 value numbers for SSA names.
51 1. Iterate value numbering in an RPO walk of the blocks, removing
52 all the entries from the hashtable after each iteration (but
53 keeping the SSA name->value number mapping between iterations).
54 Iterate until it does not change.
56 2. Perform value numbering as part of an SCC walk on the SSA graph,
57 iterating only the cycles in the SSA graph until they do not change
58 (using a separate, optimistic hashtable for value numbering the SCC
61 The second is not just faster in practice (because most SSA graph
62 cycles do not involve all the variables in the graph), it also has
65 One of these nice properties is that when we pop an SCC off the
66 stack, we are guaranteed to have processed all the operands coming from
67 *outside of that SCC*, so we do not need to do anything special to
68 ensure they have value numbers.
70 Another nice property is that the SCC walk is done as part of a DFS
71 of the SSA graph, which makes it easy to perform combining and
72 simplifying operations at the same time.
74 The code below is deliberately written in a way that makes it easy
75 to separate the SCC walk from the other work it does.
77 In order to propagate constants through the code, we track which
78 expressions contain constants, and use those while folding. In
79 theory, we could also track expressions whose value numbers are
80 replaced, in case we end up folding based on expression
83 In order to value number memory, we assign value numbers to vuses.
84 This enables us to note that, for example, stores to the same
85 address of the same value from the same starting memory states are
89 1. We can iterate only the changing portions of the SCC's, but
90 I have not seen an SCC big enough for this to be a win.
91 2. If you differentiate between phi nodes for loops and phi nodes
92 for if-then-else, you can properly consider phi nodes in different
93 blocks for equivalence.
94 3. We could value number vuses in more cases, particularly, whole
99 /* vn_nary_op hashtable helpers. */
101 struct vn_nary_op_hasher
: typed_noop_remove
<vn_nary_op_s
>
103 typedef vn_nary_op_s value_type
;
104 typedef vn_nary_op_s compare_type
;
105 static inline hashval_t
hash (const value_type
*);
106 static inline bool equal (const value_type
*, const compare_type
*);
109 /* Return the computed hashcode for nary operation P1. */
112 vn_nary_op_hasher::hash (const value_type
*vno1
)
114 return vno1
->hashcode
;
117 /* Compare nary operations P1 and P2 and return true if they are
121 vn_nary_op_hasher::equal (const value_type
*vno1
, const compare_type
*vno2
)
123 return vn_nary_op_eq (vno1
, vno2
);
126 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
127 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
130 /* vn_phi hashtable helpers. */
133 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
137 typedef vn_phi_s value_type
;
138 typedef vn_phi_s compare_type
;
139 static inline hashval_t
hash (const value_type
*);
140 static inline bool equal (const value_type
*, const compare_type
*);
141 static inline void remove (value_type
*);
144 /* Return the computed hashcode for phi operation P1. */
147 vn_phi_hasher::hash (const value_type
*vp1
)
149 return vp1
->hashcode
;
152 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
155 vn_phi_hasher::equal (const value_type
*vp1
, const compare_type
*vp2
)
157 return vn_phi_eq (vp1
, vp2
);
160 /* Free a phi operation structure VP. */
163 vn_phi_hasher::remove (value_type
*phi
)
165 phi
->phiargs
.release ();
168 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
169 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
172 /* Compare two reference operands P1 and P2 for equality. Return true if
173 they are equal, and false otherwise. */
176 vn_reference_op_eq (const void *p1
, const void *p2
)
178 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
179 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
181 return (vro1
->opcode
== vro2
->opcode
182 /* We do not care for differences in type qualification. */
183 && (vro1
->type
== vro2
->type
184 || (vro1
->type
&& vro2
->type
185 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
186 TYPE_MAIN_VARIANT (vro2
->type
))))
187 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
188 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
189 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
192 /* Free a reference operation structure VP. */
195 free_reference (vn_reference_s
*vr
)
197 vr
->operands
.release ();
201 /* vn_reference hashtable helpers. */
203 struct vn_reference_hasher
205 typedef vn_reference_s value_type
;
206 typedef vn_reference_s compare_type
;
207 static inline hashval_t
hash (const value_type
*);
208 static inline bool equal (const value_type
*, const compare_type
*);
209 static inline void remove (value_type
*);
212 /* Return the hashcode for a given reference operation P1. */
215 vn_reference_hasher::hash (const value_type
*vr1
)
217 return vr1
->hashcode
;
221 vn_reference_hasher::equal (const value_type
*v
, const compare_type
*c
)
223 return vn_reference_eq (v
, c
);
227 vn_reference_hasher::remove (value_type
*v
)
232 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
233 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
236 /* The set of hashtables and alloc_pool's for their items. */
238 typedef struct vn_tables_s
240 vn_nary_op_table_type nary
;
241 vn_phi_table_type phis
;
242 vn_reference_table_type references
;
243 struct obstack nary_obstack
;
244 alloc_pool phis_pool
;
245 alloc_pool references_pool
;
249 /* vn_constant hashtable helpers. */
251 struct vn_constant_hasher
: typed_free_remove
<vn_constant_s
>
253 typedef vn_constant_s value_type
;
254 typedef vn_constant_s compare_type
;
255 static inline hashval_t
hash (const value_type
*);
256 static inline bool equal (const value_type
*, const compare_type
*);
259 /* Hash table hash function for vn_constant_t. */
262 vn_constant_hasher::hash (const value_type
*vc1
)
264 return vc1
->hashcode
;
267 /* Hash table equality function for vn_constant_t. */
270 vn_constant_hasher::equal (const value_type
*vc1
, const compare_type
*vc2
)
272 if (vc1
->hashcode
!= vc2
->hashcode
)
275 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
278 static hash_table
<vn_constant_hasher
> constant_to_value_id
;
279 static bitmap constant_value_ids
;
282 /* Valid hashtables storing information we have proven to be
285 static vn_tables_t valid_info
;
287 /* Optimistic hashtables storing information we are making assumptions about
288 during iterations. */
290 static vn_tables_t optimistic_info
;
292 /* Pointer to the set of hashtables that is currently being used.
293 Should always point to either the optimistic_info, or the
296 static vn_tables_t current_info
;
299 /* Reverse post order index for each basic block. */
301 static int *rpo_numbers
;
303 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
305 /* This represents the top of the VN lattice, which is the universal
310 /* Unique counter for our value ids. */
312 static unsigned int next_value_id
;
314 /* Next DFS number and the stack for strongly connected component
317 static unsigned int next_dfs_num
;
318 static vec
<tree
> sccstack
;
322 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
323 are allocated on an obstack for locality reasons, and to free them
324 without looping over the vec. */
326 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
327 static struct obstack vn_ssa_aux_obstack
;
329 /* Return the value numbering information for a given SSA name. */
334 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
335 gcc_checking_assert (res
);
339 /* Set the value numbering info for a given SSA name to a given
343 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
345 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
348 /* Initialize the value numbering info for a given SSA name.
349 This should be called just once for every SSA name. */
352 VN_INFO_GET (tree name
)
354 vn_ssa_aux_t newinfo
;
356 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
357 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
358 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
359 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
360 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
365 /* Get the representative expression for the SSA_NAME NAME. Returns
366 the representative SSA_NAME if there is no expression associated with it. */
369 vn_get_expr_for (tree name
)
371 vn_ssa_aux_t vn
= VN_INFO (name
);
373 tree expr
= NULL_TREE
;
376 if (vn
->valnum
== VN_TOP
)
379 /* If the value-number is a constant it is the representative
381 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
384 /* Get to the information of the value of this SSA_NAME. */
385 vn
= VN_INFO (vn
->valnum
);
387 /* If the value-number is a constant it is the representative
389 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
392 /* Else if we have an expression, return it. */
393 if (vn
->expr
!= NULL_TREE
)
396 /* Otherwise use the defining statement to build the expression. */
397 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
399 /* If the value number is not an assignment use it directly. */
400 if (!is_gimple_assign (def_stmt
))
403 /* FIXME tuples. This is incomplete and likely will miss some
405 code
= gimple_assign_rhs_code (def_stmt
);
406 switch (TREE_CODE_CLASS (code
))
409 if ((code
== REALPART_EXPR
410 || code
== IMAGPART_EXPR
411 || code
== VIEW_CONVERT_EXPR
)
412 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
414 expr
= fold_build1 (code
,
415 gimple_expr_type (def_stmt
),
416 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
420 expr
= fold_build1 (code
,
421 gimple_expr_type (def_stmt
),
422 gimple_assign_rhs1 (def_stmt
));
426 expr
= fold_build2 (code
,
427 gimple_expr_type (def_stmt
),
428 gimple_assign_rhs1 (def_stmt
),
429 gimple_assign_rhs2 (def_stmt
));
432 case tcc_exceptional
:
433 if (code
== CONSTRUCTOR
435 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
436 expr
= gimple_assign_rhs1 (def_stmt
);
441 if (expr
== NULL_TREE
)
444 /* Cache the expression. */
450 /* Return the vn_kind the expression computed by the stmt should be
454 vn_get_stmt_kind (gimple stmt
)
456 switch (gimple_code (stmt
))
464 enum tree_code code
= gimple_assign_rhs_code (stmt
);
465 tree rhs1
= gimple_assign_rhs1 (stmt
);
466 switch (get_gimple_rhs_class (code
))
468 case GIMPLE_UNARY_RHS
:
469 case GIMPLE_BINARY_RHS
:
470 case GIMPLE_TERNARY_RHS
:
472 case GIMPLE_SINGLE_RHS
:
473 switch (TREE_CODE_CLASS (code
))
476 /* VOP-less references can go through unary case. */
477 if ((code
== REALPART_EXPR
478 || code
== IMAGPART_EXPR
479 || code
== VIEW_CONVERT_EXPR
480 || code
== BIT_FIELD_REF
)
481 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
485 case tcc_declaration
:
492 if (code
== ADDR_EXPR
)
493 return (is_gimple_min_invariant (rhs1
)
494 ? VN_CONSTANT
: VN_REFERENCE
);
495 else if (code
== CONSTRUCTOR
)
508 /* Lookup a value id for CONSTANT and return it. If it does not
512 get_constant_value_id (tree constant
)
514 vn_constant_s
**slot
;
515 struct vn_constant_s vc
;
517 vc
.hashcode
= vn_hash_constant_with_type (constant
);
518 vc
.constant
= constant
;
519 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, NO_INSERT
);
521 return (*slot
)->value_id
;
525 /* Lookup a value id for CONSTANT, and if it does not exist, create a
526 new one and return it. If it does exist, return it. */
529 get_or_alloc_constant_value_id (tree constant
)
531 vn_constant_s
**slot
;
532 struct vn_constant_s vc
;
535 vc
.hashcode
= vn_hash_constant_with_type (constant
);
536 vc
.constant
= constant
;
537 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, INSERT
);
539 return (*slot
)->value_id
;
541 vcp
= XNEW (struct vn_constant_s
);
542 vcp
->hashcode
= vc
.hashcode
;
543 vcp
->constant
= constant
;
544 vcp
->value_id
= get_next_value_id ();
546 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
547 return vcp
->value_id
;
550 /* Return true if V is a value id for a constant. */
553 value_id_constant_p (unsigned int v
)
555 return bitmap_bit_p (constant_value_ids
, v
);
558 /* Compute the hash for a reference operand VRO1. */
561 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
563 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
565 result
= iterative_hash_expr (vro1
->op0
, result
);
567 result
= iterative_hash_expr (vro1
->op1
, result
);
569 result
= iterative_hash_expr (vro1
->op2
, result
);
573 /* Compute a hash for the reference operation VR1 and return it. */
576 vn_reference_compute_hash (const vn_reference_t vr1
)
578 hashval_t result
= 0;
580 vn_reference_op_t vro
;
581 HOST_WIDE_INT off
= -1;
584 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
586 if (vro
->opcode
== MEM_REF
)
588 else if (vro
->opcode
!= ADDR_EXPR
)
600 result
= iterative_hash_hashval_t (off
, result
);
603 && vro
->opcode
== ADDR_EXPR
)
607 tree op
= TREE_OPERAND (vro
->op0
, 0);
608 result
= iterative_hash_hashval_t (TREE_CODE (op
), result
);
609 result
= iterative_hash_expr (op
, result
);
613 result
= vn_reference_op_compute_hash (vro
, result
);
617 result
+= SSA_NAME_VERSION (vr1
->vuse
);
622 /* Return true if reference operations VR1 and VR2 are equivalent. This
623 means they have the same set of operands and vuses. */
626 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
630 if (vr1
->hashcode
!= vr2
->hashcode
)
633 /* Early out if this is not a hash collision. */
634 if (vr1
->hashcode
!= vr2
->hashcode
)
637 /* The VOP needs to be the same. */
638 if (vr1
->vuse
!= vr2
->vuse
)
641 /* If the operands are the same we are done. */
642 if (vr1
->operands
== vr2
->operands
)
645 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
648 if (INTEGRAL_TYPE_P (vr1
->type
)
649 && INTEGRAL_TYPE_P (vr2
->type
))
651 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
654 else if (INTEGRAL_TYPE_P (vr1
->type
)
655 && (TYPE_PRECISION (vr1
->type
)
656 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
658 else if (INTEGRAL_TYPE_P (vr2
->type
)
659 && (TYPE_PRECISION (vr2
->type
)
660 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
667 HOST_WIDE_INT off1
= 0, off2
= 0;
668 vn_reference_op_t vro1
, vro2
;
669 vn_reference_op_s tem1
, tem2
;
670 bool deref1
= false, deref2
= false;
671 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
673 if (vro1
->opcode
== MEM_REF
)
679 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
681 if (vro2
->opcode
== MEM_REF
)
689 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
691 memset (&tem1
, 0, sizeof (tem1
));
692 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
693 tem1
.type
= TREE_TYPE (tem1
.op0
);
694 tem1
.opcode
= TREE_CODE (tem1
.op0
);
698 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
700 memset (&tem2
, 0, sizeof (tem2
));
701 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
702 tem2
.type
= TREE_TYPE (tem2
.op0
);
703 tem2
.opcode
= TREE_CODE (tem2
.op0
);
707 if (deref1
!= deref2
)
709 if (!vn_reference_op_eq (vro1
, vro2
))
714 while (vr1
->operands
.length () != i
715 || vr2
->operands
.length () != j
);
720 /* Copy the operations present in load/store REF into RESULT, a vector of
721 vn_reference_op_s's. */
724 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
726 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
728 vn_reference_op_s temp
;
732 memset (&temp
, 0, sizeof (temp
));
733 temp
.type
= TREE_TYPE (ref
);
734 temp
.opcode
= TREE_CODE (ref
);
735 temp
.op0
= TMR_INDEX (ref
);
736 temp
.op1
= TMR_STEP (ref
);
737 temp
.op2
= TMR_OFFSET (ref
);
739 result
->quick_push (temp
);
741 memset (&temp
, 0, sizeof (temp
));
742 temp
.type
= NULL_TREE
;
743 temp
.opcode
= ERROR_MARK
;
744 temp
.op0
= TMR_INDEX2 (ref
);
746 result
->quick_push (temp
);
748 memset (&temp
, 0, sizeof (temp
));
749 temp
.type
= NULL_TREE
;
750 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
751 temp
.op0
= TMR_BASE (ref
);
753 result
->quick_push (temp
);
757 /* For non-calls, store the information that makes up the address. */
761 vn_reference_op_s temp
;
763 memset (&temp
, 0, sizeof (temp
));
764 temp
.type
= TREE_TYPE (ref
);
765 temp
.opcode
= TREE_CODE (ref
);
771 temp
.op0
= TREE_OPERAND (ref
, 1);
774 temp
.op0
= TREE_OPERAND (ref
, 1);
778 /* The base address gets its own vn_reference_op_s structure. */
779 temp
.op0
= TREE_OPERAND (ref
, 1);
780 if (host_integerp (TREE_OPERAND (ref
, 1), 0))
781 temp
.off
= TREE_INT_CST_LOW (TREE_OPERAND (ref
, 1));
784 /* Record bits and position. */
785 temp
.op0
= TREE_OPERAND (ref
, 1);
786 temp
.op1
= TREE_OPERAND (ref
, 2);
789 /* The field decl is enough to unambiguously specify the field,
790 a matching type is not necessary and a mismatching type
791 is always a spurious difference. */
792 temp
.type
= NULL_TREE
;
793 temp
.op0
= TREE_OPERAND (ref
, 1);
794 temp
.op1
= TREE_OPERAND (ref
, 2);
796 tree this_offset
= component_ref_field_offset (ref
);
798 && TREE_CODE (this_offset
) == INTEGER_CST
)
800 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
801 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
804 = tree_to_double_int (this_offset
)
805 + tree_to_double_int (bit_offset
)
806 .rshift (BITS_PER_UNIT
== 8
807 ? 3 : exact_log2 (BITS_PER_UNIT
));
808 if (off
.fits_shwi ())
814 case ARRAY_RANGE_REF
:
816 /* Record index as operand. */
817 temp
.op0
= TREE_OPERAND (ref
, 1);
818 /* Always record lower bounds and element size. */
819 temp
.op1
= array_ref_low_bound (ref
);
820 temp
.op2
= array_ref_element_size (ref
);
821 if (TREE_CODE (temp
.op0
) == INTEGER_CST
822 && TREE_CODE (temp
.op1
) == INTEGER_CST
823 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
825 double_int off
= tree_to_double_int (temp
.op0
);
826 off
+= -tree_to_double_int (temp
.op1
);
827 off
*= tree_to_double_int (temp
.op2
);
828 if (off
.fits_shwi ())
833 if (DECL_HARD_REGISTER (ref
))
842 /* Canonicalize decls to MEM[&decl] which is what we end up with
843 when valueizing MEM[ptr] with ptr = &decl. */
844 temp
.opcode
= MEM_REF
;
845 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
847 result
->safe_push (temp
);
848 temp
.opcode
= ADDR_EXPR
;
849 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
850 temp
.type
= TREE_TYPE (temp
.op0
);
864 if (is_gimple_min_invariant (ref
))
870 /* These are only interesting for their operands, their
871 existence, and their type. They will never be the last
872 ref in the chain of references (IE they require an
873 operand), so we don't have to put anything
874 for op* as it will be handled by the iteration */
876 case VIEW_CONVERT_EXPR
:
880 /* This is only interesting for its constant offset. */
881 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
886 result
->safe_push (temp
);
888 if (REFERENCE_CLASS_P (ref
)
889 || TREE_CODE (ref
) == MODIFY_EXPR
890 || TREE_CODE (ref
) == WITH_SIZE_EXPR
891 || (TREE_CODE (ref
) == ADDR_EXPR
892 && !is_gimple_min_invariant (ref
)))
893 ref
= TREE_OPERAND (ref
, 0);
899 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
900 operands in *OPS, the reference alias set SET and the reference type TYPE.
901 Return true if something useful was produced. */
904 ao_ref_init_from_vn_reference (ao_ref
*ref
,
905 alias_set_type set
, tree type
,
906 vec
<vn_reference_op_s
> ops
)
908 vn_reference_op_t op
;
910 tree base
= NULL_TREE
;
912 HOST_WIDE_INT offset
= 0;
913 HOST_WIDE_INT max_size
;
914 HOST_WIDE_INT size
= -1;
915 tree size_tree
= NULL_TREE
;
916 alias_set_type base_alias_set
= -1;
918 /* First get the final access size from just the outermost expression. */
920 if (op
->opcode
== COMPONENT_REF
)
921 size_tree
= DECL_SIZE (op
->op0
);
922 else if (op
->opcode
== BIT_FIELD_REF
)
926 enum machine_mode mode
= TYPE_MODE (type
);
928 size_tree
= TYPE_SIZE (type
);
930 size
= GET_MODE_BITSIZE (mode
);
932 if (size_tree
!= NULL_TREE
)
934 if (!host_integerp (size_tree
, 1))
937 size
= TREE_INT_CST_LOW (size_tree
);
940 /* Initially, maxsize is the same as the accessed element size.
941 In the following it will only grow (or become -1). */
944 /* Compute cumulative bit-offset for nested component-refs and array-refs,
945 and find the ultimate containing object. */
946 FOR_EACH_VEC_ELT (ops
, i
, op
)
950 /* These may be in the reference ops, but we cannot do anything
951 sensible with them here. */
953 /* Apart from ADDR_EXPR arguments to MEM_REF. */
954 if (base
!= NULL_TREE
955 && TREE_CODE (base
) == MEM_REF
957 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
959 vn_reference_op_t pop
= &ops
[i
-1];
960 base
= TREE_OPERAND (op
->op0
, 0);
967 offset
+= pop
->off
* BITS_PER_UNIT
;
975 /* Record the base objects. */
977 base_alias_set
= get_deref_alias_set (op
->op0
);
978 *op0_p
= build2 (MEM_REF
, op
->type
,
980 op0_p
= &TREE_OPERAND (*op0_p
, 0);
991 /* And now the usual component-reference style ops. */
993 offset
+= tree_low_cst (op
->op1
, 0);
998 tree field
= op
->op0
;
999 /* We do not have a complete COMPONENT_REF tree here so we
1000 cannot use component_ref_field_offset. Do the interesting
1004 || !host_integerp (DECL_FIELD_OFFSET (field
), 1))
1008 offset
+= (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field
))
1010 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
1015 case ARRAY_RANGE_REF
:
1017 /* We recorded the lower bound and the element size. */
1018 if (!host_integerp (op
->op0
, 0)
1019 || !host_integerp (op
->op1
, 0)
1020 || !host_integerp (op
->op2
, 0))
1024 HOST_WIDE_INT hindex
= TREE_INT_CST_LOW (op
->op0
);
1025 hindex
-= TREE_INT_CST_LOW (op
->op1
);
1026 hindex
*= TREE_INT_CST_LOW (op
->op2
);
1027 hindex
*= BITS_PER_UNIT
;
1039 case VIEW_CONVERT_EXPR
:
1056 if (base
== NULL_TREE
)
1059 ref
->ref
= NULL_TREE
;
1061 ref
->offset
= offset
;
1063 ref
->max_size
= max_size
;
1064 ref
->ref_alias_set
= set
;
1065 if (base_alias_set
!= -1)
1066 ref
->base_alias_set
= base_alias_set
;
1068 ref
->base_alias_set
= get_alias_set (base
);
1069 /* We discount volatiles from value-numbering elsewhere. */
1070 ref
->volatile_p
= false;
1075 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1076 vn_reference_op_s's. */
1079 copy_reference_ops_from_call (gimple call
,
1080 vec
<vn_reference_op_s
> *result
)
1082 vn_reference_op_s temp
;
1084 tree lhs
= gimple_call_lhs (call
);
1086 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1087 different. By adding the lhs here in the vector, we ensure that the
1088 hashcode is different, guaranteeing a different value number. */
1089 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1091 memset (&temp
, 0, sizeof (temp
));
1092 temp
.opcode
= MODIFY_EXPR
;
1093 temp
.type
= TREE_TYPE (lhs
);
1096 result
->safe_push (temp
);
1099 /* Copy the type, opcode, function being called and static chain. */
1100 memset (&temp
, 0, sizeof (temp
));
1101 temp
.type
= gimple_call_return_type (call
);
1102 temp
.opcode
= CALL_EXPR
;
1103 temp
.op0
= gimple_call_fn (call
);
1104 temp
.op1
= gimple_call_chain (call
);
1106 result
->safe_push (temp
);
1108 /* Copy the call arguments. As they can be references as well,
1109 just chain them together. */
1110 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1112 tree callarg
= gimple_call_arg (call
, i
);
1113 copy_reference_ops_from_ref (callarg
, result
);
1117 /* Create a vector of vn_reference_op_s structures from CALL, a
1118 call statement. The vector is not shared. */
1120 static vec
<vn_reference_op_s
>
1121 create_reference_ops_from_call (gimple call
)
1123 vec
<vn_reference_op_s
> result
= vNULL
;
1125 copy_reference_ops_from_call (call
, &result
);
1129 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1130 *I_P to point to the last element of the replacement. */
1132 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1135 unsigned int i
= *i_p
;
1136 vn_reference_op_t op
= &(*ops
)[i
];
1137 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1139 HOST_WIDE_INT addr_offset
= 0;
1141 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1142 from .foo.bar to the preceding MEM_REF offset and replace the
1143 address with &OBJ. */
1144 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1146 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1147 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1149 double_int off
= tree_to_double_int (mem_op
->op0
);
1150 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1151 off
+= double_int::from_shwi (addr_offset
);
1152 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1153 op
->op0
= build_fold_addr_expr (addr_base
);
1154 if (host_integerp (mem_op
->op0
, 0))
1155 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1161 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1162 *I_P to point to the last element of the replacement. */
1164 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1167 unsigned int i
= *i_p
;
1168 vn_reference_op_t op
= &(*ops
)[i
];
1169 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1171 enum tree_code code
;
1174 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1175 if (!is_gimple_assign (def_stmt
))
1178 code
= gimple_assign_rhs_code (def_stmt
);
1179 if (code
!= ADDR_EXPR
1180 && code
!= POINTER_PLUS_EXPR
)
1183 off
= tree_to_double_int (mem_op
->op0
);
1184 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1186 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1187 from .foo.bar to the preceding MEM_REF offset and replace the
1188 address with &OBJ. */
1189 if (code
== ADDR_EXPR
)
1191 tree addr
, addr_base
;
1192 HOST_WIDE_INT addr_offset
;
1194 addr
= gimple_assign_rhs1 (def_stmt
);
1195 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1198 || TREE_CODE (addr_base
) != MEM_REF
)
1201 off
+= double_int::from_shwi (addr_offset
);
1202 off
+= mem_ref_offset (addr_base
);
1203 op
->op0
= TREE_OPERAND (addr_base
, 0);
1208 ptr
= gimple_assign_rhs1 (def_stmt
);
1209 ptroff
= gimple_assign_rhs2 (def_stmt
);
1210 if (TREE_CODE (ptr
) != SSA_NAME
1211 || TREE_CODE (ptroff
) != INTEGER_CST
)
1214 off
+= tree_to_double_int (ptroff
);
1218 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1219 if (host_integerp (mem_op
->op0
, 0))
1220 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1223 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1224 op
->op0
= SSA_VAL (op
->op0
);
1225 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1226 op
->opcode
= TREE_CODE (op
->op0
);
1229 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1230 vn_reference_maybe_forwprop_address (ops
, i_p
);
1231 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1232 vn_reference_fold_indirect (ops
, i_p
);
1235 /* Optimize the reference REF to a constant if possible or return
1236 NULL_TREE if not. */
1239 fully_constant_vn_reference_p (vn_reference_t ref
)
1241 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1242 vn_reference_op_t op
;
1244 /* Try to simplify the translated expression if it is
1245 a call to a builtin function with at most two arguments. */
1247 if (op
->opcode
== CALL_EXPR
1248 && TREE_CODE (op
->op0
) == ADDR_EXPR
1249 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1250 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1251 && operands
.length () >= 2
1252 && operands
.length () <= 3)
1254 vn_reference_op_t arg0
, arg1
= NULL
;
1255 bool anyconst
= false;
1256 arg0
= &operands
[1];
1257 if (operands
.length () > 2)
1258 arg1
= &operands
[2];
1259 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1260 || (arg0
->opcode
== ADDR_EXPR
1261 && is_gimple_min_invariant (arg0
->op0
)))
1264 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1265 || (arg1
->opcode
== ADDR_EXPR
1266 && is_gimple_min_invariant (arg1
->op0
))))
1270 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1273 arg1
? arg1
->op0
: NULL
);
1275 && TREE_CODE (folded
) == NOP_EXPR
)
1276 folded
= TREE_OPERAND (folded
, 0);
1278 && is_gimple_min_invariant (folded
))
1283 /* Simplify reads from constant strings. */
1284 else if (op
->opcode
== ARRAY_REF
1285 && TREE_CODE (op
->op0
) == INTEGER_CST
1286 && integer_zerop (op
->op1
)
1287 && operands
.length () == 2)
1289 vn_reference_op_t arg0
;
1290 arg0
= &operands
[1];
1291 if (arg0
->opcode
== STRING_CST
1292 && (TYPE_MODE (op
->type
)
1293 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1294 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1295 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1296 && tree_int_cst_sgn (op
->op0
) >= 0
1297 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1298 return build_int_cst_type (op
->type
,
1299 (TREE_STRING_POINTER (arg0
->op0
)
1300 [TREE_INT_CST_LOW (op
->op0
)]));
1306 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1307 structures into their value numbers. This is done in-place, and
1308 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1309 whether any operands were valueized. */
1311 static vec
<vn_reference_op_s
>
1312 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1314 vn_reference_op_t vro
;
1317 *valueized_anything
= false;
1319 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1321 if (vro
->opcode
== SSA_NAME
1322 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1324 tree tem
= SSA_VAL (vro
->op0
);
1325 if (tem
!= vro
->op0
)
1327 *valueized_anything
= true;
1330 /* If it transforms from an SSA_NAME to a constant, update
1332 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1333 vro
->opcode
= TREE_CODE (vro
->op0
);
1335 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1337 tree tem
= SSA_VAL (vro
->op1
);
1338 if (tem
!= vro
->op1
)
1340 *valueized_anything
= true;
1344 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1346 tree tem
= SSA_VAL (vro
->op2
);
1347 if (tem
!= vro
->op2
)
1349 *valueized_anything
= true;
1353 /* If it transforms from an SSA_NAME to an address, fold with
1354 a preceding indirect reference. */
1357 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1358 && orig
[i
- 1].opcode
== MEM_REF
)
1359 vn_reference_fold_indirect (&orig
, &i
);
1361 && vro
->opcode
== SSA_NAME
1362 && orig
[i
- 1].opcode
== MEM_REF
)
1363 vn_reference_maybe_forwprop_address (&orig
, &i
);
1364 /* If it transforms a non-constant ARRAY_REF into a constant
1365 one, adjust the constant offset. */
1366 else if (vro
->opcode
== ARRAY_REF
1368 && TREE_CODE (vro
->op0
) == INTEGER_CST
1369 && TREE_CODE (vro
->op1
) == INTEGER_CST
1370 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1372 double_int off
= tree_to_double_int (vro
->op0
);
1373 off
+= -tree_to_double_int (vro
->op1
);
1374 off
*= tree_to_double_int (vro
->op2
);
1375 if (off
.fits_shwi ())
1383 static vec
<vn_reference_op_s
>
1384 valueize_refs (vec
<vn_reference_op_s
> orig
)
1387 return valueize_refs_1 (orig
, &tem
);
1390 static vec
<vn_reference_op_s
> shared_lookup_references
;
1392 /* Create a vector of vn_reference_op_s structures from REF, a
1393 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1394 this function. *VALUEIZED_ANYTHING will specify whether any
1395 operands were valueized. */
1397 static vec
<vn_reference_op_s
>
1398 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1402 shared_lookup_references
.truncate (0);
1403 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1404 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1405 valueized_anything
);
1406 return shared_lookup_references
;
1409 /* Create a vector of vn_reference_op_s structures from CALL, a
1410 call statement. The vector is shared among all callers of
1413 static vec
<vn_reference_op_s
>
1414 valueize_shared_reference_ops_from_call (gimple call
)
1418 shared_lookup_references
.truncate (0);
1419 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1420 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1421 return shared_lookup_references
;
1424 /* Lookup a SCCVN reference operation VR in the current hash table.
1425 Returns the resulting value number if it exists in the hash table,
1426 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1427 vn_reference_t stored in the hashtable if something is found. */
1430 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1432 vn_reference_s
**slot
;
1435 hash
= vr
->hashcode
;
1436 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1437 if (!slot
&& current_info
== optimistic_info
)
1438 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1442 *vnresult
= (vn_reference_t
)*slot
;
1443 return ((vn_reference_t
)*slot
)->result
;
1449 static tree
*last_vuse_ptr
;
1450 static vn_lookup_kind vn_walk_kind
;
1451 static vn_lookup_kind default_vn_walk_kind
;
1453 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1454 with the current VUSE and performs the expression lookup. */
1457 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1458 unsigned int cnt
, void *vr_
)
1460 vn_reference_t vr
= (vn_reference_t
)vr_
;
1461 vn_reference_s
**slot
;
1464 /* This bounds the stmt walks we perform on reference lookups
1465 to O(1) instead of O(N) where N is the number of dominating
1467 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1471 *last_vuse_ptr
= vuse
;
1473 /* Fixup vuse and hash. */
1475 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1476 vr
->vuse
= SSA_VAL (vuse
);
1478 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1480 hash
= vr
->hashcode
;
1481 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1482 if (!slot
&& current_info
== optimistic_info
)
1483 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1490 /* Lookup an existing or insert a new vn_reference entry into the
1491 value table for the VUSE, SET, TYPE, OPERANDS reference which
1492 has the value VALUE which is either a constant or an SSA name. */
1494 static vn_reference_t
1495 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1498 vec
<vn_reference_op_s
,
1502 struct vn_reference_s vr1
;
1503 vn_reference_t result
;
1506 vr1
.operands
= operands
;
1509 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1510 if (vn_reference_lookup_1 (&vr1
, &result
))
1512 if (TREE_CODE (value
) == SSA_NAME
)
1513 value_id
= VN_INFO (value
)->value_id
;
1515 value_id
= get_or_alloc_constant_value_id (value
);
1516 return vn_reference_insert_pieces (vuse
, set
, type
,
1517 operands
.copy (), value
, value_id
);
1520 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1521 from the statement defining VUSE and if not successful tries to
1522 translate *REFP and VR_ through an aggregate copy at the definition
1526 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
)
1528 vn_reference_t vr
= (vn_reference_t
)vr_
;
1529 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1531 HOST_WIDE_INT offset
, maxsize
;
1532 static vec
<vn_reference_op_s
>
1535 bool lhs_ref_ok
= false;
1537 /* First try to disambiguate after value-replacing in the definitions LHS. */
1538 if (is_gimple_assign (def_stmt
))
1540 vec
<vn_reference_op_s
> tem
;
1541 tree lhs
= gimple_assign_lhs (def_stmt
);
1542 bool valueized_anything
= false;
1543 /* Avoid re-allocation overhead. */
1544 lhs_ops
.truncate (0);
1545 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1547 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1548 gcc_assert (lhs_ops
== tem
);
1549 if (valueized_anything
)
1551 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1552 get_alias_set (lhs
),
1553 TREE_TYPE (lhs
), lhs_ops
);
1555 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1560 ao_ref_init (&lhs_ref
, lhs
);
1565 base
= ao_ref_base (ref
);
1566 offset
= ref
->offset
;
1567 maxsize
= ref
->max_size
;
1569 /* If we cannot constrain the size of the reference we cannot
1570 test if anything kills it. */
1574 /* We can't deduce anything useful from clobbers. */
1575 if (gimple_clobber_p (def_stmt
))
1578 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1579 from that definition.
1581 if (is_gimple_reg_type (vr
->type
)
1582 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1583 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1584 && host_integerp (gimple_call_arg (def_stmt
, 2), 1)
1585 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1587 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1589 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1590 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1591 size2
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2)) * 8;
1592 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1593 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2))
1595 && operand_equal_p (base
, base2
, 0)
1596 && offset2
<= offset
1597 && offset2
+ size2
>= offset
+ maxsize
)
1599 tree val
= build_zero_cst (vr
->type
);
1600 return vn_reference_lookup_or_insert_for_pieces
1601 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1605 /* 2) Assignment from an empty CONSTRUCTOR. */
1606 else if (is_gimple_reg_type (vr
->type
)
1607 && gimple_assign_single_p (def_stmt
)
1608 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1609 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1612 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1613 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1614 &offset2
, &size2
, &maxsize2
);
1616 && operand_equal_p (base
, base2
, 0)
1617 && offset2
<= offset
1618 && offset2
+ size2
>= offset
+ maxsize
)
1620 tree val
= build_zero_cst (vr
->type
);
1621 return vn_reference_lookup_or_insert_for_pieces
1622 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1626 /* 3) Assignment from a constant. We can use folds native encode/interpret
1627 routines to extract the assigned bits. */
1628 else if (vn_walk_kind
== VN_WALKREWRITE
1629 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1630 && ref
->size
== maxsize
1631 && maxsize
% BITS_PER_UNIT
== 0
1632 && offset
% BITS_PER_UNIT
== 0
1633 && is_gimple_reg_type (vr
->type
)
1634 && gimple_assign_single_p (def_stmt
)
1635 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1638 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1639 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1640 &offset2
, &size2
, &maxsize2
);
1642 && maxsize2
== size2
1643 && size2
% BITS_PER_UNIT
== 0
1644 && offset2
% BITS_PER_UNIT
== 0
1645 && operand_equal_p (base
, base2
, 0)
1646 && offset2
<= offset
1647 && offset2
+ size2
>= offset
+ maxsize
)
1649 /* We support up to 512-bit values (for V8DFmode). */
1650 unsigned char buffer
[64];
1653 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1654 buffer
, sizeof (buffer
));
1657 tree val
= native_interpret_expr (vr
->type
,
1659 + ((offset
- offset2
)
1661 ref
->size
/ BITS_PER_UNIT
);
1663 return vn_reference_lookup_or_insert_for_pieces
1664 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1669 /* 4) Assignment from an SSA name which definition we may be able
1670 to access pieces from. */
1671 else if (ref
->size
== maxsize
1672 && is_gimple_reg_type (vr
->type
)
1673 && gimple_assign_single_p (def_stmt
)
1674 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1676 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1677 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1678 if (is_gimple_assign (def_stmt2
)
1679 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1680 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1681 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1684 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1685 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1686 &offset2
, &size2
, &maxsize2
);
1687 off
= offset
- offset2
;
1689 && maxsize2
== size2
1690 && operand_equal_p (base
, base2
, 0)
1691 && offset2
<= offset
1692 && offset2
+ size2
>= offset
+ maxsize
)
1694 tree val
= NULL_TREE
;
1696 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1697 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1700 val
= gimple_assign_rhs1 (def_stmt2
);
1701 else if (off
== elsz
)
1702 val
= gimple_assign_rhs2 (def_stmt2
);
1704 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1707 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1708 unsigned i
= off
/ elsz
;
1709 if (i
< CONSTRUCTOR_NELTS (ctor
))
1711 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1712 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1714 if (TREE_CODE (TREE_TYPE (elt
->value
))
1721 return vn_reference_lookup_or_insert_for_pieces
1722 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1727 /* 5) For aggregate copies translate the reference through them if
1728 the copy kills ref. */
1729 else if (vn_walk_kind
== VN_WALKREWRITE
1730 && gimple_assign_single_p (def_stmt
)
1731 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1732 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1733 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1736 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1738 vec
<vn_reference_op_s
>
1740 vn_reference_op_t vro
;
1746 /* See if the assignment kills REF. */
1747 base2
= ao_ref_base (&lhs_ref
);
1748 offset2
= lhs_ref
.offset
;
1749 size2
= lhs_ref
.size
;
1750 maxsize2
= lhs_ref
.max_size
;
1752 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1754 || offset2
+ size2
< offset
+ maxsize
)
1757 /* Find the common base of ref and the lhs. lhs_ops already
1758 contains valueized operands for the lhs. */
1759 i
= vr
->operands
.length () - 1;
1760 j
= lhs_ops
.length () - 1;
1761 while (j
>= 0 && i
>= 0
1762 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1768 /* ??? The innermost op should always be a MEM_REF and we already
1769 checked that the assignment to the lhs kills vr. Thus for
1770 aggregate copies using char[] types the vn_reference_op_eq
1771 may fail when comparing types for compatibility. But we really
1772 don't care here - further lookups with the rewritten operands
1773 will simply fail if we messed up types too badly. */
1774 if (j
== 0 && i
>= 0
1775 && lhs_ops
[0].opcode
== MEM_REF
1776 && lhs_ops
[0].off
!= -1
1777 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1780 /* i now points to the first additional op.
1781 ??? LHS may not be completely contained in VR, one or more
1782 VIEW_CONVERT_EXPRs could be in its way. We could at least
1783 try handling outermost VIEW_CONVERT_EXPRs. */
1787 /* Now re-write REF to be based on the rhs of the assignment. */
1788 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1789 /* We need to pre-pend vr->operands[0..i] to rhs. */
1790 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1792 vec
<vn_reference_op_s
> old
= vr
->operands
;
1793 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1794 if (old
== shared_lookup_references
1795 && vr
->operands
!= old
)
1796 shared_lookup_references
= vNULL
;
1799 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1800 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1801 vr
->operands
[i
+ 1 + j
] = *vro
;
1803 vr
->operands
= valueize_refs (vr
->operands
);
1804 vr
->hashcode
= vn_reference_compute_hash (vr
);
1806 /* Adjust *ref from the new operands. */
1807 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1809 /* This can happen with bitfields. */
1810 if (ref
->size
!= r
.size
)
1814 /* Do not update last seen VUSE after translating. */
1815 last_vuse_ptr
= NULL
;
1817 /* Keep looking for the adjusted *REF / VR pair. */
1821 /* 6) For memcpy copies translate the reference through them if
1822 the copy kills ref. */
1823 else if (vn_walk_kind
== VN_WALKREWRITE
1824 && is_gimple_reg_type (vr
->type
)
1825 /* ??? Handle BCOPY as well. */
1826 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1827 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1828 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1829 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1830 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1831 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1832 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1833 && host_integerp (gimple_call_arg (def_stmt
, 2), 1))
1837 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1838 vn_reference_op_s op
;
1842 /* Only handle non-variable, addressable refs. */
1843 if (ref
->size
!= maxsize
1844 || offset
% BITS_PER_UNIT
!= 0
1845 || ref
->size
% BITS_PER_UNIT
!= 0)
1848 /* Extract a pointer base and an offset for the destination. */
1849 lhs
= gimple_call_arg (def_stmt
, 0);
1851 if (TREE_CODE (lhs
) == SSA_NAME
)
1852 lhs
= SSA_VAL (lhs
);
1853 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1855 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1859 if (TREE_CODE (tem
) == MEM_REF
1860 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1862 lhs
= TREE_OPERAND (tem
, 0);
1863 lhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1865 else if (DECL_P (tem
))
1866 lhs
= build_fold_addr_expr (tem
);
1870 if (TREE_CODE (lhs
) != SSA_NAME
1871 && TREE_CODE (lhs
) != ADDR_EXPR
)
1874 /* Extract a pointer base and an offset for the source. */
1875 rhs
= gimple_call_arg (def_stmt
, 1);
1877 if (TREE_CODE (rhs
) == SSA_NAME
)
1878 rhs
= SSA_VAL (rhs
);
1879 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1881 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1885 if (TREE_CODE (tem
) == MEM_REF
1886 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1888 rhs
= TREE_OPERAND (tem
, 0);
1889 rhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1891 else if (DECL_P (tem
))
1892 rhs
= build_fold_addr_expr (tem
);
1896 if (TREE_CODE (rhs
) != SSA_NAME
1897 && TREE_CODE (rhs
) != ADDR_EXPR
)
1900 copy_size
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2));
1902 /* The bases of the destination and the references have to agree. */
1903 if ((TREE_CODE (base
) != MEM_REF
1905 || (TREE_CODE (base
) == MEM_REF
1906 && (TREE_OPERAND (base
, 0) != lhs
1907 || !host_integerp (TREE_OPERAND (base
, 1), 1)))
1909 && (TREE_CODE (lhs
) != ADDR_EXPR
1910 || TREE_OPERAND (lhs
, 0) != base
)))
1913 /* And the access has to be contained within the memcpy destination. */
1914 at
= offset
/ BITS_PER_UNIT
;
1915 if (TREE_CODE (base
) == MEM_REF
)
1916 at
+= TREE_INT_CST_LOW (TREE_OPERAND (base
, 1));
1918 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1921 /* Make room for 2 operands in the new reference. */
1922 if (vr
->operands
.length () < 2)
1924 vec
<vn_reference_op_s
> old
= vr
->operands
;
1925 vr
->operands
.safe_grow_cleared (2);
1926 if (old
== shared_lookup_references
1927 && vr
->operands
!= old
)
1928 shared_lookup_references
.create (0);
1931 vr
->operands
.truncate (2);
1933 /* The looked-through reference is a simple MEM_REF. */
1934 memset (&op
, 0, sizeof (op
));
1936 op
.opcode
= MEM_REF
;
1937 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
1938 op
.off
= at
- lhs_offset
+ rhs_offset
;
1939 vr
->operands
[0] = op
;
1940 op
.type
= TREE_TYPE (rhs
);
1941 op
.opcode
= TREE_CODE (rhs
);
1944 vr
->operands
[1] = op
;
1945 vr
->hashcode
= vn_reference_compute_hash (vr
);
1947 /* Adjust *ref from the new operands. */
1948 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1950 /* This can happen with bitfields. */
1951 if (ref
->size
!= r
.size
)
1955 /* Do not update last seen VUSE after translating. */
1956 last_vuse_ptr
= NULL
;
1958 /* Keep looking for the adjusted *REF / VR pair. */
1962 /* Bail out and stop walking. */
1966 /* Lookup a reference operation by it's parts, in the current hash table.
1967 Returns the resulting value number if it exists in the hash table,
1968 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1969 vn_reference_t stored in the hashtable if something is found. */
1972 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
1973 vec
<vn_reference_op_s
> operands
,
1974 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
1976 struct vn_reference_s vr1
;
1984 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1985 shared_lookup_references
.truncate (0);
1986 shared_lookup_references
.safe_grow (operands
.length ());
1987 memcpy (shared_lookup_references
.address (),
1988 operands
.address (),
1989 sizeof (vn_reference_op_s
)
1990 * operands
.length ());
1991 vr1
.operands
= operands
= shared_lookup_references
1992 = valueize_refs (shared_lookup_references
);
1995 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1996 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
1999 vn_reference_lookup_1 (&vr1
, vnresult
);
2001 && kind
!= VN_NOWALK
2005 vn_walk_kind
= kind
;
2006 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2008 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2009 vn_reference_lookup_2
,
2010 vn_reference_lookup_3
, &vr1
);
2011 if (vr1
.operands
!= operands
)
2012 vr1
.operands
.release ();
2016 return (*vnresult
)->result
;
2021 /* Lookup OP in the current hash table, and return the resulting value
2022 number if it exists in the hash table. Return NULL_TREE if it does
2023 not exist in the hash table or if the result field of the structure
2024 was NULL.. VNRESULT will be filled in with the vn_reference_t
2025 stored in the hashtable if one exists. */
2028 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2029 vn_reference_t
*vnresult
)
2031 vec
<vn_reference_op_s
> operands
;
2032 struct vn_reference_s vr1
;
2034 bool valuezied_anything
;
2039 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2040 vr1
.operands
= operands
2041 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2042 vr1
.type
= TREE_TYPE (op
);
2043 vr1
.set
= get_alias_set (op
);
2044 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2045 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2048 if (kind
!= VN_NOWALK
2051 vn_reference_t wvnresult
;
2053 /* Make sure to use a valueized reference if we valueized anything.
2054 Otherwise preserve the full reference for advanced TBAA. */
2055 if (!valuezied_anything
2056 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2058 ao_ref_init (&r
, op
);
2059 vn_walk_kind
= kind
;
2061 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2062 vn_reference_lookup_2
,
2063 vn_reference_lookup_3
, &vr1
);
2064 if (vr1
.operands
!= operands
)
2065 vr1
.operands
.release ();
2069 *vnresult
= wvnresult
;
2070 return wvnresult
->result
;
2076 return vn_reference_lookup_1 (&vr1
, vnresult
);
2080 /* Insert OP into the current hash table with a value number of
2081 RESULT, and return the resulting reference structure we created. */
2084 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2086 vn_reference_s
**slot
;
2090 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2091 if (TREE_CODE (result
) == SSA_NAME
)
2092 vr1
->value_id
= VN_INFO (result
)->value_id
;
2094 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2095 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2096 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2097 vr1
->type
= TREE_TYPE (op
);
2098 vr1
->set
= get_alias_set (op
);
2099 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2100 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2101 vr1
->result_vdef
= vdef
;
2103 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2106 /* Because we lookup stores using vuses, and value number failures
2107 using the vdefs (see visit_reference_op_store for how and why),
2108 it's possible that on failure we may try to insert an already
2109 inserted store. This is not wrong, there is no ssa name for a
2110 store that we could use as a differentiator anyway. Thus, unlike
2111 the other lookup functions, you cannot gcc_assert (!*slot)
2114 /* But free the old slot in case of a collision. */
2116 free_reference (*slot
);
2122 /* Insert a reference by it's pieces into the current hash table with
2123 a value number of RESULT. Return the resulting reference
2124 structure we created. */
2127 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2128 vec
<vn_reference_op_s
> operands
,
2129 tree result
, unsigned int value_id
)
2132 vn_reference_s
**slot
;
2135 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2136 vr1
->value_id
= value_id
;
2137 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2138 vr1
->operands
= valueize_refs (operands
);
2141 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2142 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2143 result
= SSA_VAL (result
);
2144 vr1
->result
= result
;
2146 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2149 /* At this point we should have all the things inserted that we have
2150 seen before, and we should never try inserting something that
2152 gcc_assert (!*slot
);
2154 free_reference (*slot
);
2160 /* Compute and return the hash value for nary operation VBO1. */
2163 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2168 for (i
= 0; i
< vno1
->length
; ++i
)
2169 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2170 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2172 if (vno1
->length
== 2
2173 && commutative_tree_code (vno1
->opcode
)
2174 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2176 tree temp
= vno1
->op
[0];
2177 vno1
->op
[0] = vno1
->op
[1];
2181 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2182 for (i
= 0; i
< vno1
->length
; ++i
)
2183 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2188 /* Compare nary operations VNO1 and VNO2 and return true if they are
2192 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2196 if (vno1
->hashcode
!= vno2
->hashcode
)
2199 if (vno1
->length
!= vno2
->length
)
2202 if (vno1
->opcode
!= vno2
->opcode
2203 || !types_compatible_p (vno1
->type
, vno2
->type
))
2206 for (i
= 0; i
< vno1
->length
; ++i
)
2207 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2213 /* Initialize VNO from the pieces provided. */
2216 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2217 enum tree_code code
, tree type
, tree
*ops
)
2220 vno
->length
= length
;
2222 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2225 /* Initialize VNO from OP. */
2228 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2232 vno
->opcode
= TREE_CODE (op
);
2233 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2234 vno
->type
= TREE_TYPE (op
);
2235 for (i
= 0; i
< vno
->length
; ++i
)
2236 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2239 /* Return the number of operands for a vn_nary ops structure from STMT. */
2242 vn_nary_length_from_stmt (gimple stmt
)
2244 switch (gimple_assign_rhs_code (stmt
))
2248 case VIEW_CONVERT_EXPR
:
2255 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2258 return gimple_num_ops (stmt
) - 1;
2262 /* Initialize VNO from STMT. */
2265 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2269 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2270 vno
->type
= gimple_expr_type (stmt
);
2271 switch (vno
->opcode
)
2275 case VIEW_CONVERT_EXPR
:
2277 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2282 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2283 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2284 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2288 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2289 for (i
= 0; i
< vno
->length
; ++i
)
2290 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2294 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2295 vno
->length
= gimple_num_ops (stmt
) - 1;
2296 for (i
= 0; i
< vno
->length
; ++i
)
2297 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2301 /* Compute the hashcode for VNO and look for it in the hash table;
2302 return the resulting value number if it exists in the hash table.
2303 Return NULL_TREE if it does not exist in the hash table or if the
2304 result field of the operation is NULL. VNRESULT will contain the
2305 vn_nary_op_t from the hashtable if it exists. */
2308 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2310 vn_nary_op_s
**slot
;
2315 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2316 slot
= current_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2317 if (!slot
&& current_info
== optimistic_info
)
2318 slot
= valid_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2323 return (*slot
)->result
;
2326 /* Lookup a n-ary operation by its pieces and return the resulting value
2327 number if it exists in the hash table. Return NULL_TREE if it does
2328 not exist in the hash table or if the result field of the operation
2329 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2333 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2334 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2336 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2337 sizeof_vn_nary_op (length
));
2338 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2339 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2342 /* Lookup OP in the current hash table, and return the resulting value
2343 number if it exists in the hash table. Return NULL_TREE if it does
2344 not exist in the hash table or if the result field of the operation
2345 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2349 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2352 = XALLOCAVAR (struct vn_nary_op_s
,
2353 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2354 init_vn_nary_op_from_op (vno1
, op
);
2355 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2358 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2359 value number if it exists in the hash table. Return NULL_TREE if
2360 it does not exist in the hash table. VNRESULT will contain the
2361 vn_nary_op_t from the hashtable if it exists. */
2364 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2367 = XALLOCAVAR (struct vn_nary_op_s
,
2368 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2369 init_vn_nary_op_from_stmt (vno1
, stmt
);
2370 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2373 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2376 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2378 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2381 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2385 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2387 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2388 ¤t_info
->nary_obstack
);
2390 vno1
->value_id
= value_id
;
2391 vno1
->length
= length
;
2392 vno1
->result
= result
;
2397 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2398 VNO->HASHCODE first. */
2401 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type table
,
2404 vn_nary_op_s
**slot
;
2407 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2409 slot
= table
.find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2410 gcc_assert (!*slot
);
2416 /* Insert a n-ary operation into the current hash table using it's
2417 pieces. Return the vn_nary_op_t structure we created and put in
2421 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2422 tree type
, tree
*ops
,
2423 tree result
, unsigned int value_id
)
2425 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2426 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2427 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2430 /* Insert OP into the current hash table with a value number of
2431 RESULT. Return the vn_nary_op_t structure we created and put in
2435 vn_nary_op_insert (tree op
, tree result
)
2437 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2440 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2441 init_vn_nary_op_from_op (vno1
, op
);
2442 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2445 /* Insert the rhs of STMT into the current hash table with a value number of
2449 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2452 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2453 result
, VN_INFO (result
)->value_id
);
2454 init_vn_nary_op_from_stmt (vno1
, stmt
);
2455 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2458 /* Compute a hashcode for PHI operation VP1 and return it. */
2460 static inline hashval_t
2461 vn_phi_compute_hash (vn_phi_t vp1
)
2468 result
= vp1
->block
->index
;
2470 /* If all PHI arguments are constants we need to distinguish
2471 the PHI node via its type. */
2473 result
+= vn_hash_type (type
);
2475 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2477 if (phi1op
== VN_TOP
)
2479 result
= iterative_hash_expr (phi1op
, result
);
2485 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2488 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2490 if (vp1
->hashcode
!= vp2
->hashcode
)
2493 if (vp1
->block
== vp2
->block
)
2498 /* If the PHI nodes do not have compatible types
2499 they are not the same. */
2500 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2503 /* Any phi in the same block will have it's arguments in the
2504 same edge order, because of how we store phi nodes. */
2505 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2507 tree phi2op
= vp2
->phiargs
[i
];
2508 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2510 if (!expressions_equal_p (phi1op
, phi2op
))
2518 static vec
<tree
> shared_lookup_phiargs
;
2520 /* Lookup PHI in the current hash table, and return the resulting
2521 value number if it exists in the hash table. Return NULL_TREE if
2522 it does not exist in the hash table. */
2525 vn_phi_lookup (gimple phi
)
2528 struct vn_phi_s vp1
;
2531 shared_lookup_phiargs
.truncate (0);
2533 /* Canonicalize the SSA_NAME's to their value number. */
2534 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2536 tree def
= PHI_ARG_DEF (phi
, i
);
2537 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2538 shared_lookup_phiargs
.safe_push (def
);
2540 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2541 vp1
.phiargs
= shared_lookup_phiargs
;
2542 vp1
.block
= gimple_bb (phi
);
2543 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2544 slot
= current_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2545 if (!slot
&& current_info
== optimistic_info
)
2546 slot
= valid_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2549 return (*slot
)->result
;
2552 /* Insert PHI into the current hash table with a value number of
2556 vn_phi_insert (gimple phi
, tree result
)
2559 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2561 vec
<tree
> args
= vNULL
;
2563 /* Canonicalize the SSA_NAME's to their value number. */
2564 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2566 tree def
= PHI_ARG_DEF (phi
, i
);
2567 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2568 args
.safe_push (def
);
2570 vp1
->value_id
= VN_INFO (result
)->value_id
;
2571 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2572 vp1
->phiargs
= args
;
2573 vp1
->block
= gimple_bb (phi
);
2574 vp1
->result
= result
;
2575 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2577 slot
= current_info
->phis
.find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2579 /* Because we iterate over phi operations more than once, it's
2580 possible the slot might already exist here, hence no assert.*/
2586 /* Print set of components in strongly connected component SCC to OUT. */
2589 print_scc (FILE *out
, vec
<tree
> scc
)
2594 fprintf (out
, "SCC consists of:");
2595 FOR_EACH_VEC_ELT (scc
, i
, var
)
2598 print_generic_expr (out
, var
, 0);
2600 fprintf (out
, "\n");
2603 /* Set the value number of FROM to TO, return true if it has changed
2607 set_ssa_val_to (tree from
, tree to
)
2609 tree currval
= SSA_VAL (from
);
2610 HOST_WIDE_INT toff
, coff
;
2614 if (currval
== from
)
2616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2618 fprintf (dump_file
, "Not changing value number of ");
2619 print_generic_expr (dump_file
, from
, 0);
2620 fprintf (dump_file
, " from VARYING to ");
2621 print_generic_expr (dump_file
, to
, 0);
2622 fprintf (dump_file
, "\n");
2626 else if (TREE_CODE (to
) == SSA_NAME
2627 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2631 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2632 and invariants. So assert that here. */
2633 gcc_assert (to
!= NULL_TREE
2635 || TREE_CODE (to
) == SSA_NAME
2636 || is_gimple_min_invariant (to
)));
2638 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2640 fprintf (dump_file
, "Setting value number of ");
2641 print_generic_expr (dump_file
, from
, 0);
2642 fprintf (dump_file
, " to ");
2643 print_generic_expr (dump_file
, to
, 0);
2647 && !operand_equal_p (currval
, to
, 0)
2648 /* ??? For addresses involving volatile objects or types operand_equal_p
2649 does not reliably detect ADDR_EXPRs as equal. We know we are only
2650 getting invariant gimple addresses here, so can use
2651 get_addr_base_and_unit_offset to do this comparison. */
2652 && !(TREE_CODE (currval
) == ADDR_EXPR
2653 && TREE_CODE (to
) == ADDR_EXPR
2654 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2655 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2658 VN_INFO (from
)->valnum
= to
;
2659 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2660 fprintf (dump_file
, " (changed)\n");
2663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2664 fprintf (dump_file
, "\n");
2668 /* Mark as processed all the definitions in the defining stmt of USE, or
2672 mark_use_processed (tree use
)
2676 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2678 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2680 VN_INFO (use
)->use_processed
= true;
2684 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2686 tree def
= DEF_FROM_PTR (defp
);
2688 VN_INFO (def
)->use_processed
= true;
2692 /* Set all definitions in STMT to value number to themselves.
2693 Return true if a value number changed. */
2696 defs_to_varying (gimple stmt
)
2698 bool changed
= false;
2702 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2704 tree def
= DEF_FROM_PTR (defp
);
2705 changed
|= set_ssa_val_to (def
, def
);
2710 static bool expr_has_constants (tree expr
);
2711 static tree
valueize_expr (tree expr
);
2713 /* Visit a copy between LHS and RHS, return true if the value number
2717 visit_copy (tree lhs
, tree rhs
)
2719 /* The copy may have a more interesting constant filled expression
2720 (we don't, since we know our RHS is just an SSA name). */
2721 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2722 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2724 /* And finally valueize. */
2725 rhs
= SSA_VAL (rhs
);
2727 return set_ssa_val_to (lhs
, rhs
);
2730 /* Visit a nary operator RHS, value number it, and return true if the
2731 value number of LHS has changed as a result. */
2734 visit_nary_op (tree lhs
, gimple stmt
)
2736 bool changed
= false;
2737 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2740 changed
= set_ssa_val_to (lhs
, result
);
2743 changed
= set_ssa_val_to (lhs
, lhs
);
2744 vn_nary_op_insert_stmt (stmt
, lhs
);
2750 /* Visit a call STMT storing into LHS. Return true if the value number
2751 of the LHS has changed as a result. */
2754 visit_reference_op_call (tree lhs
, gimple stmt
)
2756 bool changed
= false;
2757 struct vn_reference_s vr1
;
2758 vn_reference_t vnresult
= NULL
;
2759 tree vuse
= gimple_vuse (stmt
);
2760 tree vdef
= gimple_vdef (stmt
);
2762 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2763 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2766 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2767 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2768 vr1
.type
= gimple_expr_type (stmt
);
2770 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2771 vn_reference_lookup_1 (&vr1
, &vnresult
);
2775 if (vnresult
->result_vdef
)
2776 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2778 if (!vnresult
->result
&& lhs
)
2779 vnresult
->result
= lhs
;
2781 if (vnresult
->result
&& lhs
)
2783 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2785 if (VN_INFO (vnresult
->result
)->has_constants
)
2786 VN_INFO (lhs
)->has_constants
= true;
2791 vn_reference_s
**slot
;
2794 changed
|= set_ssa_val_to (vdef
, vdef
);
2796 changed
|= set_ssa_val_to (lhs
, lhs
);
2797 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2798 vr2
->vuse
= vr1
.vuse
;
2799 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2800 vr2
->type
= vr1
.type
;
2802 vr2
->hashcode
= vr1
.hashcode
;
2804 vr2
->result_vdef
= vdef
;
2805 slot
= current_info
->references
.find_slot_with_hash (vr2
, vr2
->hashcode
,
2808 free_reference (*slot
);
2815 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2816 and return true if the value number of the LHS has changed as a result. */
2819 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2821 bool changed
= false;
2825 last_vuse
= gimple_vuse (stmt
);
2826 last_vuse_ptr
= &last_vuse
;
2827 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2828 default_vn_walk_kind
, NULL
);
2829 last_vuse_ptr
= NULL
;
2831 /* If we have a VCE, try looking up its operand as it might be stored in
2832 a different type. */
2833 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2834 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2835 default_vn_walk_kind
, NULL
);
2837 /* We handle type-punning through unions by value-numbering based
2838 on offset and size of the access. Be prepared to handle a
2839 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2841 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2843 /* We will be setting the value number of lhs to the value number
2844 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2845 So first simplify and lookup this expression to see if it
2846 is already available. */
2847 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2848 if ((CONVERT_EXPR_P (val
)
2849 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2850 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2852 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2853 if ((CONVERT_EXPR_P (tem
)
2854 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2855 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2856 TREE_TYPE (val
), tem
)))
2860 if (!is_gimple_min_invariant (val
)
2861 && TREE_CODE (val
) != SSA_NAME
)
2862 result
= vn_nary_op_lookup (val
, NULL
);
2863 /* If the expression is not yet available, value-number lhs to
2864 a new SSA_NAME we create. */
2867 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2869 /* Initialize value-number information properly. */
2870 VN_INFO_GET (result
)->valnum
= result
;
2871 VN_INFO (result
)->value_id
= get_next_value_id ();
2872 VN_INFO (result
)->expr
= val
;
2873 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2874 VN_INFO (result
)->needs_insertion
= true;
2875 /* As all "inserted" statements are singleton SCCs, insert
2876 to the valid table. This is strictly needed to
2877 avoid re-generating new value SSA_NAMEs for the same
2878 expression during SCC iteration over and over (the
2879 optimistic table gets cleared after each iteration).
2880 We do not need to insert into the optimistic table, as
2881 lookups there will fall back to the valid table. */
2882 if (current_info
== optimistic_info
)
2884 current_info
= valid_info
;
2885 vn_nary_op_insert (val
, result
);
2886 current_info
= optimistic_info
;
2889 vn_nary_op_insert (val
, result
);
2890 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2892 fprintf (dump_file
, "Inserting name ");
2893 print_generic_expr (dump_file
, result
, 0);
2894 fprintf (dump_file
, " for expression ");
2895 print_generic_expr (dump_file
, val
, 0);
2896 fprintf (dump_file
, "\n");
2903 changed
= set_ssa_val_to (lhs
, result
);
2904 if (TREE_CODE (result
) == SSA_NAME
2905 && VN_INFO (result
)->has_constants
)
2907 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2908 VN_INFO (lhs
)->has_constants
= true;
2913 changed
= set_ssa_val_to (lhs
, lhs
);
2914 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
2921 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2922 and return true if the value number of the LHS has changed as a result. */
2925 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2927 bool changed
= false;
2928 vn_reference_t vnresult
= NULL
;
2929 tree result
, assign
;
2930 bool resultsame
= false;
2931 tree vuse
= gimple_vuse (stmt
);
2932 tree vdef
= gimple_vdef (stmt
);
2934 /* First we want to lookup using the *vuses* from the store and see
2935 if there the last store to this location with the same address
2938 The vuses represent the memory state before the store. If the
2939 memory state, address, and value of the store is the same as the
2940 last store to this location, then this store will produce the
2941 same memory state as that store.
2943 In this case the vdef versions for this store are value numbered to those
2944 vuse versions, since they represent the same memory state after
2947 Otherwise, the vdefs for the store are used when inserting into
2948 the table, since the store generates a new memory state. */
2950 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
2954 if (TREE_CODE (result
) == SSA_NAME
)
2955 result
= SSA_VAL (result
);
2956 if (TREE_CODE (op
) == SSA_NAME
)
2958 resultsame
= expressions_equal_p (result
, op
);
2961 if (!result
|| !resultsame
)
2963 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2964 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
2967 VN_INFO (vdef
)->use_processed
= true;
2968 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2972 if (!result
|| !resultsame
)
2974 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2976 fprintf (dump_file
, "No store match\n");
2977 fprintf (dump_file
, "Value numbering store ");
2978 print_generic_expr (dump_file
, lhs
, 0);
2979 fprintf (dump_file
, " to ");
2980 print_generic_expr (dump_file
, op
, 0);
2981 fprintf (dump_file
, "\n");
2983 /* Have to set value numbers before insert, since insert is
2984 going to valueize the references in-place. */
2987 changed
|= set_ssa_val_to (vdef
, vdef
);
2990 /* Do not insert structure copies into the tables. */
2991 if (is_gimple_min_invariant (op
)
2992 || is_gimple_reg (op
))
2993 vn_reference_insert (lhs
, op
, vdef
, NULL
);
2995 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2996 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3000 /* We had a match, so value number the vdef to have the value
3001 number of the vuse it came from. */
3003 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3004 fprintf (dump_file
, "Store matched earlier value,"
3005 "value numbering store vdefs to matching vuses.\n");
3007 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3013 /* Visit and value number PHI, return true if the value number
3017 visit_phi (gimple phi
)
3019 bool changed
= false;
3021 tree sameval
= VN_TOP
;
3022 bool allsame
= true;
3025 /* TODO: We could check for this in init_sccvn, and replace this
3026 with a gcc_assert. */
3027 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3028 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3030 /* See if all non-TOP arguments have the same value. TOP is
3031 equivalent to everything, so we can ignore it. */
3032 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3034 tree def
= PHI_ARG_DEF (phi
, i
);
3036 if (TREE_CODE (def
) == SSA_NAME
)
3037 def
= SSA_VAL (def
);
3040 if (sameval
== VN_TOP
)
3046 if (!expressions_equal_p (def
, sameval
))
3054 /* If all value numbered to the same value, the phi node has that
3058 if (is_gimple_min_invariant (sameval
))
3060 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
3061 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3065 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3066 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3069 if (TREE_CODE (sameval
) == SSA_NAME
)
3070 return visit_copy (PHI_RESULT (phi
), sameval
);
3072 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3075 /* Otherwise, see if it is equivalent to a phi node in this block. */
3076 result
= vn_phi_lookup (phi
);
3079 if (TREE_CODE (result
) == SSA_NAME
)
3080 changed
= visit_copy (PHI_RESULT (phi
), result
);
3082 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3086 vn_phi_insert (phi
, PHI_RESULT (phi
));
3087 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3088 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3089 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3095 /* Return true if EXPR contains constants. */
3098 expr_has_constants (tree expr
)
3100 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3103 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3106 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3107 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3108 /* Constants inside reference ops are rarely interesting, but
3109 it can take a lot of looking to find them. */
3111 case tcc_declaration
:
3114 return is_gimple_min_invariant (expr
);
3119 /* Return true if STMT contains constants. */
3122 stmt_has_constants (gimple stmt
)
3126 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3129 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3131 case GIMPLE_TERNARY_RHS
:
3132 tem
= gimple_assign_rhs3 (stmt
);
3133 if (TREE_CODE (tem
) == SSA_NAME
)
3134 tem
= SSA_VAL (tem
);
3135 if (is_gimple_min_invariant (tem
))
3139 case GIMPLE_BINARY_RHS
:
3140 tem
= gimple_assign_rhs2 (stmt
);
3141 if (TREE_CODE (tem
) == SSA_NAME
)
3142 tem
= SSA_VAL (tem
);
3143 if (is_gimple_min_invariant (tem
))
3147 case GIMPLE_SINGLE_RHS
:
3148 /* Constants inside reference ops are rarely interesting, but
3149 it can take a lot of looking to find them. */
3150 case GIMPLE_UNARY_RHS
:
3151 tem
= gimple_assign_rhs1 (stmt
);
3152 if (TREE_CODE (tem
) == SSA_NAME
)
3153 tem
= SSA_VAL (tem
);
3154 return is_gimple_min_invariant (tem
);
3162 /* Replace SSA_NAMES in expr with their value numbers, and return the
3164 This is performed in place. */
3167 valueize_expr (tree expr
)
3169 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3172 TREE_OPERAND (expr
, 1) = vn_valueize (TREE_OPERAND (expr
, 1));
3175 TREE_OPERAND (expr
, 0) = vn_valueize (TREE_OPERAND (expr
, 0));
3182 /* Simplify the binary expression RHS, and return the result if
3186 simplify_binary_expression (gimple stmt
)
3188 tree result
= NULL_TREE
;
3189 tree op0
= gimple_assign_rhs1 (stmt
);
3190 tree op1
= gimple_assign_rhs2 (stmt
);
3191 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3193 /* This will not catch every single case we could combine, but will
3194 catch those with constants. The goal here is to simultaneously
3195 combine constants between expressions, but avoid infinite
3196 expansion of expressions during simplification. */
3197 if (TREE_CODE (op0
) == SSA_NAME
)
3199 if (VN_INFO (op0
)->has_constants
3200 || TREE_CODE_CLASS (code
) == tcc_comparison
3201 || code
== COMPLEX_EXPR
)
3202 op0
= valueize_expr (vn_get_expr_for (op0
));
3204 op0
= vn_valueize (op0
);
3207 if (TREE_CODE (op1
) == SSA_NAME
)
3209 if (VN_INFO (op1
)->has_constants
3210 || code
== COMPLEX_EXPR
)
3211 op1
= valueize_expr (vn_get_expr_for (op1
));
3213 op1
= vn_valueize (op1
);
3216 /* Pointer plus constant can be represented as invariant address.
3217 Do so to allow further propatation, see also tree forwprop. */
3218 if (code
== POINTER_PLUS_EXPR
3219 && host_integerp (op1
, 1)
3220 && TREE_CODE (op0
) == ADDR_EXPR
3221 && is_gimple_min_invariant (op0
))
3222 return build_invariant_address (TREE_TYPE (op0
),
3223 TREE_OPERAND (op0
, 0),
3224 TREE_INT_CST_LOW (op1
));
3226 /* Avoid folding if nothing changed. */
3227 if (op0
== gimple_assign_rhs1 (stmt
)
3228 && op1
== gimple_assign_rhs2 (stmt
))
3231 fold_defer_overflow_warnings ();
3233 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3235 STRIP_USELESS_TYPE_CONVERSION (result
);
3237 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3240 /* Make sure result is not a complex expression consisting
3241 of operators of operators (IE (a + b) + (a + c))
3242 Otherwise, we will end up with unbounded expressions if
3243 fold does anything at all. */
3244 if (result
&& valid_gimple_rhs_p (result
))
3250 /* Simplify the unary expression RHS, and return the result if
3254 simplify_unary_expression (gimple stmt
)
3256 tree result
= NULL_TREE
;
3257 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3258 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3260 /* We handle some tcc_reference codes here that are all
3261 GIMPLE_ASSIGN_SINGLE codes. */
3262 if (code
== REALPART_EXPR
3263 || code
== IMAGPART_EXPR
3264 || code
== VIEW_CONVERT_EXPR
3265 || code
== BIT_FIELD_REF
)
3266 op0
= TREE_OPERAND (op0
, 0);
3268 if (TREE_CODE (op0
) != SSA_NAME
)
3272 if (VN_INFO (op0
)->has_constants
)
3273 op0
= valueize_expr (vn_get_expr_for (op0
));
3274 else if (CONVERT_EXPR_CODE_P (code
)
3275 || code
== REALPART_EXPR
3276 || code
== IMAGPART_EXPR
3277 || code
== VIEW_CONVERT_EXPR
3278 || code
== BIT_FIELD_REF
)
3280 /* We want to do tree-combining on conversion-like expressions.
3281 Make sure we feed only SSA_NAMEs or constants to fold though. */
3282 tree tem
= valueize_expr (vn_get_expr_for (op0
));
3283 if (UNARY_CLASS_P (tem
)
3284 || BINARY_CLASS_P (tem
)
3285 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3286 || TREE_CODE (tem
) == SSA_NAME
3287 || TREE_CODE (tem
) == CONSTRUCTOR
3288 || is_gimple_min_invariant (tem
))
3292 /* Avoid folding if nothing changed, but remember the expression. */
3293 if (op0
== orig_op0
)
3296 if (code
== BIT_FIELD_REF
)
3298 tree rhs
= gimple_assign_rhs1 (stmt
);
3299 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3300 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3303 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3306 STRIP_USELESS_TYPE_CONVERSION (result
);
3307 if (valid_gimple_rhs_p (result
))
3314 /* Try to simplify RHS using equivalences and constant folding. */
3317 try_to_simplify (gimple stmt
)
3319 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3322 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3323 in this case, there is no point in doing extra work. */
3324 if (code
== SSA_NAME
)
3327 /* First try constant folding based on our current lattice. */
3328 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3330 && (TREE_CODE (tem
) == SSA_NAME
3331 || is_gimple_min_invariant (tem
)))
3334 /* If that didn't work try combining multiple statements. */
3335 switch (TREE_CODE_CLASS (code
))
3338 /* Fallthrough for some unary codes that can operate on registers. */
3339 if (!(code
== REALPART_EXPR
3340 || code
== IMAGPART_EXPR
3341 || code
== VIEW_CONVERT_EXPR
3342 || code
== BIT_FIELD_REF
))
3344 /* We could do a little more with unary ops, if they expand
3345 into binary ops, but it's debatable whether it is worth it. */
3347 return simplify_unary_expression (stmt
);
3349 case tcc_comparison
:
3351 return simplify_binary_expression (stmt
);
3360 /* Visit and value number USE, return true if the value number
3364 visit_use (tree use
)
3366 bool changed
= false;
3367 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3369 mark_use_processed (use
);
3371 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3372 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3373 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3375 fprintf (dump_file
, "Value numbering ");
3376 print_generic_expr (dump_file
, use
, 0);
3377 fprintf (dump_file
, " stmt = ");
3378 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3381 /* Handle uninitialized uses. */
3382 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3383 changed
= set_ssa_val_to (use
, use
);
3386 if (gimple_code (stmt
) == GIMPLE_PHI
)
3387 changed
= visit_phi (stmt
);
3388 else if (gimple_has_volatile_ops (stmt
))
3389 changed
= defs_to_varying (stmt
);
3390 else if (is_gimple_assign (stmt
))
3392 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3393 tree lhs
= gimple_assign_lhs (stmt
);
3394 tree rhs1
= gimple_assign_rhs1 (stmt
);
3397 /* Shortcut for copies. Simplifying copies is pointless,
3398 since we copy the expression and value they represent. */
3399 if (code
== SSA_NAME
3400 && TREE_CODE (lhs
) == SSA_NAME
)
3402 changed
= visit_copy (lhs
, rhs1
);
3405 simplified
= try_to_simplify (stmt
);
3408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3410 fprintf (dump_file
, "RHS ");
3411 print_gimple_expr (dump_file
, stmt
, 0, 0);
3412 fprintf (dump_file
, " simplified to ");
3413 print_generic_expr (dump_file
, simplified
, 0);
3414 if (TREE_CODE (lhs
) == SSA_NAME
)
3415 fprintf (dump_file
, " has constants %d\n",
3416 expr_has_constants (simplified
));
3418 fprintf (dump_file
, "\n");
3421 /* Setting value numbers to constants will occasionally
3422 screw up phi congruence because constants are not
3423 uniquely associated with a single ssa name that can be
3426 && is_gimple_min_invariant (simplified
)
3427 && TREE_CODE (lhs
) == SSA_NAME
)
3429 VN_INFO (lhs
)->expr
= simplified
;
3430 VN_INFO (lhs
)->has_constants
= true;
3431 changed
= set_ssa_val_to (lhs
, simplified
);
3435 && TREE_CODE (simplified
) == SSA_NAME
3436 && TREE_CODE (lhs
) == SSA_NAME
)
3438 changed
= visit_copy (lhs
, simplified
);
3441 else if (simplified
)
3443 if (TREE_CODE (lhs
) == SSA_NAME
)
3445 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3446 /* We have to unshare the expression or else
3447 valuizing may change the IL stream. */
3448 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3451 else if (stmt_has_constants (stmt
)
3452 && TREE_CODE (lhs
) == SSA_NAME
)
3453 VN_INFO (lhs
)->has_constants
= true;
3454 else if (TREE_CODE (lhs
) == SSA_NAME
)
3456 /* We reset expr and constantness here because we may
3457 have been value numbering optimistically, and
3458 iterating. They may become non-constant in this case,
3459 even if they were optimistically constant. */
3461 VN_INFO (lhs
)->has_constants
= false;
3462 VN_INFO (lhs
)->expr
= NULL_TREE
;
3465 if ((TREE_CODE (lhs
) == SSA_NAME
3466 /* We can substitute SSA_NAMEs that are live over
3467 abnormal edges with their constant value. */
3468 && !(gimple_assign_copy_p (stmt
)
3469 && is_gimple_min_invariant (rhs1
))
3471 && is_gimple_min_invariant (simplified
))
3472 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3473 /* Stores or copies from SSA_NAMEs that are live over
3474 abnormal edges are a problem. */
3475 || (code
== SSA_NAME
3476 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3477 changed
= defs_to_varying (stmt
);
3478 else if (REFERENCE_CLASS_P (lhs
)
3480 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3481 else if (TREE_CODE (lhs
) == SSA_NAME
)
3483 if ((gimple_assign_copy_p (stmt
)
3484 && is_gimple_min_invariant (rhs1
))
3486 && is_gimple_min_invariant (simplified
)))
3488 VN_INFO (lhs
)->has_constants
= true;
3490 changed
= set_ssa_val_to (lhs
, simplified
);
3492 changed
= set_ssa_val_to (lhs
, rhs1
);
3496 /* First try to lookup the simplified expression. */
3499 enum gimple_rhs_class rhs_class
;
3502 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3503 if ((rhs_class
== GIMPLE_UNARY_RHS
3504 || rhs_class
== GIMPLE_BINARY_RHS
3505 || rhs_class
== GIMPLE_TERNARY_RHS
)
3506 && valid_gimple_rhs_p (simplified
))
3508 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3511 changed
= set_ssa_val_to (lhs
, result
);
3517 /* Otherwise visit the original statement. */
3518 switch (vn_get_stmt_kind (stmt
))
3521 changed
= visit_nary_op (lhs
, stmt
);
3524 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3527 changed
= defs_to_varying (stmt
);
3533 changed
= defs_to_varying (stmt
);
3535 else if (is_gimple_call (stmt
))
3537 tree lhs
= gimple_call_lhs (stmt
);
3539 /* ??? We could try to simplify calls. */
3541 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3543 if (stmt_has_constants (stmt
))
3544 VN_INFO (lhs
)->has_constants
= true;
3547 /* We reset expr and constantness here because we may
3548 have been value numbering optimistically, and
3549 iterating. They may become non-constant in this case,
3550 even if they were optimistically constant. */
3551 VN_INFO (lhs
)->has_constants
= false;
3552 VN_INFO (lhs
)->expr
= NULL_TREE
;
3555 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3557 changed
= defs_to_varying (stmt
);
3562 if (!gimple_call_internal_p (stmt
)
3563 && (/* Calls to the same function with the same vuse
3564 and the same operands do not necessarily return the same
3565 value, unless they're pure or const. */
3566 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3567 /* If calls have a vdef, subsequent calls won't have
3568 the same incoming vuse. So, if 2 calls with vdef have the
3569 same vuse, we know they're not subsequent.
3570 We can value number 2 calls to the same function with the
3571 same vuse and the same operands which are not subsequent
3572 the same, because there is no code in the program that can
3573 compare the 2 values... */
3574 || (gimple_vdef (stmt
)
3575 /* ... unless the call returns a pointer which does
3576 not alias with anything else. In which case the
3577 information that the values are distinct are encoded
3579 && !(gimple_call_return_flags (stmt
) & ERF_NOALIAS
))))
3580 changed
= visit_reference_op_call (lhs
, stmt
);
3582 changed
= defs_to_varying (stmt
);
3585 changed
= defs_to_varying (stmt
);
3591 /* Compare two operands by reverse postorder index */
3594 compare_ops (const void *pa
, const void *pb
)
3596 const tree opa
= *((const tree
*)pa
);
3597 const tree opb
= *((const tree
*)pb
);
3598 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3599 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3603 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3604 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3605 else if (gimple_nop_p (opstmta
))
3607 else if (gimple_nop_p (opstmtb
))
3610 bba
= gimple_bb (opstmta
);
3611 bbb
= gimple_bb (opstmtb
);
3614 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3622 if (gimple_code (opstmta
) == GIMPLE_PHI
3623 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3624 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3625 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3627 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3629 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3630 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3632 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3634 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3637 /* Sort an array containing members of a strongly connected component
3638 SCC so that the members are ordered by RPO number.
3639 This means that when the sort is complete, iterating through the
3640 array will give you the members in RPO order. */
3643 sort_scc (vec
<tree
> scc
)
3645 scc
.qsort (compare_ops
);
3648 /* Insert the no longer used nary ONARY to the hash INFO. */
3651 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3653 size_t size
= sizeof_vn_nary_op (onary
->length
);
3654 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3655 &info
->nary_obstack
);
3656 memcpy (nary
, onary
, size
);
3657 vn_nary_op_insert_into (nary
, info
->nary
, false);
3660 /* Insert the no longer used phi OPHI to the hash INFO. */
3663 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3665 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3667 memcpy (phi
, ophi
, sizeof (*phi
));
3668 ophi
->phiargs
.create (0);
3669 slot
= info
->phis
.find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3670 gcc_assert (!*slot
);
3674 /* Insert the no longer used reference OREF to the hash INFO. */
3677 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3680 vn_reference_s
**slot
;
3681 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3682 memcpy (ref
, oref
, sizeof (*ref
));
3683 oref
->operands
.create (0);
3684 slot
= info
->references
.find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3686 free_reference (*slot
);
3690 /* Process a strongly connected component in the SSA graph. */
3693 process_scc (vec
<tree
> scc
)
3697 unsigned int iterations
= 0;
3698 bool changed
= true;
3699 vn_nary_op_iterator_type hin
;
3700 vn_phi_iterator_type hip
;
3701 vn_reference_iterator_type hir
;
3706 /* If the SCC has a single member, just visit it. */
3707 if (scc
.length () == 1)
3710 if (VN_INFO (use
)->use_processed
)
3712 /* We need to make sure it doesn't form a cycle itself, which can
3713 happen for self-referential PHI nodes. In that case we would
3714 end up inserting an expression with VN_TOP operands into the
3715 valid table which makes us derive bogus equivalences later.
3716 The cheapest way to check this is to assume it for all PHI nodes. */
3717 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3718 /* Fallthru to iteration. */ ;
3726 /* Iterate over the SCC with the optimistic table until it stops
3728 current_info
= optimistic_info
;
3733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3734 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3735 /* As we are value-numbering optimistically we have to
3736 clear the expression tables and the simplified expressions
3737 in each iteration until we converge. */
3738 optimistic_info
->nary
.empty ();
3739 optimistic_info
->phis
.empty ();
3740 optimistic_info
->references
.empty ();
3741 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3742 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3743 empty_alloc_pool (optimistic_info
->phis_pool
);
3744 empty_alloc_pool (optimistic_info
->references_pool
);
3745 FOR_EACH_VEC_ELT (scc
, i
, var
)
3746 VN_INFO (var
)->expr
= NULL_TREE
;
3747 FOR_EACH_VEC_ELT (scc
, i
, var
)
3748 changed
|= visit_use (var
);
3751 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3753 /* Finally, copy the contents of the no longer used optimistic
3754 table to the valid table. */
3755 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3756 copy_nary (nary
, valid_info
);
3757 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3758 copy_phi (phi
, valid_info
);
3759 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->references
,
3760 ref
, vn_reference_t
, hir
)
3761 copy_reference (ref
, valid_info
);
3763 current_info
= valid_info
;
3767 /* Pop the components of the found SCC for NAME off the SCC stack
3768 and process them. Returns true if all went well, false if
3769 we run into resource limits. */
3772 extract_and_process_scc_for_name (tree name
)
3774 vec
<tree
> scc
= vNULL
;
3777 /* Found an SCC, pop the components off the SCC stack and
3781 x
= sccstack
.pop ();
3783 VN_INFO (x
)->on_sccstack
= false;
3785 } while (x
!= name
);
3787 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3789 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3792 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3793 "SCC size %u exceeding %u\n", scc
.length (),
3794 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3800 if (scc
.length () > 1)
3803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3804 print_scc (dump_file
, scc
);
3813 /* Depth first search on NAME to discover and process SCC's in the SSA
3815 Execution of this algorithm relies on the fact that the SCC's are
3816 popped off the stack in topological order.
3817 Returns true if successful, false if we stopped processing SCC's due
3818 to resource constraints. */
3823 vec
<ssa_op_iter
> itervec
= vNULL
;
3824 vec
<tree
> namevec
= vNULL
;
3825 use_operand_p usep
= NULL
;
3832 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3833 VN_INFO (name
)->visited
= true;
3834 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3836 sccstack
.safe_push (name
);
3837 VN_INFO (name
)->on_sccstack
= true;
3838 defstmt
= SSA_NAME_DEF_STMT (name
);
3840 /* Recursively DFS on our operands, looking for SCC's. */
3841 if (!gimple_nop_p (defstmt
))
3843 /* Push a new iterator. */
3844 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3845 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3847 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3850 clear_and_done_ssa_iter (&iter
);
3854 /* If we are done processing uses of a name, go up the stack
3855 of iterators and process SCCs as we found them. */
3856 if (op_iter_done (&iter
))
3858 /* See if we found an SCC. */
3859 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3860 if (!extract_and_process_scc_for_name (name
))
3867 /* Check if we are done. */
3868 if (namevec
.is_empty ())
3875 /* Restore the last use walker and continue walking there. */
3877 name
= namevec
.pop ();
3878 memcpy (&iter
, &itervec
.last (),
3879 sizeof (ssa_op_iter
));
3881 goto continue_walking
;
3884 use
= USE_FROM_PTR (usep
);
3886 /* Since we handle phi nodes, we will sometimes get
3887 invariants in the use expression. */
3888 if (TREE_CODE (use
) == SSA_NAME
)
3890 if (! (VN_INFO (use
)->visited
))
3892 /* Recurse by pushing the current use walking state on
3893 the stack and starting over. */
3894 itervec
.safe_push (iter
);
3895 namevec
.safe_push (name
);
3900 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3901 VN_INFO (use
)->low
);
3903 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3904 && VN_INFO (use
)->on_sccstack
)
3906 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3907 VN_INFO (name
)->low
);
3911 usep
= op_iter_next_use (&iter
);
3915 /* Allocate a value number table. */
3918 allocate_vn_table (vn_tables_t table
)
3920 table
->phis
.create (23);
3921 table
->nary
.create (23);
3922 table
->references
.create (23);
3924 gcc_obstack_init (&table
->nary_obstack
);
3925 table
->phis_pool
= create_alloc_pool ("VN phis",
3926 sizeof (struct vn_phi_s
),
3928 table
->references_pool
= create_alloc_pool ("VN references",
3929 sizeof (struct vn_reference_s
),
3933 /* Free a value number table. */
3936 free_vn_table (vn_tables_t table
)
3938 table
->phis
.dispose ();
3939 table
->nary
.dispose ();
3940 table
->references
.dispose ();
3941 obstack_free (&table
->nary_obstack
, NULL
);
3942 free_alloc_pool (table
->phis_pool
);
3943 free_alloc_pool (table
->references_pool
);
3951 int *rpo_numbers_temp
;
3953 calculate_dominance_info (CDI_DOMINATORS
);
3954 sccstack
.create (0);
3955 constant_to_value_id
.create (23);
3957 constant_value_ids
= BITMAP_ALLOC (NULL
);
3962 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
3963 /* VEC_alloc doesn't actually grow it to the right size, it just
3964 preallocates the space to do so. */
3965 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
3966 gcc_obstack_init (&vn_ssa_aux_obstack
);
3968 shared_lookup_phiargs
.create (0);
3969 shared_lookup_references
.create (0);
3970 rpo_numbers
= XNEWVEC (int, last_basic_block
);
3971 rpo_numbers_temp
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3972 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
3974 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3975 the i'th block in RPO order is bb. We want to map bb's to RPO
3976 numbers, so we need to rearrange this array. */
3977 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
3978 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
3980 XDELETE (rpo_numbers_temp
);
3982 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
3984 /* Create the VN_INFO structures, and initialize value numbers to
3986 for (i
= 0; i
< num_ssa_names
; i
++)
3988 tree name
= ssa_name (i
);
3991 VN_INFO_GET (name
)->valnum
= VN_TOP
;
3992 VN_INFO (name
)->expr
= NULL_TREE
;
3993 VN_INFO (name
)->value_id
= 0;
3997 renumber_gimple_stmt_uids ();
3999 /* Create the valid and optimistic value numbering tables. */
4000 valid_info
= XCNEW (struct vn_tables_s
);
4001 allocate_vn_table (valid_info
);
4002 optimistic_info
= XCNEW (struct vn_tables_s
);
4003 allocate_vn_table (optimistic_info
);
4011 constant_to_value_id
.dispose ();
4012 BITMAP_FREE (constant_value_ids
);
4013 shared_lookup_phiargs
.release ();
4014 shared_lookup_references
.release ();
4015 XDELETEVEC (rpo_numbers
);
4017 for (i
= 0; i
< num_ssa_names
; i
++)
4019 tree name
= ssa_name (i
);
4021 && VN_INFO (name
)->needs_insertion
)
4022 release_ssa_name (name
);
4024 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4025 vn_ssa_aux_table
.release ();
4027 sccstack
.release ();
4028 free_vn_table (valid_info
);
4029 XDELETE (valid_info
);
4030 free_vn_table (optimistic_info
);
4031 XDELETE (optimistic_info
);
4034 /* Set *ID according to RESULT. */
4037 set_value_id_for_result (tree result
, unsigned int *id
)
4039 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4040 *id
= VN_INFO (result
)->value_id
;
4041 else if (result
&& is_gimple_min_invariant (result
))
4042 *id
= get_or_alloc_constant_value_id (result
);
4044 *id
= get_next_value_id ();
4047 /* Set the value ids in the valid hash tables. */
4050 set_hashtable_value_ids (void)
4052 vn_nary_op_iterator_type hin
;
4053 vn_phi_iterator_type hip
;
4054 vn_reference_iterator_type hir
;
4059 /* Now set the value ids of the things we had put in the hash
4062 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4063 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4065 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->phis
, vp
, vn_phi_t
, hip
)
4066 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4068 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->references
, vr
, vn_reference_t
, hir
)
4069 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4072 /* Do SCCVN. Returns true if it finished, false if we bailed out
4073 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4074 how we use the alias oracle walking during the VN process. */
4077 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4082 default_vn_walk_kind
= default_vn_walk_kind_
;
4085 current_info
= valid_info
;
4087 for (param
= DECL_ARGUMENTS (current_function_decl
);
4089 param
= DECL_CHAIN (param
))
4091 tree def
= ssa_default_def (cfun
, param
);
4093 VN_INFO (def
)->valnum
= def
;
4096 for (i
= 1; i
< num_ssa_names
; ++i
)
4098 tree name
= ssa_name (i
);
4100 && VN_INFO (name
)->visited
== false
4101 && !has_zero_uses (name
))
4109 /* Initialize the value ids. */
4111 for (i
= 1; i
< num_ssa_names
; ++i
)
4113 tree name
= ssa_name (i
);
4117 info
= VN_INFO (name
);
4118 if (info
->valnum
== name
4119 || info
->valnum
== VN_TOP
)
4120 info
->value_id
= get_next_value_id ();
4121 else if (is_gimple_min_invariant (info
->valnum
))
4122 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4126 for (i
= 1; i
< num_ssa_names
; ++i
)
4128 tree name
= ssa_name (i
);
4132 info
= VN_INFO (name
);
4133 if (TREE_CODE (info
->valnum
) == SSA_NAME
4134 && info
->valnum
!= name
4135 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4136 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4139 set_hashtable_value_ids ();
4141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4143 fprintf (dump_file
, "Value numbers:\n");
4144 for (i
= 0; i
< num_ssa_names
; i
++)
4146 tree name
= ssa_name (i
);
4148 && VN_INFO (name
)->visited
4149 && SSA_VAL (name
) != name
)
4151 print_generic_expr (dump_file
, name
, 0);
4152 fprintf (dump_file
, " = ");
4153 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4154 fprintf (dump_file
, "\n");
4162 /* Return the maximum value id we have ever seen. */
4165 get_max_value_id (void)
4167 return next_value_id
;
4170 /* Return the next unique value id. */
4173 get_next_value_id (void)
4175 return next_value_id
++;
4179 /* Compare two expressions E1 and E2 and return true if they are equal. */
4182 expressions_equal_p (tree e1
, tree e2
)
4184 /* The obvious case. */
4188 /* If only one of them is null, they cannot be equal. */
4192 /* Now perform the actual comparison. */
4193 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4194 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4201 /* Return true if the nary operation NARY may trap. This is a copy
4202 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4205 vn_nary_may_trap (vn_nary_op_t nary
)
4208 tree rhs2
= NULL_TREE
;
4209 bool honor_nans
= false;
4210 bool honor_snans
= false;
4211 bool fp_operation
= false;
4212 bool honor_trapv
= false;
4216 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4217 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4218 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4221 fp_operation
= FLOAT_TYPE_P (type
);
4224 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4225 honor_snans
= flag_signaling_nans
!= 0;
4227 else if (INTEGRAL_TYPE_P (type
)
4228 && TYPE_OVERFLOW_TRAPS (type
))
4231 if (nary
->length
>= 2)
4233 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4235 honor_nans
, honor_snans
, rhs2
,
4241 for (i
= 0; i
< nary
->length
; ++i
)
4242 if (tree_could_trap_p (nary
->op
[i
]))