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"
29 #include "tree-flow.h"
32 #include "hash-table.h"
33 #include "alloc-pool.h"
38 #include "tree-ssa-propagate.h"
39 #include "tree-ssa-sccvn.h"
40 #include "gimple-fold.h"
42 /* This algorithm is based on the SCC algorithm presented by Keith
43 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
44 (http://citeseer.ist.psu.edu/41805.html). In
45 straight line code, it is equivalent to a regular hash based value
46 numbering that is performed in reverse postorder.
48 For code with cycles, there are two alternatives, both of which
49 require keeping the hashtables separate from the actual list of
50 value numbers for SSA names.
52 1. Iterate value numbering in an RPO walk of the blocks, removing
53 all the entries from the hashtable after each iteration (but
54 keeping the SSA name->value number mapping between iterations).
55 Iterate until it does not change.
57 2. Perform value numbering as part of an SCC walk on the SSA graph,
58 iterating only the cycles in the SSA graph until they do not change
59 (using a separate, optimistic hashtable for value numbering the SCC
62 The second is not just faster in practice (because most SSA graph
63 cycles do not involve all the variables in the graph), it also has
66 One of these nice properties is that when we pop an SCC off the
67 stack, we are guaranteed to have processed all the operands coming from
68 *outside of that SCC*, so we do not need to do anything special to
69 ensure they have value numbers.
71 Another nice property is that the SCC walk is done as part of a DFS
72 of the SSA graph, which makes it easy to perform combining and
73 simplifying operations at the same time.
75 The code below is deliberately written in a way that makes it easy
76 to separate the SCC walk from the other work it does.
78 In order to propagate constants through the code, we track which
79 expressions contain constants, and use those while folding. In
80 theory, we could also track expressions whose value numbers are
81 replaced, in case we end up folding based on expression
84 In order to value number memory, we assign value numbers to vuses.
85 This enables us to note that, for example, stores to the same
86 address of the same value from the same starting memory states are
90 1. We can iterate only the changing portions of the SCC's, but
91 I have not seen an SCC big enough for this to be a win.
92 2. If you differentiate between phi nodes for loops and phi nodes
93 for if-then-else, you can properly consider phi nodes in different
94 blocks for equivalence.
95 3. We could value number vuses in more cases, particularly, whole
100 /* vn_nary_op hashtable helpers. */
102 struct vn_nary_op_hasher
: typed_noop_remove
<vn_nary_op_s
>
104 typedef vn_nary_op_s value_type
;
105 typedef vn_nary_op_s compare_type
;
106 static inline hashval_t
hash (const value_type
*);
107 static inline bool equal (const value_type
*, const compare_type
*);
110 /* Return the computed hashcode for nary operation P1. */
113 vn_nary_op_hasher::hash (const value_type
*vno1
)
115 return vno1
->hashcode
;
118 /* Compare nary operations P1 and P2 and return true if they are
122 vn_nary_op_hasher::equal (const value_type
*vno1
, const compare_type
*vno2
)
124 return vn_nary_op_eq (vno1
, vno2
);
127 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
128 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
131 /* vn_phi hashtable helpers. */
134 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
138 typedef vn_phi_s value_type
;
139 typedef vn_phi_s compare_type
;
140 static inline hashval_t
hash (const value_type
*);
141 static inline bool equal (const value_type
*, const compare_type
*);
142 static inline void remove (value_type
*);
145 /* Return the computed hashcode for phi operation P1. */
148 vn_phi_hasher::hash (const value_type
*vp1
)
150 return vp1
->hashcode
;
153 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
156 vn_phi_hasher::equal (const value_type
*vp1
, const compare_type
*vp2
)
158 return vn_phi_eq (vp1
, vp2
);
161 /* Free a phi operation structure VP. */
164 vn_phi_hasher::remove (value_type
*phi
)
166 phi
->phiargs
.release ();
169 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
170 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
173 /* Compare two reference operands P1 and P2 for equality. Return true if
174 they are equal, and false otherwise. */
177 vn_reference_op_eq (const void *p1
, const void *p2
)
179 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
180 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
182 return (vro1
->opcode
== vro2
->opcode
183 /* We do not care for differences in type qualification. */
184 && (vro1
->type
== vro2
->type
185 || (vro1
->type
&& vro2
->type
186 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
187 TYPE_MAIN_VARIANT (vro2
->type
))))
188 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
189 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
190 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
193 /* Free a reference operation structure VP. */
196 free_reference (vn_reference_s
*vr
)
198 vr
->operands
.release ();
202 /* vn_reference hashtable helpers. */
204 struct vn_reference_hasher
206 typedef vn_reference_s value_type
;
207 typedef vn_reference_s compare_type
;
208 static inline hashval_t
hash (const value_type
*);
209 static inline bool equal (const value_type
*, const compare_type
*);
210 static inline void remove (value_type
*);
213 /* Return the hashcode for a given reference operation P1. */
216 vn_reference_hasher::hash (const value_type
*vr1
)
218 return vr1
->hashcode
;
222 vn_reference_hasher::equal (const value_type
*v
, const compare_type
*c
)
224 return vn_reference_eq (v
, c
);
228 vn_reference_hasher::remove (value_type
*v
)
233 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
234 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
237 /* The set of hashtables and alloc_pool's for their items. */
239 typedef struct vn_tables_s
241 vn_nary_op_table_type nary
;
242 vn_phi_table_type phis
;
243 vn_reference_table_type references
;
244 struct obstack nary_obstack
;
245 alloc_pool phis_pool
;
246 alloc_pool references_pool
;
250 /* vn_constant hashtable helpers. */
252 struct vn_constant_hasher
: typed_free_remove
<vn_constant_s
>
254 typedef vn_constant_s value_type
;
255 typedef vn_constant_s compare_type
;
256 static inline hashval_t
hash (const value_type
*);
257 static inline bool equal (const value_type
*, const compare_type
*);
260 /* Hash table hash function for vn_constant_t. */
263 vn_constant_hasher::hash (const value_type
*vc1
)
265 return vc1
->hashcode
;
268 /* Hash table equality function for vn_constant_t. */
271 vn_constant_hasher::equal (const value_type
*vc1
, const compare_type
*vc2
)
273 if (vc1
->hashcode
!= vc2
->hashcode
)
276 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
279 static hash_table
<vn_constant_hasher
> constant_to_value_id
;
280 static bitmap constant_value_ids
;
283 /* Valid hashtables storing information we have proven to be
286 static vn_tables_t valid_info
;
288 /* Optimistic hashtables storing information we are making assumptions about
289 during iterations. */
291 static vn_tables_t optimistic_info
;
293 /* Pointer to the set of hashtables that is currently being used.
294 Should always point to either the optimistic_info, or the
297 static vn_tables_t current_info
;
300 /* Reverse post order index for each basic block. */
302 static int *rpo_numbers
;
304 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
306 /* This represents the top of the VN lattice, which is the universal
311 /* Unique counter for our value ids. */
313 static unsigned int next_value_id
;
315 /* Next DFS number and the stack for strongly connected component
318 static unsigned int next_dfs_num
;
319 static vec
<tree
> sccstack
;
323 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
324 are allocated on an obstack for locality reasons, and to free them
325 without looping over the vec. */
327 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
328 static struct obstack vn_ssa_aux_obstack
;
330 /* Return the value numbering information for a given SSA name. */
335 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
336 gcc_checking_assert (res
);
340 /* Set the value numbering info for a given SSA name to a given
344 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
346 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
349 /* Initialize the value numbering info for a given SSA name.
350 This should be called just once for every SSA name. */
353 VN_INFO_GET (tree name
)
355 vn_ssa_aux_t newinfo
;
357 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
358 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
359 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
360 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
361 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
366 /* Get the representative expression for the SSA_NAME NAME. Returns
367 the representative SSA_NAME if there is no expression associated with it. */
370 vn_get_expr_for (tree name
)
372 vn_ssa_aux_t vn
= VN_INFO (name
);
374 tree expr
= NULL_TREE
;
377 if (vn
->valnum
== VN_TOP
)
380 /* If the value-number is a constant it is the representative
382 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
385 /* Get to the information of the value of this SSA_NAME. */
386 vn
= VN_INFO (vn
->valnum
);
388 /* If the value-number is a constant it is the representative
390 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
393 /* Else if we have an expression, return it. */
394 if (vn
->expr
!= NULL_TREE
)
397 /* Otherwise use the defining statement to build the expression. */
398 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
400 /* If the value number is not an assignment use it directly. */
401 if (!is_gimple_assign (def_stmt
))
404 /* FIXME tuples. This is incomplete and likely will miss some
406 code
= gimple_assign_rhs_code (def_stmt
);
407 switch (TREE_CODE_CLASS (code
))
410 if ((code
== REALPART_EXPR
411 || code
== IMAGPART_EXPR
412 || code
== VIEW_CONVERT_EXPR
)
413 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
415 expr
= fold_build1 (code
,
416 gimple_expr_type (def_stmt
),
417 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
421 expr
= fold_build1 (code
,
422 gimple_expr_type (def_stmt
),
423 gimple_assign_rhs1 (def_stmt
));
427 expr
= fold_build2 (code
,
428 gimple_expr_type (def_stmt
),
429 gimple_assign_rhs1 (def_stmt
),
430 gimple_assign_rhs2 (def_stmt
));
433 case tcc_exceptional
:
434 if (code
== CONSTRUCTOR
436 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
437 expr
= gimple_assign_rhs1 (def_stmt
);
442 if (expr
== NULL_TREE
)
445 /* Cache the expression. */
451 /* Return the vn_kind the expression computed by the stmt should be
455 vn_get_stmt_kind (gimple stmt
)
457 switch (gimple_code (stmt
))
465 enum tree_code code
= gimple_assign_rhs_code (stmt
);
466 tree rhs1
= gimple_assign_rhs1 (stmt
);
467 switch (get_gimple_rhs_class (code
))
469 case GIMPLE_UNARY_RHS
:
470 case GIMPLE_BINARY_RHS
:
471 case GIMPLE_TERNARY_RHS
:
473 case GIMPLE_SINGLE_RHS
:
474 switch (TREE_CODE_CLASS (code
))
477 /* VOP-less references can go through unary case. */
478 if ((code
== REALPART_EXPR
479 || code
== IMAGPART_EXPR
480 || code
== VIEW_CONVERT_EXPR
481 || code
== BIT_FIELD_REF
)
482 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
486 case tcc_declaration
:
493 if (code
== ADDR_EXPR
)
494 return (is_gimple_min_invariant (rhs1
)
495 ? VN_CONSTANT
: VN_REFERENCE
);
496 else if (code
== CONSTRUCTOR
)
509 /* Lookup a value id for CONSTANT and return it. If it does not
513 get_constant_value_id (tree constant
)
515 vn_constant_s
**slot
;
516 struct vn_constant_s vc
;
518 vc
.hashcode
= vn_hash_constant_with_type (constant
);
519 vc
.constant
= constant
;
520 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, NO_INSERT
);
522 return (*slot
)->value_id
;
526 /* Lookup a value id for CONSTANT, and if it does not exist, create a
527 new one and return it. If it does exist, return it. */
530 get_or_alloc_constant_value_id (tree constant
)
532 vn_constant_s
**slot
;
533 struct vn_constant_s vc
;
536 vc
.hashcode
= vn_hash_constant_with_type (constant
);
537 vc
.constant
= constant
;
538 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, INSERT
);
540 return (*slot
)->value_id
;
542 vcp
= XNEW (struct vn_constant_s
);
543 vcp
->hashcode
= vc
.hashcode
;
544 vcp
->constant
= constant
;
545 vcp
->value_id
= get_next_value_id ();
547 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
548 return vcp
->value_id
;
551 /* Return true if V is a value id for a constant. */
554 value_id_constant_p (unsigned int v
)
556 return bitmap_bit_p (constant_value_ids
, v
);
559 /* Compute the hash for a reference operand VRO1. */
562 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
564 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
566 result
= iterative_hash_expr (vro1
->op0
, result
);
568 result
= iterative_hash_expr (vro1
->op1
, result
);
570 result
= iterative_hash_expr (vro1
->op2
, result
);
574 /* Compute a hash for the reference operation VR1 and return it. */
577 vn_reference_compute_hash (const vn_reference_t vr1
)
579 hashval_t result
= 0;
581 vn_reference_op_t vro
;
582 HOST_WIDE_INT off
= -1;
585 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
587 if (vro
->opcode
== MEM_REF
)
589 else if (vro
->opcode
!= ADDR_EXPR
)
601 result
= iterative_hash_hashval_t (off
, result
);
604 && vro
->opcode
== ADDR_EXPR
)
608 tree op
= TREE_OPERAND (vro
->op0
, 0);
609 result
= iterative_hash_hashval_t (TREE_CODE (op
), result
);
610 result
= iterative_hash_expr (op
, result
);
614 result
= vn_reference_op_compute_hash (vro
, result
);
618 result
+= SSA_NAME_VERSION (vr1
->vuse
);
623 /* Return true if reference operations VR1 and VR2 are equivalent. This
624 means they have the same set of operands and vuses. */
627 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
631 if (vr1
->hashcode
!= vr2
->hashcode
)
634 /* Early out if this is not a hash collision. */
635 if (vr1
->hashcode
!= vr2
->hashcode
)
638 /* The VOP needs to be the same. */
639 if (vr1
->vuse
!= vr2
->vuse
)
642 /* If the operands are the same we are done. */
643 if (vr1
->operands
== vr2
->operands
)
646 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
649 if (INTEGRAL_TYPE_P (vr1
->type
)
650 && INTEGRAL_TYPE_P (vr2
->type
))
652 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
655 else if (INTEGRAL_TYPE_P (vr1
->type
)
656 && (TYPE_PRECISION (vr1
->type
)
657 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
659 else if (INTEGRAL_TYPE_P (vr2
->type
)
660 && (TYPE_PRECISION (vr2
->type
)
661 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
668 HOST_WIDE_INT off1
= 0, off2
= 0;
669 vn_reference_op_t vro1
, vro2
;
670 vn_reference_op_s tem1
, tem2
;
671 bool deref1
= false, deref2
= false;
672 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
674 if (vro1
->opcode
== MEM_REF
)
680 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
682 if (vro2
->opcode
== MEM_REF
)
690 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
692 memset (&tem1
, 0, sizeof (tem1
));
693 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
694 tem1
.type
= TREE_TYPE (tem1
.op0
);
695 tem1
.opcode
= TREE_CODE (tem1
.op0
);
699 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
701 memset (&tem2
, 0, sizeof (tem2
));
702 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
703 tem2
.type
= TREE_TYPE (tem2
.op0
);
704 tem2
.opcode
= TREE_CODE (tem2
.op0
);
708 if (deref1
!= deref2
)
710 if (!vn_reference_op_eq (vro1
, vro2
))
715 while (vr1
->operands
.length () != i
716 || vr2
->operands
.length () != j
);
721 /* Copy the operations present in load/store REF into RESULT, a vector of
722 vn_reference_op_s's. */
725 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
727 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
729 vn_reference_op_s temp
;
733 memset (&temp
, 0, sizeof (temp
));
734 temp
.type
= TREE_TYPE (ref
);
735 temp
.opcode
= TREE_CODE (ref
);
736 temp
.op0
= TMR_INDEX (ref
);
737 temp
.op1
= TMR_STEP (ref
);
738 temp
.op2
= TMR_OFFSET (ref
);
740 result
->quick_push (temp
);
742 memset (&temp
, 0, sizeof (temp
));
743 temp
.type
= NULL_TREE
;
744 temp
.opcode
= ERROR_MARK
;
745 temp
.op0
= TMR_INDEX2 (ref
);
747 result
->quick_push (temp
);
749 memset (&temp
, 0, sizeof (temp
));
750 temp
.type
= NULL_TREE
;
751 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
752 temp
.op0
= TMR_BASE (ref
);
754 result
->quick_push (temp
);
758 /* For non-calls, store the information that makes up the address. */
762 vn_reference_op_s temp
;
764 memset (&temp
, 0, sizeof (temp
));
765 temp
.type
= TREE_TYPE (ref
);
766 temp
.opcode
= TREE_CODE (ref
);
772 temp
.op0
= TREE_OPERAND (ref
, 1);
775 temp
.op0
= TREE_OPERAND (ref
, 1);
779 /* The base address gets its own vn_reference_op_s structure. */
780 temp
.op0
= TREE_OPERAND (ref
, 1);
781 if (host_integerp (TREE_OPERAND (ref
, 1), 0))
782 temp
.off
= TREE_INT_CST_LOW (TREE_OPERAND (ref
, 1));
785 /* Record bits and position. */
786 temp
.op0
= TREE_OPERAND (ref
, 1);
787 temp
.op1
= TREE_OPERAND (ref
, 2);
790 /* The field decl is enough to unambiguously specify the field,
791 a matching type is not necessary and a mismatching type
792 is always a spurious difference. */
793 temp
.type
= NULL_TREE
;
794 temp
.op0
= TREE_OPERAND (ref
, 1);
795 temp
.op1
= TREE_OPERAND (ref
, 2);
797 tree this_offset
= component_ref_field_offset (ref
);
799 && TREE_CODE (this_offset
) == INTEGER_CST
)
801 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
802 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
805 = tree_to_double_int (this_offset
)
806 + tree_to_double_int (bit_offset
)
807 .rshift (BITS_PER_UNIT
== 8
808 ? 3 : exact_log2 (BITS_PER_UNIT
));
809 if (off
.fits_shwi ())
815 case ARRAY_RANGE_REF
:
817 /* Record index as operand. */
818 temp
.op0
= TREE_OPERAND (ref
, 1);
819 /* Always record lower bounds and element size. */
820 temp
.op1
= array_ref_low_bound (ref
);
821 temp
.op2
= array_ref_element_size (ref
);
822 if (TREE_CODE (temp
.op0
) == INTEGER_CST
823 && TREE_CODE (temp
.op1
) == INTEGER_CST
824 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
826 double_int off
= tree_to_double_int (temp
.op0
);
827 off
+= -tree_to_double_int (temp
.op1
);
828 off
*= tree_to_double_int (temp
.op2
);
829 if (off
.fits_shwi ())
834 if (DECL_HARD_REGISTER (ref
))
843 /* Canonicalize decls to MEM[&decl] which is what we end up with
844 when valueizing MEM[ptr] with ptr = &decl. */
845 temp
.opcode
= MEM_REF
;
846 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
848 result
->safe_push (temp
);
849 temp
.opcode
= ADDR_EXPR
;
850 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
851 temp
.type
= TREE_TYPE (temp
.op0
);
865 if (is_gimple_min_invariant (ref
))
871 /* These are only interesting for their operands, their
872 existence, and their type. They will never be the last
873 ref in the chain of references (IE they require an
874 operand), so we don't have to put anything
875 for op* as it will be handled by the iteration */
877 case VIEW_CONVERT_EXPR
:
881 /* This is only interesting for its constant offset. */
882 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
887 result
->safe_push (temp
);
889 if (REFERENCE_CLASS_P (ref
)
890 || TREE_CODE (ref
) == MODIFY_EXPR
891 || TREE_CODE (ref
) == WITH_SIZE_EXPR
892 || (TREE_CODE (ref
) == ADDR_EXPR
893 && !is_gimple_min_invariant (ref
)))
894 ref
= TREE_OPERAND (ref
, 0);
900 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
901 operands in *OPS, the reference alias set SET and the reference type TYPE.
902 Return true if something useful was produced. */
905 ao_ref_init_from_vn_reference (ao_ref
*ref
,
906 alias_set_type set
, tree type
,
907 vec
<vn_reference_op_s
> ops
)
909 vn_reference_op_t op
;
911 tree base
= NULL_TREE
;
913 HOST_WIDE_INT offset
= 0;
914 HOST_WIDE_INT max_size
;
915 HOST_WIDE_INT size
= -1;
916 tree size_tree
= NULL_TREE
;
917 alias_set_type base_alias_set
= -1;
919 /* First get the final access size from just the outermost expression. */
921 if (op
->opcode
== COMPONENT_REF
)
922 size_tree
= DECL_SIZE (op
->op0
);
923 else if (op
->opcode
== BIT_FIELD_REF
)
927 enum machine_mode mode
= TYPE_MODE (type
);
929 size_tree
= TYPE_SIZE (type
);
931 size
= GET_MODE_BITSIZE (mode
);
933 if (size_tree
!= NULL_TREE
)
935 if (!host_integerp (size_tree
, 1))
938 size
= TREE_INT_CST_LOW (size_tree
);
941 /* Initially, maxsize is the same as the accessed element size.
942 In the following it will only grow (or become -1). */
945 /* Compute cumulative bit-offset for nested component-refs and array-refs,
946 and find the ultimate containing object. */
947 FOR_EACH_VEC_ELT (ops
, i
, op
)
951 /* These may be in the reference ops, but we cannot do anything
952 sensible with them here. */
954 /* Apart from ADDR_EXPR arguments to MEM_REF. */
955 if (base
!= NULL_TREE
956 && TREE_CODE (base
) == MEM_REF
958 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
960 vn_reference_op_t pop
= &ops
[i
-1];
961 base
= TREE_OPERAND (op
->op0
, 0);
968 offset
+= pop
->off
* BITS_PER_UNIT
;
976 /* Record the base objects. */
978 base_alias_set
= get_deref_alias_set (op
->op0
);
979 *op0_p
= build2 (MEM_REF
, op
->type
,
981 op0_p
= &TREE_OPERAND (*op0_p
, 0);
992 /* And now the usual component-reference style ops. */
994 offset
+= tree_low_cst (op
->op1
, 0);
999 tree field
= op
->op0
;
1000 /* We do not have a complete COMPONENT_REF tree here so we
1001 cannot use component_ref_field_offset. Do the interesting
1005 || !host_integerp (DECL_FIELD_OFFSET (field
), 1))
1009 offset
+= (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field
))
1011 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
1016 case ARRAY_RANGE_REF
:
1018 /* We recorded the lower bound and the element size. */
1019 if (!host_integerp (op
->op0
, 0)
1020 || !host_integerp (op
->op1
, 0)
1021 || !host_integerp (op
->op2
, 0))
1025 HOST_WIDE_INT hindex
= TREE_INT_CST_LOW (op
->op0
);
1026 hindex
-= TREE_INT_CST_LOW (op
->op1
);
1027 hindex
*= TREE_INT_CST_LOW (op
->op2
);
1028 hindex
*= BITS_PER_UNIT
;
1040 case VIEW_CONVERT_EXPR
:
1057 if (base
== NULL_TREE
)
1060 ref
->ref
= NULL_TREE
;
1062 ref
->offset
= offset
;
1064 ref
->max_size
= max_size
;
1065 ref
->ref_alias_set
= set
;
1066 if (base_alias_set
!= -1)
1067 ref
->base_alias_set
= base_alias_set
;
1069 ref
->base_alias_set
= get_alias_set (base
);
1070 /* We discount volatiles from value-numbering elsewhere. */
1071 ref
->volatile_p
= false;
1076 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1077 vn_reference_op_s's. */
1080 copy_reference_ops_from_call (gimple call
,
1081 vec
<vn_reference_op_s
> *result
)
1083 vn_reference_op_s temp
;
1085 tree lhs
= gimple_call_lhs (call
);
1087 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1088 different. By adding the lhs here in the vector, we ensure that the
1089 hashcode is different, guaranteeing a different value number. */
1090 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1092 memset (&temp
, 0, sizeof (temp
));
1093 temp
.opcode
= MODIFY_EXPR
;
1094 temp
.type
= TREE_TYPE (lhs
);
1097 result
->safe_push (temp
);
1100 /* Copy the type, opcode, function being called and static chain. */
1101 memset (&temp
, 0, sizeof (temp
));
1102 temp
.type
= gimple_call_return_type (call
);
1103 temp
.opcode
= CALL_EXPR
;
1104 temp
.op0
= gimple_call_fn (call
);
1105 temp
.op1
= gimple_call_chain (call
);
1107 result
->safe_push (temp
);
1109 /* Copy the call arguments. As they can be references as well,
1110 just chain them together. */
1111 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1113 tree callarg
= gimple_call_arg (call
, i
);
1114 copy_reference_ops_from_ref (callarg
, result
);
1118 /* Create a vector of vn_reference_op_s structures from CALL, a
1119 call statement. The vector is not shared. */
1121 static vec
<vn_reference_op_s
>
1122 create_reference_ops_from_call (gimple call
)
1124 vec
<vn_reference_op_s
> result
= vNULL
;
1126 copy_reference_ops_from_call (call
, &result
);
1130 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1131 *I_P to point to the last element of the replacement. */
1133 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1136 unsigned int i
= *i_p
;
1137 vn_reference_op_t op
= &(*ops
)[i
];
1138 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1140 HOST_WIDE_INT addr_offset
= 0;
1142 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1143 from .foo.bar to the preceding MEM_REF offset and replace the
1144 address with &OBJ. */
1145 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1147 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1148 if (addr_base
!= op
->op0
)
1150 double_int off
= tree_to_double_int (mem_op
->op0
);
1151 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1152 off
+= double_int::from_shwi (addr_offset
);
1153 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1154 op
->op0
= build_fold_addr_expr (addr_base
);
1155 if (host_integerp (mem_op
->op0
, 0))
1156 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1162 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1163 *I_P to point to the last element of the replacement. */
1165 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1168 unsigned int i
= *i_p
;
1169 vn_reference_op_t op
= &(*ops
)[i
];
1170 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1172 enum tree_code code
;
1175 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1176 if (!is_gimple_assign (def_stmt
))
1179 code
= gimple_assign_rhs_code (def_stmt
);
1180 if (code
!= ADDR_EXPR
1181 && code
!= POINTER_PLUS_EXPR
)
1184 off
= tree_to_double_int (mem_op
->op0
);
1185 off
= off
.sext (TYPE_PRECISION (TREE_TYPE (mem_op
->op0
)));
1187 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1188 from .foo.bar to the preceding MEM_REF offset and replace the
1189 address with &OBJ. */
1190 if (code
== ADDR_EXPR
)
1192 tree addr
, addr_base
;
1193 HOST_WIDE_INT addr_offset
;
1195 addr
= gimple_assign_rhs1 (def_stmt
);
1196 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1199 || TREE_CODE (addr_base
) != MEM_REF
)
1202 off
+= double_int::from_shwi (addr_offset
);
1203 off
+= mem_ref_offset (addr_base
);
1204 op
->op0
= TREE_OPERAND (addr_base
, 0);
1209 ptr
= gimple_assign_rhs1 (def_stmt
);
1210 ptroff
= gimple_assign_rhs2 (def_stmt
);
1211 if (TREE_CODE (ptr
) != SSA_NAME
1212 || TREE_CODE (ptroff
) != INTEGER_CST
)
1215 off
+= tree_to_double_int (ptroff
);
1219 mem_op
->op0
= double_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1220 if (host_integerp (mem_op
->op0
, 0))
1221 mem_op
->off
= TREE_INT_CST_LOW (mem_op
->op0
);
1224 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1225 op
->op0
= SSA_VAL (op
->op0
);
1226 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1227 op
->opcode
= TREE_CODE (op
->op0
);
1230 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1231 vn_reference_maybe_forwprop_address (ops
, i_p
);
1232 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1233 vn_reference_fold_indirect (ops
, i_p
);
1236 /* Optimize the reference REF to a constant if possible or return
1237 NULL_TREE if not. */
1240 fully_constant_vn_reference_p (vn_reference_t ref
)
1242 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1243 vn_reference_op_t op
;
1245 /* Try to simplify the translated expression if it is
1246 a call to a builtin function with at most two arguments. */
1248 if (op
->opcode
== CALL_EXPR
1249 && TREE_CODE (op
->op0
) == ADDR_EXPR
1250 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1251 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1252 && operands
.length () >= 2
1253 && operands
.length () <= 3)
1255 vn_reference_op_t arg0
, arg1
= NULL
;
1256 bool anyconst
= false;
1257 arg0
= &operands
[1];
1258 if (operands
.length () > 2)
1259 arg1
= &operands
[2];
1260 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1261 || (arg0
->opcode
== ADDR_EXPR
1262 && is_gimple_min_invariant (arg0
->op0
)))
1265 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1266 || (arg1
->opcode
== ADDR_EXPR
1267 && is_gimple_min_invariant (arg1
->op0
))))
1271 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1274 arg1
? arg1
->op0
: NULL
);
1276 && TREE_CODE (folded
) == NOP_EXPR
)
1277 folded
= TREE_OPERAND (folded
, 0);
1279 && is_gimple_min_invariant (folded
))
1284 /* Simplify reads from constant strings. */
1285 else if (op
->opcode
== ARRAY_REF
1286 && TREE_CODE (op
->op0
) == INTEGER_CST
1287 && integer_zerop (op
->op1
)
1288 && operands
.length () == 2)
1290 vn_reference_op_t arg0
;
1291 arg0
= &operands
[1];
1292 if (arg0
->opcode
== STRING_CST
1293 && (TYPE_MODE (op
->type
)
1294 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1295 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1296 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1297 && tree_int_cst_sgn (op
->op0
) >= 0
1298 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1299 return build_int_cst_type (op
->type
,
1300 (TREE_STRING_POINTER (arg0
->op0
)
1301 [TREE_INT_CST_LOW (op
->op0
)]));
1307 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1308 structures into their value numbers. This is done in-place, and
1309 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1310 whether any operands were valueized. */
1312 static vec
<vn_reference_op_s
>
1313 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1315 vn_reference_op_t vro
;
1318 *valueized_anything
= false;
1320 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1322 if (vro
->opcode
== SSA_NAME
1323 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1325 tree tem
= SSA_VAL (vro
->op0
);
1326 if (tem
!= vro
->op0
)
1328 *valueized_anything
= true;
1331 /* If it transforms from an SSA_NAME to a constant, update
1333 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1334 vro
->opcode
= TREE_CODE (vro
->op0
);
1336 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1338 tree tem
= SSA_VAL (vro
->op1
);
1339 if (tem
!= vro
->op1
)
1341 *valueized_anything
= true;
1345 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1347 tree tem
= SSA_VAL (vro
->op2
);
1348 if (tem
!= vro
->op2
)
1350 *valueized_anything
= true;
1354 /* If it transforms from an SSA_NAME to an address, fold with
1355 a preceding indirect reference. */
1358 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1359 && orig
[i
- 1].opcode
== MEM_REF
)
1360 vn_reference_fold_indirect (&orig
, &i
);
1362 && vro
->opcode
== SSA_NAME
1363 && orig
[i
- 1].opcode
== MEM_REF
)
1364 vn_reference_maybe_forwprop_address (&orig
, &i
);
1365 /* If it transforms a non-constant ARRAY_REF into a constant
1366 one, adjust the constant offset. */
1367 else if (vro
->opcode
== ARRAY_REF
1369 && TREE_CODE (vro
->op0
) == INTEGER_CST
1370 && TREE_CODE (vro
->op1
) == INTEGER_CST
1371 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1373 double_int off
= tree_to_double_int (vro
->op0
);
1374 off
+= -tree_to_double_int (vro
->op1
);
1375 off
*= tree_to_double_int (vro
->op2
);
1376 if (off
.fits_shwi ())
1384 static vec
<vn_reference_op_s
>
1385 valueize_refs (vec
<vn_reference_op_s
> orig
)
1388 return valueize_refs_1 (orig
, &tem
);
1391 static vec
<vn_reference_op_s
> shared_lookup_references
;
1393 /* Create a vector of vn_reference_op_s structures from REF, a
1394 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1395 this function. *VALUEIZED_ANYTHING will specify whether any
1396 operands were valueized. */
1398 static vec
<vn_reference_op_s
>
1399 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1403 shared_lookup_references
.truncate (0);
1404 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1405 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1406 valueized_anything
);
1407 return shared_lookup_references
;
1410 /* Create a vector of vn_reference_op_s structures from CALL, a
1411 call statement. The vector is shared among all callers of
1414 static vec
<vn_reference_op_s
>
1415 valueize_shared_reference_ops_from_call (gimple call
)
1419 shared_lookup_references
.truncate (0);
1420 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1421 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1422 return shared_lookup_references
;
1425 /* Lookup a SCCVN reference operation VR in the current hash table.
1426 Returns the resulting value number if it exists in the hash table,
1427 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1428 vn_reference_t stored in the hashtable if something is found. */
1431 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1433 vn_reference_s
**slot
;
1436 hash
= vr
->hashcode
;
1437 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1438 if (!slot
&& current_info
== optimistic_info
)
1439 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1443 *vnresult
= (vn_reference_t
)*slot
;
1444 return ((vn_reference_t
)*slot
)->result
;
1450 static tree
*last_vuse_ptr
;
1451 static vn_lookup_kind vn_walk_kind
;
1452 static vn_lookup_kind default_vn_walk_kind
;
1454 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1455 with the current VUSE and performs the expression lookup. */
1458 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1459 unsigned int cnt
, void *vr_
)
1461 vn_reference_t vr
= (vn_reference_t
)vr_
;
1462 vn_reference_s
**slot
;
1465 /* This bounds the stmt walks we perform on reference lookups
1466 to O(1) instead of O(N) where N is the number of dominating
1468 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1472 *last_vuse_ptr
= vuse
;
1474 /* Fixup vuse and hash. */
1476 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1477 vr
->vuse
= SSA_VAL (vuse
);
1479 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1481 hash
= vr
->hashcode
;
1482 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1483 if (!slot
&& current_info
== optimistic_info
)
1484 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1491 /* Lookup an existing or insert a new vn_reference entry into the
1492 value table for the VUSE, SET, TYPE, OPERANDS reference which
1493 has the value VALUE which is either a constant or an SSA name. */
1495 static vn_reference_t
1496 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1499 vec
<vn_reference_op_s
,
1503 struct vn_reference_s vr1
;
1504 vn_reference_t result
;
1507 vr1
.operands
= operands
;
1510 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1511 if (vn_reference_lookup_1 (&vr1
, &result
))
1513 if (TREE_CODE (value
) == SSA_NAME
)
1514 value_id
= VN_INFO (value
)->value_id
;
1516 value_id
= get_or_alloc_constant_value_id (value
);
1517 return vn_reference_insert_pieces (vuse
, set
, type
,
1518 operands
.copy (), value
, value_id
);
1521 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1522 from the statement defining VUSE and if not successful tries to
1523 translate *REFP and VR_ through an aggregate copy at the definition
1527 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
)
1529 vn_reference_t vr
= (vn_reference_t
)vr_
;
1530 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1532 HOST_WIDE_INT offset
, maxsize
;
1533 static vec
<vn_reference_op_s
>
1536 bool lhs_ref_ok
= false;
1538 /* First try to disambiguate after value-replacing in the definitions LHS. */
1539 if (is_gimple_assign (def_stmt
))
1541 vec
<vn_reference_op_s
> tem
;
1542 tree lhs
= gimple_assign_lhs (def_stmt
);
1543 bool valueized_anything
= false;
1544 /* Avoid re-allocation overhead. */
1545 lhs_ops
.truncate (0);
1546 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1548 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1549 gcc_assert (lhs_ops
== tem
);
1550 if (valueized_anything
)
1552 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1553 get_alias_set (lhs
),
1554 TREE_TYPE (lhs
), lhs_ops
);
1556 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1561 ao_ref_init (&lhs_ref
, lhs
);
1566 base
= ao_ref_base (ref
);
1567 offset
= ref
->offset
;
1568 maxsize
= ref
->max_size
;
1570 /* If we cannot constrain the size of the reference we cannot
1571 test if anything kills it. */
1575 /* We can't deduce anything useful from clobbers. */
1576 if (gimple_clobber_p (def_stmt
))
1579 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1580 from that definition.
1582 if (is_gimple_reg_type (vr
->type
)
1583 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1584 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1585 && host_integerp (gimple_call_arg (def_stmt
, 2), 1)
1586 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1588 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1590 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1591 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1592 size2
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2)) * 8;
1593 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1594 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2))
1596 && operand_equal_p (base
, base2
, 0)
1597 && offset2
<= offset
1598 && offset2
+ size2
>= offset
+ maxsize
)
1600 tree val
= build_zero_cst (vr
->type
);
1601 return vn_reference_lookup_or_insert_for_pieces
1602 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1606 /* 2) Assignment from an empty CONSTRUCTOR. */
1607 else if (is_gimple_reg_type (vr
->type
)
1608 && gimple_assign_single_p (def_stmt
)
1609 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1610 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1613 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1614 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1615 &offset2
, &size2
, &maxsize2
);
1617 && operand_equal_p (base
, base2
, 0)
1618 && offset2
<= offset
1619 && offset2
+ size2
>= offset
+ maxsize
)
1621 tree val
= build_zero_cst (vr
->type
);
1622 return vn_reference_lookup_or_insert_for_pieces
1623 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1627 /* 3) Assignment from a constant. We can use folds native encode/interpret
1628 routines to extract the assigned bits. */
1629 else if (vn_walk_kind
== VN_WALKREWRITE
1630 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1631 && ref
->size
== maxsize
1632 && maxsize
% BITS_PER_UNIT
== 0
1633 && offset
% BITS_PER_UNIT
== 0
1634 && is_gimple_reg_type (vr
->type
)
1635 && gimple_assign_single_p (def_stmt
)
1636 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1639 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1640 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1641 &offset2
, &size2
, &maxsize2
);
1643 && maxsize2
== size2
1644 && size2
% BITS_PER_UNIT
== 0
1645 && offset2
% BITS_PER_UNIT
== 0
1646 && operand_equal_p (base
, base2
, 0)
1647 && offset2
<= offset
1648 && offset2
+ size2
>= offset
+ maxsize
)
1650 /* We support up to 512-bit values (for V8DFmode). */
1651 unsigned char buffer
[64];
1654 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1655 buffer
, sizeof (buffer
));
1658 tree val
= native_interpret_expr (vr
->type
,
1660 + ((offset
- offset2
)
1662 ref
->size
/ BITS_PER_UNIT
);
1664 return vn_reference_lookup_or_insert_for_pieces
1665 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1670 /* 4) Assignment from an SSA name which definition we may be able
1671 to access pieces from. */
1672 else if (ref
->size
== maxsize
1673 && is_gimple_reg_type (vr
->type
)
1674 && gimple_assign_single_p (def_stmt
)
1675 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1677 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1678 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1679 if (is_gimple_assign (def_stmt2
)
1680 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1681 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1682 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1685 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1686 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1687 &offset2
, &size2
, &maxsize2
);
1688 off
= offset
- offset2
;
1690 && maxsize2
== size2
1691 && operand_equal_p (base
, base2
, 0)
1692 && offset2
<= offset
1693 && offset2
+ size2
>= offset
+ maxsize
)
1695 tree val
= NULL_TREE
;
1697 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1698 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1701 val
= gimple_assign_rhs1 (def_stmt2
);
1702 else if (off
== elsz
)
1703 val
= gimple_assign_rhs2 (def_stmt2
);
1705 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1708 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1709 unsigned i
= off
/ elsz
;
1710 if (i
< CONSTRUCTOR_NELTS (ctor
))
1712 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1713 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1715 if (TREE_CODE (TREE_TYPE (elt
->value
))
1722 return vn_reference_lookup_or_insert_for_pieces
1723 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1728 /* 5) For aggregate copies translate the reference through them if
1729 the copy kills ref. */
1730 else if (vn_walk_kind
== VN_WALKREWRITE
1731 && gimple_assign_single_p (def_stmt
)
1732 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1733 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1734 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1737 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1739 vec
<vn_reference_op_s
>
1741 vn_reference_op_t vro
;
1747 /* See if the assignment kills REF. */
1748 base2
= ao_ref_base (&lhs_ref
);
1749 offset2
= lhs_ref
.offset
;
1750 size2
= lhs_ref
.size
;
1751 maxsize2
= lhs_ref
.max_size
;
1753 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1755 || offset2
+ size2
< offset
+ maxsize
)
1758 /* Find the common base of ref and the lhs. lhs_ops already
1759 contains valueized operands for the lhs. */
1760 i
= vr
->operands
.length () - 1;
1761 j
= lhs_ops
.length () - 1;
1762 while (j
>= 0 && i
>= 0
1763 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1769 /* ??? The innermost op should always be a MEM_REF and we already
1770 checked that the assignment to the lhs kills vr. Thus for
1771 aggregate copies using char[] types the vn_reference_op_eq
1772 may fail when comparing types for compatibility. But we really
1773 don't care here - further lookups with the rewritten operands
1774 will simply fail if we messed up types too badly. */
1775 if (j
== 0 && i
>= 0
1776 && lhs_ops
[0].opcode
== MEM_REF
1777 && lhs_ops
[0].off
!= -1
1778 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1781 /* i now points to the first additional op.
1782 ??? LHS may not be completely contained in VR, one or more
1783 VIEW_CONVERT_EXPRs could be in its way. We could at least
1784 try handling outermost VIEW_CONVERT_EXPRs. */
1788 /* Now re-write REF to be based on the rhs of the assignment. */
1789 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1790 /* We need to pre-pend vr->operands[0..i] to rhs. */
1791 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1793 vec
<vn_reference_op_s
> old
= vr
->operands
;
1794 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1795 if (old
== shared_lookup_references
1796 && vr
->operands
!= old
)
1797 shared_lookup_references
= vNULL
;
1800 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1801 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1802 vr
->operands
[i
+ 1 + j
] = *vro
;
1804 vr
->operands
= valueize_refs (vr
->operands
);
1805 vr
->hashcode
= vn_reference_compute_hash (vr
);
1807 /* Adjust *ref from the new operands. */
1808 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1810 /* This can happen with bitfields. */
1811 if (ref
->size
!= r
.size
)
1815 /* Do not update last seen VUSE after translating. */
1816 last_vuse_ptr
= NULL
;
1818 /* Keep looking for the adjusted *REF / VR pair. */
1822 /* 6) For memcpy copies translate the reference through them if
1823 the copy kills ref. */
1824 else if (vn_walk_kind
== VN_WALKREWRITE
1825 && is_gimple_reg_type (vr
->type
)
1826 /* ??? Handle BCOPY as well. */
1827 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1828 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1829 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1830 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1831 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1832 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1833 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1834 && host_integerp (gimple_call_arg (def_stmt
, 2), 1))
1838 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1839 vn_reference_op_s op
;
1843 /* Only handle non-variable, addressable refs. */
1844 if (ref
->size
!= maxsize
1845 || offset
% BITS_PER_UNIT
!= 0
1846 || ref
->size
% BITS_PER_UNIT
!= 0)
1849 /* Extract a pointer base and an offset for the destination. */
1850 lhs
= gimple_call_arg (def_stmt
, 0);
1852 if (TREE_CODE (lhs
) == SSA_NAME
)
1853 lhs
= SSA_VAL (lhs
);
1854 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1856 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1860 if (TREE_CODE (tem
) == MEM_REF
1861 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1863 lhs
= TREE_OPERAND (tem
, 0);
1864 lhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1866 else if (DECL_P (tem
))
1867 lhs
= build_fold_addr_expr (tem
);
1871 if (TREE_CODE (lhs
) != SSA_NAME
1872 && TREE_CODE (lhs
) != ADDR_EXPR
)
1875 /* Extract a pointer base and an offset for the source. */
1876 rhs
= gimple_call_arg (def_stmt
, 1);
1878 if (TREE_CODE (rhs
) == SSA_NAME
)
1879 rhs
= SSA_VAL (rhs
);
1880 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1882 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1886 if (TREE_CODE (tem
) == MEM_REF
1887 && host_integerp (TREE_OPERAND (tem
, 1), 1))
1889 rhs
= TREE_OPERAND (tem
, 0);
1890 rhs_offset
+= TREE_INT_CST_LOW (TREE_OPERAND (tem
, 1));
1892 else if (DECL_P (tem
))
1893 rhs
= build_fold_addr_expr (tem
);
1897 if (TREE_CODE (rhs
) != SSA_NAME
1898 && TREE_CODE (rhs
) != ADDR_EXPR
)
1901 copy_size
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2));
1903 /* The bases of the destination and the references have to agree. */
1904 if ((TREE_CODE (base
) != MEM_REF
1906 || (TREE_CODE (base
) == MEM_REF
1907 && (TREE_OPERAND (base
, 0) != lhs
1908 || !host_integerp (TREE_OPERAND (base
, 1), 1)))
1910 && (TREE_CODE (lhs
) != ADDR_EXPR
1911 || TREE_OPERAND (lhs
, 0) != base
)))
1914 /* And the access has to be contained within the memcpy destination. */
1915 at
= offset
/ BITS_PER_UNIT
;
1916 if (TREE_CODE (base
) == MEM_REF
)
1917 at
+= TREE_INT_CST_LOW (TREE_OPERAND (base
, 1));
1919 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1922 /* Make room for 2 operands in the new reference. */
1923 if (vr
->operands
.length () < 2)
1925 vec
<vn_reference_op_s
> old
= vr
->operands
;
1926 vr
->operands
.safe_grow_cleared (2);
1927 if (old
== shared_lookup_references
1928 && vr
->operands
!= old
)
1929 shared_lookup_references
.create (0);
1932 vr
->operands
.truncate (2);
1934 /* The looked-through reference is a simple MEM_REF. */
1935 memset (&op
, 0, sizeof (op
));
1937 op
.opcode
= MEM_REF
;
1938 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
1939 op
.off
= at
- lhs_offset
+ rhs_offset
;
1940 vr
->operands
[0] = op
;
1941 op
.type
= TREE_TYPE (rhs
);
1942 op
.opcode
= TREE_CODE (rhs
);
1945 vr
->operands
[1] = op
;
1946 vr
->hashcode
= vn_reference_compute_hash (vr
);
1948 /* Adjust *ref from the new operands. */
1949 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1951 /* This can happen with bitfields. */
1952 if (ref
->size
!= r
.size
)
1956 /* Do not update last seen VUSE after translating. */
1957 last_vuse_ptr
= NULL
;
1959 /* Keep looking for the adjusted *REF / VR pair. */
1963 /* Bail out and stop walking. */
1967 /* Lookup a reference operation by it's parts, in the current hash table.
1968 Returns the resulting value number if it exists in the hash table,
1969 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1970 vn_reference_t stored in the hashtable if something is found. */
1973 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
1974 vec
<vn_reference_op_s
> operands
,
1975 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
1977 struct vn_reference_s vr1
;
1985 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1986 shared_lookup_references
.truncate (0);
1987 shared_lookup_references
.safe_grow (operands
.length ());
1988 memcpy (shared_lookup_references
.address (),
1989 operands
.address (),
1990 sizeof (vn_reference_op_s
)
1991 * operands
.length ());
1992 vr1
.operands
= operands
= shared_lookup_references
1993 = valueize_refs (shared_lookup_references
);
1996 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1997 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2000 vn_reference_lookup_1 (&vr1
, vnresult
);
2002 && kind
!= VN_NOWALK
2006 vn_walk_kind
= kind
;
2007 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2009 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2010 vn_reference_lookup_2
,
2011 vn_reference_lookup_3
, &vr1
);
2012 if (vr1
.operands
!= operands
)
2013 vr1
.operands
.release ();
2017 return (*vnresult
)->result
;
2022 /* Lookup OP in the current hash table, and return the resulting value
2023 number if it exists in the hash table. Return NULL_TREE if it does
2024 not exist in the hash table or if the result field of the structure
2025 was NULL.. VNRESULT will be filled in with the vn_reference_t
2026 stored in the hashtable if one exists. */
2029 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2030 vn_reference_t
*vnresult
)
2032 vec
<vn_reference_op_s
> operands
;
2033 struct vn_reference_s vr1
;
2035 bool valuezied_anything
;
2040 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2041 vr1
.operands
= operands
2042 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2043 vr1
.type
= TREE_TYPE (op
);
2044 vr1
.set
= get_alias_set (op
);
2045 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2046 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2049 if (kind
!= VN_NOWALK
2052 vn_reference_t wvnresult
;
2054 /* Make sure to use a valueized reference if we valueized anything.
2055 Otherwise preserve the full reference for advanced TBAA. */
2056 if (!valuezied_anything
2057 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2059 ao_ref_init (&r
, op
);
2060 vn_walk_kind
= kind
;
2062 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2063 vn_reference_lookup_2
,
2064 vn_reference_lookup_3
, &vr1
);
2065 if (vr1
.operands
!= operands
)
2066 vr1
.operands
.release ();
2070 *vnresult
= wvnresult
;
2071 return wvnresult
->result
;
2077 return vn_reference_lookup_1 (&vr1
, vnresult
);
2081 /* Insert OP into the current hash table with a value number of
2082 RESULT, and return the resulting reference structure we created. */
2085 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2087 vn_reference_s
**slot
;
2091 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2092 if (TREE_CODE (result
) == SSA_NAME
)
2093 vr1
->value_id
= VN_INFO (result
)->value_id
;
2095 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2096 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2097 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2098 vr1
->type
= TREE_TYPE (op
);
2099 vr1
->set
= get_alias_set (op
);
2100 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2101 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2102 vr1
->result_vdef
= vdef
;
2104 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2107 /* Because we lookup stores using vuses, and value number failures
2108 using the vdefs (see visit_reference_op_store for how and why),
2109 it's possible that on failure we may try to insert an already
2110 inserted store. This is not wrong, there is no ssa name for a
2111 store that we could use as a differentiator anyway. Thus, unlike
2112 the other lookup functions, you cannot gcc_assert (!*slot)
2115 /* But free the old slot in case of a collision. */
2117 free_reference (*slot
);
2123 /* Insert a reference by it's pieces into the current hash table with
2124 a value number of RESULT. Return the resulting reference
2125 structure we created. */
2128 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2129 vec
<vn_reference_op_s
> operands
,
2130 tree result
, unsigned int value_id
)
2133 vn_reference_s
**slot
;
2136 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2137 vr1
->value_id
= value_id
;
2138 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2139 vr1
->operands
= valueize_refs (operands
);
2142 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2143 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2144 result
= SSA_VAL (result
);
2145 vr1
->result
= result
;
2147 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2150 /* At this point we should have all the things inserted that we have
2151 seen before, and we should never try inserting something that
2153 gcc_assert (!*slot
);
2155 free_reference (*slot
);
2161 /* Compute and return the hash value for nary operation VBO1. */
2164 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2169 for (i
= 0; i
< vno1
->length
; ++i
)
2170 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2171 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2173 if (vno1
->length
== 2
2174 && commutative_tree_code (vno1
->opcode
)
2175 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2177 tree temp
= vno1
->op
[0];
2178 vno1
->op
[0] = vno1
->op
[1];
2182 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2183 for (i
= 0; i
< vno1
->length
; ++i
)
2184 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2189 /* Compare nary operations VNO1 and VNO2 and return true if they are
2193 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2197 if (vno1
->hashcode
!= vno2
->hashcode
)
2200 if (vno1
->length
!= vno2
->length
)
2203 if (vno1
->opcode
!= vno2
->opcode
2204 || !types_compatible_p (vno1
->type
, vno2
->type
))
2207 for (i
= 0; i
< vno1
->length
; ++i
)
2208 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2214 /* Initialize VNO from the pieces provided. */
2217 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2218 enum tree_code code
, tree type
, tree
*ops
)
2221 vno
->length
= length
;
2223 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2226 /* Initialize VNO from OP. */
2229 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2233 vno
->opcode
= TREE_CODE (op
);
2234 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2235 vno
->type
= TREE_TYPE (op
);
2236 for (i
= 0; i
< vno
->length
; ++i
)
2237 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2240 /* Return the number of operands for a vn_nary ops structure from STMT. */
2243 vn_nary_length_from_stmt (gimple stmt
)
2245 switch (gimple_assign_rhs_code (stmt
))
2249 case VIEW_CONVERT_EXPR
:
2256 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2259 return gimple_num_ops (stmt
) - 1;
2263 /* Initialize VNO from STMT. */
2266 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2270 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2271 vno
->type
= gimple_expr_type (stmt
);
2272 switch (vno
->opcode
)
2276 case VIEW_CONVERT_EXPR
:
2278 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2283 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2284 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2285 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2289 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2290 for (i
= 0; i
< vno
->length
; ++i
)
2291 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2295 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2296 vno
->length
= gimple_num_ops (stmt
) - 1;
2297 for (i
= 0; i
< vno
->length
; ++i
)
2298 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2302 /* Compute the hashcode for VNO and look for it in the hash table;
2303 return the resulting value number if it exists in the hash table.
2304 Return NULL_TREE if it does not exist in the hash table or if the
2305 result field of the operation is NULL. VNRESULT will contain the
2306 vn_nary_op_t from the hashtable if it exists. */
2309 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2311 vn_nary_op_s
**slot
;
2316 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2317 slot
= current_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2318 if (!slot
&& current_info
== optimistic_info
)
2319 slot
= valid_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2324 return (*slot
)->result
;
2327 /* Lookup a n-ary operation by its pieces and return the resulting value
2328 number if it exists in the hash table. Return NULL_TREE if it does
2329 not exist in the hash table or if the result field of the operation
2330 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2334 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2335 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2337 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2338 sizeof_vn_nary_op (length
));
2339 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2340 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2343 /* Lookup OP in the current hash table, and return the resulting value
2344 number if it exists in the hash table. Return NULL_TREE if it does
2345 not exist in the hash table or if the result field of the operation
2346 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2350 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2353 = XALLOCAVAR (struct vn_nary_op_s
,
2354 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2355 init_vn_nary_op_from_op (vno1
, op
);
2356 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2359 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2360 value number if it exists in the hash table. Return NULL_TREE if
2361 it does not exist in the hash table. VNRESULT will contain the
2362 vn_nary_op_t from the hashtable if it exists. */
2365 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2368 = XALLOCAVAR (struct vn_nary_op_s
,
2369 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2370 init_vn_nary_op_from_stmt (vno1
, stmt
);
2371 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2374 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2377 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2379 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2382 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2386 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2388 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2389 ¤t_info
->nary_obstack
);
2391 vno1
->value_id
= value_id
;
2392 vno1
->length
= length
;
2393 vno1
->result
= result
;
2398 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2399 VNO->HASHCODE first. */
2402 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type table
,
2405 vn_nary_op_s
**slot
;
2408 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2410 slot
= table
.find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2411 gcc_assert (!*slot
);
2417 /* Insert a n-ary operation into the current hash table using it's
2418 pieces. Return the vn_nary_op_t structure we created and put in
2422 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2423 tree type
, tree
*ops
,
2424 tree result
, unsigned int value_id
)
2426 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2427 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2428 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2431 /* Insert OP into the current hash table with a value number of
2432 RESULT. Return the vn_nary_op_t structure we created and put in
2436 vn_nary_op_insert (tree op
, tree result
)
2438 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2441 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2442 init_vn_nary_op_from_op (vno1
, op
);
2443 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2446 /* Insert the rhs of STMT into the current hash table with a value number of
2450 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2453 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2454 result
, VN_INFO (result
)->value_id
);
2455 init_vn_nary_op_from_stmt (vno1
, stmt
);
2456 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2459 /* Compute a hashcode for PHI operation VP1 and return it. */
2461 static inline hashval_t
2462 vn_phi_compute_hash (vn_phi_t vp1
)
2469 result
= vp1
->block
->index
;
2471 /* If all PHI arguments are constants we need to distinguish
2472 the PHI node via its type. */
2474 result
+= vn_hash_type (type
);
2476 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2478 if (phi1op
== VN_TOP
)
2480 result
= iterative_hash_expr (phi1op
, result
);
2486 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2489 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2491 if (vp1
->hashcode
!= vp2
->hashcode
)
2494 if (vp1
->block
== vp2
->block
)
2499 /* If the PHI nodes do not have compatible types
2500 they are not the same. */
2501 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2504 /* Any phi in the same block will have it's arguments in the
2505 same edge order, because of how we store phi nodes. */
2506 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2508 tree phi2op
= vp2
->phiargs
[i
];
2509 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2511 if (!expressions_equal_p (phi1op
, phi2op
))
2519 static vec
<tree
> shared_lookup_phiargs
;
2521 /* Lookup PHI in the current hash table, and return the resulting
2522 value number if it exists in the hash table. Return NULL_TREE if
2523 it does not exist in the hash table. */
2526 vn_phi_lookup (gimple phi
)
2529 struct vn_phi_s vp1
;
2532 shared_lookup_phiargs
.truncate (0);
2534 /* Canonicalize the SSA_NAME's to their value number. */
2535 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2537 tree def
= PHI_ARG_DEF (phi
, i
);
2538 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2539 shared_lookup_phiargs
.safe_push (def
);
2541 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2542 vp1
.phiargs
= shared_lookup_phiargs
;
2543 vp1
.block
= gimple_bb (phi
);
2544 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2545 slot
= current_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2546 if (!slot
&& current_info
== optimistic_info
)
2547 slot
= valid_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2550 return (*slot
)->result
;
2553 /* Insert PHI into the current hash table with a value number of
2557 vn_phi_insert (gimple phi
, tree result
)
2560 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2562 vec
<tree
> args
= vNULL
;
2564 /* Canonicalize the SSA_NAME's to their value number. */
2565 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2567 tree def
= PHI_ARG_DEF (phi
, i
);
2568 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2569 args
.safe_push (def
);
2571 vp1
->value_id
= VN_INFO (result
)->value_id
;
2572 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2573 vp1
->phiargs
= args
;
2574 vp1
->block
= gimple_bb (phi
);
2575 vp1
->result
= result
;
2576 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2578 slot
= current_info
->phis
.find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2580 /* Because we iterate over phi operations more than once, it's
2581 possible the slot might already exist here, hence no assert.*/
2587 /* Print set of components in strongly connected component SCC to OUT. */
2590 print_scc (FILE *out
, vec
<tree
> scc
)
2595 fprintf (out
, "SCC consists of:");
2596 FOR_EACH_VEC_ELT (scc
, i
, var
)
2599 print_generic_expr (out
, var
, 0);
2601 fprintf (out
, "\n");
2604 /* Set the value number of FROM to TO, return true if it has changed
2608 set_ssa_val_to (tree from
, tree to
)
2610 tree currval
= SSA_VAL (from
);
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);
2646 if (currval
!= to
&& !operand_equal_p (currval
, to
, OEP_PURE_SAME
))
2648 VN_INFO (from
)->valnum
= to
;
2649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2650 fprintf (dump_file
, " (changed)\n");
2653 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2654 fprintf (dump_file
, "\n");
2658 /* Mark as processed all the definitions in the defining stmt of USE, or
2662 mark_use_processed (tree use
)
2666 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2668 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2670 VN_INFO (use
)->use_processed
= true;
2674 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2676 tree def
= DEF_FROM_PTR (defp
);
2678 VN_INFO (def
)->use_processed
= true;
2682 /* Set all definitions in STMT to value number to themselves.
2683 Return true if a value number changed. */
2686 defs_to_varying (gimple stmt
)
2688 bool changed
= false;
2692 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2694 tree def
= DEF_FROM_PTR (defp
);
2695 changed
|= set_ssa_val_to (def
, def
);
2700 static bool expr_has_constants (tree expr
);
2701 static tree
valueize_expr (tree expr
);
2703 /* Visit a copy between LHS and RHS, return true if the value number
2707 visit_copy (tree lhs
, tree rhs
)
2709 /* The copy may have a more interesting constant filled expression
2710 (we don't, since we know our RHS is just an SSA name). */
2711 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2712 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2714 /* And finally valueize. */
2715 rhs
= SSA_VAL (rhs
);
2717 return set_ssa_val_to (lhs
, rhs
);
2720 /* Visit a nary operator RHS, value number it, and return true if the
2721 value number of LHS has changed as a result. */
2724 visit_nary_op (tree lhs
, gimple stmt
)
2726 bool changed
= false;
2727 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2730 changed
= set_ssa_val_to (lhs
, result
);
2733 changed
= set_ssa_val_to (lhs
, lhs
);
2734 vn_nary_op_insert_stmt (stmt
, lhs
);
2740 /* Visit a call STMT storing into LHS. Return true if the value number
2741 of the LHS has changed as a result. */
2744 visit_reference_op_call (tree lhs
, gimple stmt
)
2746 bool changed
= false;
2747 struct vn_reference_s vr1
;
2748 vn_reference_t vnresult
= NULL
;
2749 tree vuse
= gimple_vuse (stmt
);
2750 tree vdef
= gimple_vdef (stmt
);
2752 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2753 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2756 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2757 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2758 vr1
.type
= gimple_expr_type (stmt
);
2760 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2761 vn_reference_lookup_1 (&vr1
, &vnresult
);
2765 if (vnresult
->result_vdef
)
2766 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2768 if (!vnresult
->result
&& lhs
)
2769 vnresult
->result
= lhs
;
2771 if (vnresult
->result
&& lhs
)
2773 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2775 if (VN_INFO (vnresult
->result
)->has_constants
)
2776 VN_INFO (lhs
)->has_constants
= true;
2781 vn_reference_s
**slot
;
2784 changed
|= set_ssa_val_to (vdef
, vdef
);
2786 changed
|= set_ssa_val_to (lhs
, lhs
);
2787 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2788 vr2
->vuse
= vr1
.vuse
;
2789 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2790 vr2
->type
= vr1
.type
;
2792 vr2
->hashcode
= vr1
.hashcode
;
2794 vr2
->result_vdef
= vdef
;
2795 slot
= current_info
->references
.find_slot_with_hash (vr2
, vr2
->hashcode
,
2798 free_reference (*slot
);
2805 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2806 and return true if the value number of the LHS has changed as a result. */
2809 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2811 bool changed
= false;
2815 last_vuse
= gimple_vuse (stmt
);
2816 last_vuse_ptr
= &last_vuse
;
2817 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2818 default_vn_walk_kind
, NULL
);
2819 last_vuse_ptr
= NULL
;
2821 /* If we have a VCE, try looking up its operand as it might be stored in
2822 a different type. */
2823 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2824 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2825 default_vn_walk_kind
, NULL
);
2827 /* We handle type-punning through unions by value-numbering based
2828 on offset and size of the access. Be prepared to handle a
2829 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2831 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2833 /* We will be setting the value number of lhs to the value number
2834 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2835 So first simplify and lookup this expression to see if it
2836 is already available. */
2837 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2838 if ((CONVERT_EXPR_P (val
)
2839 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2840 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2842 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2843 if ((CONVERT_EXPR_P (tem
)
2844 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2845 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2846 TREE_TYPE (val
), tem
)))
2850 if (!is_gimple_min_invariant (val
)
2851 && TREE_CODE (val
) != SSA_NAME
)
2852 result
= vn_nary_op_lookup (val
, NULL
);
2853 /* If the expression is not yet available, value-number lhs to
2854 a new SSA_NAME we create. */
2857 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2859 /* Initialize value-number information properly. */
2860 VN_INFO_GET (result
)->valnum
= result
;
2861 VN_INFO (result
)->value_id
= get_next_value_id ();
2862 VN_INFO (result
)->expr
= val
;
2863 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2864 VN_INFO (result
)->needs_insertion
= true;
2865 /* As all "inserted" statements are singleton SCCs, insert
2866 to the valid table. This is strictly needed to
2867 avoid re-generating new value SSA_NAMEs for the same
2868 expression during SCC iteration over and over (the
2869 optimistic table gets cleared after each iteration).
2870 We do not need to insert into the optimistic table, as
2871 lookups there will fall back to the valid table. */
2872 if (current_info
== optimistic_info
)
2874 current_info
= valid_info
;
2875 vn_nary_op_insert (val
, result
);
2876 current_info
= optimistic_info
;
2879 vn_nary_op_insert (val
, result
);
2880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2882 fprintf (dump_file
, "Inserting name ");
2883 print_generic_expr (dump_file
, result
, 0);
2884 fprintf (dump_file
, " for expression ");
2885 print_generic_expr (dump_file
, val
, 0);
2886 fprintf (dump_file
, "\n");
2893 changed
= set_ssa_val_to (lhs
, result
);
2894 if (TREE_CODE (result
) == SSA_NAME
2895 && VN_INFO (result
)->has_constants
)
2897 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2898 VN_INFO (lhs
)->has_constants
= true;
2903 changed
= set_ssa_val_to (lhs
, lhs
);
2904 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
2911 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2912 and return true if the value number of the LHS has changed as a result. */
2915 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2917 bool changed
= false;
2918 vn_reference_t vnresult
= NULL
;
2919 tree result
, assign
;
2920 bool resultsame
= false;
2921 tree vuse
= gimple_vuse (stmt
);
2922 tree vdef
= gimple_vdef (stmt
);
2924 /* First we want to lookup using the *vuses* from the store and see
2925 if there the last store to this location with the same address
2928 The vuses represent the memory state before the store. If the
2929 memory state, address, and value of the store is the same as the
2930 last store to this location, then this store will produce the
2931 same memory state as that store.
2933 In this case the vdef versions for this store are value numbered to those
2934 vuse versions, since they represent the same memory state after
2937 Otherwise, the vdefs for the store are used when inserting into
2938 the table, since the store generates a new memory state. */
2940 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
2944 if (TREE_CODE (result
) == SSA_NAME
)
2945 result
= SSA_VAL (result
);
2946 if (TREE_CODE (op
) == SSA_NAME
)
2948 resultsame
= expressions_equal_p (result
, op
);
2951 if (!result
|| !resultsame
)
2953 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2954 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
2957 VN_INFO (vdef
)->use_processed
= true;
2958 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2962 if (!result
|| !resultsame
)
2964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2966 fprintf (dump_file
, "No store match\n");
2967 fprintf (dump_file
, "Value numbering store ");
2968 print_generic_expr (dump_file
, lhs
, 0);
2969 fprintf (dump_file
, " to ");
2970 print_generic_expr (dump_file
, op
, 0);
2971 fprintf (dump_file
, "\n");
2973 /* Have to set value numbers before insert, since insert is
2974 going to valueize the references in-place. */
2977 changed
|= set_ssa_val_to (vdef
, vdef
);
2980 /* Do not insert structure copies into the tables. */
2981 if (is_gimple_min_invariant (op
)
2982 || is_gimple_reg (op
))
2983 vn_reference_insert (lhs
, op
, vdef
, NULL
);
2985 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
2986 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
2990 /* We had a match, so value number the vdef to have the value
2991 number of the vuse it came from. */
2993 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2994 fprintf (dump_file
, "Store matched earlier value,"
2995 "value numbering store vdefs to matching vuses.\n");
2997 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3003 /* Visit and value number PHI, return true if the value number
3007 visit_phi (gimple phi
)
3009 bool changed
= false;
3011 tree sameval
= VN_TOP
;
3012 bool allsame
= true;
3015 /* TODO: We could check for this in init_sccvn, and replace this
3016 with a gcc_assert. */
3017 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3018 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3020 /* See if all non-TOP arguments have the same value. TOP is
3021 equivalent to everything, so we can ignore it. */
3022 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3024 tree def
= PHI_ARG_DEF (phi
, i
);
3026 if (TREE_CODE (def
) == SSA_NAME
)
3027 def
= SSA_VAL (def
);
3030 if (sameval
== VN_TOP
)
3036 if (!expressions_equal_p (def
, sameval
))
3044 /* If all value numbered to the same value, the phi node has that
3048 if (is_gimple_min_invariant (sameval
))
3050 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
3051 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3055 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3056 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3059 if (TREE_CODE (sameval
) == SSA_NAME
)
3060 return visit_copy (PHI_RESULT (phi
), sameval
);
3062 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3065 /* Otherwise, see if it is equivalent to a phi node in this block. */
3066 result
= vn_phi_lookup (phi
);
3069 if (TREE_CODE (result
) == SSA_NAME
)
3070 changed
= visit_copy (PHI_RESULT (phi
), result
);
3072 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3076 vn_phi_insert (phi
, PHI_RESULT (phi
));
3077 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3078 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3079 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3085 /* Return true if EXPR contains constants. */
3088 expr_has_constants (tree expr
)
3090 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3093 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3096 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3097 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3098 /* Constants inside reference ops are rarely interesting, but
3099 it can take a lot of looking to find them. */
3101 case tcc_declaration
:
3104 return is_gimple_min_invariant (expr
);
3109 /* Return true if STMT contains constants. */
3112 stmt_has_constants (gimple stmt
)
3116 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3119 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3121 case GIMPLE_TERNARY_RHS
:
3122 tem
= gimple_assign_rhs3 (stmt
);
3123 if (TREE_CODE (tem
) == SSA_NAME
)
3124 tem
= SSA_VAL (tem
);
3125 if (is_gimple_min_invariant (tem
))
3129 case GIMPLE_BINARY_RHS
:
3130 tem
= gimple_assign_rhs2 (stmt
);
3131 if (TREE_CODE (tem
) == SSA_NAME
)
3132 tem
= SSA_VAL (tem
);
3133 if (is_gimple_min_invariant (tem
))
3137 case GIMPLE_SINGLE_RHS
:
3138 /* Constants inside reference ops are rarely interesting, but
3139 it can take a lot of looking to find them. */
3140 case GIMPLE_UNARY_RHS
:
3141 tem
= gimple_assign_rhs1 (stmt
);
3142 if (TREE_CODE (tem
) == SSA_NAME
)
3143 tem
= SSA_VAL (tem
);
3144 return is_gimple_min_invariant (tem
);
3152 /* Replace SSA_NAMES in expr with their value numbers, and return the
3154 This is performed in place. */
3157 valueize_expr (tree expr
)
3159 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3162 TREE_OPERAND (expr
, 1) = vn_valueize (TREE_OPERAND (expr
, 1));
3165 TREE_OPERAND (expr
, 0) = vn_valueize (TREE_OPERAND (expr
, 0));
3172 /* Simplify the binary expression RHS, and return the result if
3176 simplify_binary_expression (gimple stmt
)
3178 tree result
= NULL_TREE
;
3179 tree op0
= gimple_assign_rhs1 (stmt
);
3180 tree op1
= gimple_assign_rhs2 (stmt
);
3181 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3183 /* This will not catch every single case we could combine, but will
3184 catch those with constants. The goal here is to simultaneously
3185 combine constants between expressions, but avoid infinite
3186 expansion of expressions during simplification. */
3187 if (TREE_CODE (op0
) == SSA_NAME
)
3189 if (VN_INFO (op0
)->has_constants
3190 || TREE_CODE_CLASS (code
) == tcc_comparison
3191 || code
== COMPLEX_EXPR
)
3192 op0
= valueize_expr (vn_get_expr_for (op0
));
3194 op0
= vn_valueize (op0
);
3197 if (TREE_CODE (op1
) == SSA_NAME
)
3199 if (VN_INFO (op1
)->has_constants
3200 || code
== COMPLEX_EXPR
)
3201 op1
= valueize_expr (vn_get_expr_for (op1
));
3203 op1
= vn_valueize (op1
);
3206 /* Pointer plus constant can be represented as invariant address.
3207 Do so to allow further propatation, see also tree forwprop. */
3208 if (code
== POINTER_PLUS_EXPR
3209 && host_integerp (op1
, 1)
3210 && TREE_CODE (op0
) == ADDR_EXPR
3211 && is_gimple_min_invariant (op0
))
3212 return build_invariant_address (TREE_TYPE (op0
),
3213 TREE_OPERAND (op0
, 0),
3214 TREE_INT_CST_LOW (op1
));
3216 /* Avoid folding if nothing changed. */
3217 if (op0
== gimple_assign_rhs1 (stmt
)
3218 && op1
== gimple_assign_rhs2 (stmt
))
3221 fold_defer_overflow_warnings ();
3223 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3225 STRIP_USELESS_TYPE_CONVERSION (result
);
3227 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3230 /* Make sure result is not a complex expression consisting
3231 of operators of operators (IE (a + b) + (a + c))
3232 Otherwise, we will end up with unbounded expressions if
3233 fold does anything at all. */
3234 if (result
&& valid_gimple_rhs_p (result
))
3240 /* Simplify the unary expression RHS, and return the result if
3244 simplify_unary_expression (gimple stmt
)
3246 tree result
= NULL_TREE
;
3247 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3248 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3250 /* We handle some tcc_reference codes here that are all
3251 GIMPLE_ASSIGN_SINGLE codes. */
3252 if (code
== REALPART_EXPR
3253 || code
== IMAGPART_EXPR
3254 || code
== VIEW_CONVERT_EXPR
3255 || code
== BIT_FIELD_REF
)
3256 op0
= TREE_OPERAND (op0
, 0);
3258 if (TREE_CODE (op0
) != SSA_NAME
)
3262 if (VN_INFO (op0
)->has_constants
)
3263 op0
= valueize_expr (vn_get_expr_for (op0
));
3264 else if (CONVERT_EXPR_CODE_P (code
)
3265 || code
== REALPART_EXPR
3266 || code
== IMAGPART_EXPR
3267 || code
== VIEW_CONVERT_EXPR
3268 || code
== BIT_FIELD_REF
)
3270 /* We want to do tree-combining on conversion-like expressions.
3271 Make sure we feed only SSA_NAMEs or constants to fold though. */
3272 tree tem
= valueize_expr (vn_get_expr_for (op0
));
3273 if (UNARY_CLASS_P (tem
)
3274 || BINARY_CLASS_P (tem
)
3275 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3276 || TREE_CODE (tem
) == SSA_NAME
3277 || TREE_CODE (tem
) == CONSTRUCTOR
3278 || is_gimple_min_invariant (tem
))
3282 /* Avoid folding if nothing changed, but remember the expression. */
3283 if (op0
== orig_op0
)
3286 if (code
== BIT_FIELD_REF
)
3288 tree rhs
= gimple_assign_rhs1 (stmt
);
3289 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3290 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3293 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3296 STRIP_USELESS_TYPE_CONVERSION (result
);
3297 if (valid_gimple_rhs_p (result
))
3304 /* Try to simplify RHS using equivalences and constant folding. */
3307 try_to_simplify (gimple stmt
)
3309 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3312 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3313 in this case, there is no point in doing extra work. */
3314 if (code
== SSA_NAME
)
3317 /* First try constant folding based on our current lattice. */
3318 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3320 && (TREE_CODE (tem
) == SSA_NAME
3321 || is_gimple_min_invariant (tem
)))
3324 /* If that didn't work try combining multiple statements. */
3325 switch (TREE_CODE_CLASS (code
))
3328 /* Fallthrough for some unary codes that can operate on registers. */
3329 if (!(code
== REALPART_EXPR
3330 || code
== IMAGPART_EXPR
3331 || code
== VIEW_CONVERT_EXPR
3332 || code
== BIT_FIELD_REF
))
3334 /* We could do a little more with unary ops, if they expand
3335 into binary ops, but it's debatable whether it is worth it. */
3337 return simplify_unary_expression (stmt
);
3339 case tcc_comparison
:
3341 return simplify_binary_expression (stmt
);
3350 /* Visit and value number USE, return true if the value number
3354 visit_use (tree use
)
3356 bool changed
= false;
3357 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3359 mark_use_processed (use
);
3361 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3362 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3363 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3365 fprintf (dump_file
, "Value numbering ");
3366 print_generic_expr (dump_file
, use
, 0);
3367 fprintf (dump_file
, " stmt = ");
3368 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3371 /* Handle uninitialized uses. */
3372 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3373 changed
= set_ssa_val_to (use
, use
);
3376 if (gimple_code (stmt
) == GIMPLE_PHI
)
3377 changed
= visit_phi (stmt
);
3378 else if (gimple_has_volatile_ops (stmt
))
3379 changed
= defs_to_varying (stmt
);
3380 else if (is_gimple_assign (stmt
))
3382 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3383 tree lhs
= gimple_assign_lhs (stmt
);
3384 tree rhs1
= gimple_assign_rhs1 (stmt
);
3387 /* Shortcut for copies. Simplifying copies is pointless,
3388 since we copy the expression and value they represent. */
3389 if (code
== SSA_NAME
3390 && TREE_CODE (lhs
) == SSA_NAME
)
3392 changed
= visit_copy (lhs
, rhs1
);
3395 simplified
= try_to_simplify (stmt
);
3398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3400 fprintf (dump_file
, "RHS ");
3401 print_gimple_expr (dump_file
, stmt
, 0, 0);
3402 fprintf (dump_file
, " simplified to ");
3403 print_generic_expr (dump_file
, simplified
, 0);
3404 if (TREE_CODE (lhs
) == SSA_NAME
)
3405 fprintf (dump_file
, " has constants %d\n",
3406 expr_has_constants (simplified
));
3408 fprintf (dump_file
, "\n");
3411 /* Setting value numbers to constants will occasionally
3412 screw up phi congruence because constants are not
3413 uniquely associated with a single ssa name that can be
3416 && is_gimple_min_invariant (simplified
)
3417 && TREE_CODE (lhs
) == SSA_NAME
)
3419 VN_INFO (lhs
)->expr
= simplified
;
3420 VN_INFO (lhs
)->has_constants
= true;
3421 changed
= set_ssa_val_to (lhs
, simplified
);
3425 && TREE_CODE (simplified
) == SSA_NAME
3426 && TREE_CODE (lhs
) == SSA_NAME
)
3428 changed
= visit_copy (lhs
, simplified
);
3431 else if (simplified
)
3433 if (TREE_CODE (lhs
) == SSA_NAME
)
3435 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3436 /* We have to unshare the expression or else
3437 valuizing may change the IL stream. */
3438 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3441 else if (stmt_has_constants (stmt
)
3442 && TREE_CODE (lhs
) == SSA_NAME
)
3443 VN_INFO (lhs
)->has_constants
= true;
3444 else if (TREE_CODE (lhs
) == SSA_NAME
)
3446 /* We reset expr and constantness here because we may
3447 have been value numbering optimistically, and
3448 iterating. They may become non-constant in this case,
3449 even if they were optimistically constant. */
3451 VN_INFO (lhs
)->has_constants
= false;
3452 VN_INFO (lhs
)->expr
= NULL_TREE
;
3455 if ((TREE_CODE (lhs
) == SSA_NAME
3456 /* We can substitute SSA_NAMEs that are live over
3457 abnormal edges with their constant value. */
3458 && !(gimple_assign_copy_p (stmt
)
3459 && is_gimple_min_invariant (rhs1
))
3461 && is_gimple_min_invariant (simplified
))
3462 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3463 /* Stores or copies from SSA_NAMEs that are live over
3464 abnormal edges are a problem. */
3465 || (code
== SSA_NAME
3466 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3467 changed
= defs_to_varying (stmt
);
3468 else if (REFERENCE_CLASS_P (lhs
)
3470 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3471 else if (TREE_CODE (lhs
) == SSA_NAME
)
3473 if ((gimple_assign_copy_p (stmt
)
3474 && is_gimple_min_invariant (rhs1
))
3476 && is_gimple_min_invariant (simplified
)))
3478 VN_INFO (lhs
)->has_constants
= true;
3480 changed
= set_ssa_val_to (lhs
, simplified
);
3482 changed
= set_ssa_val_to (lhs
, rhs1
);
3486 /* First try to lookup the simplified expression. */
3489 enum gimple_rhs_class rhs_class
;
3492 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3493 if ((rhs_class
== GIMPLE_UNARY_RHS
3494 || rhs_class
== GIMPLE_BINARY_RHS
3495 || rhs_class
== GIMPLE_TERNARY_RHS
)
3496 && valid_gimple_rhs_p (simplified
))
3498 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3501 changed
= set_ssa_val_to (lhs
, result
);
3507 /* Otherwise visit the original statement. */
3508 switch (vn_get_stmt_kind (stmt
))
3511 changed
= visit_nary_op (lhs
, stmt
);
3514 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3517 changed
= defs_to_varying (stmt
);
3523 changed
= defs_to_varying (stmt
);
3525 else if (is_gimple_call (stmt
))
3527 tree lhs
= gimple_call_lhs (stmt
);
3529 /* ??? We could try to simplify calls. */
3531 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3533 if (stmt_has_constants (stmt
))
3534 VN_INFO (lhs
)->has_constants
= true;
3537 /* We reset expr and constantness here because we may
3538 have been value numbering optimistically, and
3539 iterating. They may become non-constant in this case,
3540 even if they were optimistically constant. */
3541 VN_INFO (lhs
)->has_constants
= false;
3542 VN_INFO (lhs
)->expr
= NULL_TREE
;
3545 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3547 changed
= defs_to_varying (stmt
);
3552 if (!gimple_call_internal_p (stmt
)
3553 && (/* Calls to the same function with the same vuse
3554 and the same operands do not necessarily return the same
3555 value, unless they're pure or const. */
3556 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3557 /* If calls have a vdef, subsequent calls won't have
3558 the same incoming vuse. So, if 2 calls with vdef have the
3559 same vuse, we know they're not subsequent.
3560 We can value number 2 calls to the same function with the
3561 same vuse and the same operands which are not subsequent
3562 the same, because there is no code in the program that can
3563 compare the 2 values... */
3564 || (gimple_vdef (stmt
)
3565 /* ... unless the call returns a pointer which does
3566 not alias with anything else. In which case the
3567 information that the values are distinct are encoded
3569 && !(gimple_call_return_flags (stmt
) & ERF_NOALIAS
))))
3570 changed
= visit_reference_op_call (lhs
, stmt
);
3572 changed
= defs_to_varying (stmt
);
3575 changed
= defs_to_varying (stmt
);
3581 /* Compare two operands by reverse postorder index */
3584 compare_ops (const void *pa
, const void *pb
)
3586 const tree opa
= *((const tree
*)pa
);
3587 const tree opb
= *((const tree
*)pb
);
3588 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3589 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3593 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3594 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3595 else if (gimple_nop_p (opstmta
))
3597 else if (gimple_nop_p (opstmtb
))
3600 bba
= gimple_bb (opstmta
);
3601 bbb
= gimple_bb (opstmtb
);
3604 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3612 if (gimple_code (opstmta
) == GIMPLE_PHI
3613 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3614 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3615 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3617 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3619 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3620 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3622 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3624 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3627 /* Sort an array containing members of a strongly connected component
3628 SCC so that the members are ordered by RPO number.
3629 This means that when the sort is complete, iterating through the
3630 array will give you the members in RPO order. */
3633 sort_scc (vec
<tree
> scc
)
3635 scc
.qsort (compare_ops
);
3638 /* Insert the no longer used nary ONARY to the hash INFO. */
3641 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3643 size_t size
= sizeof_vn_nary_op (onary
->length
);
3644 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3645 &info
->nary_obstack
);
3646 memcpy (nary
, onary
, size
);
3647 vn_nary_op_insert_into (nary
, info
->nary
, false);
3650 /* Insert the no longer used phi OPHI to the hash INFO. */
3653 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3655 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3657 memcpy (phi
, ophi
, sizeof (*phi
));
3658 ophi
->phiargs
.create (0);
3659 slot
= info
->phis
.find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3660 gcc_assert (!*slot
);
3664 /* Insert the no longer used reference OREF to the hash INFO. */
3667 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3670 vn_reference_s
**slot
;
3671 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3672 memcpy (ref
, oref
, sizeof (*ref
));
3673 oref
->operands
.create (0);
3674 slot
= info
->references
.find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3676 free_reference (*slot
);
3680 /* Process a strongly connected component in the SSA graph. */
3683 process_scc (vec
<tree
> scc
)
3687 unsigned int iterations
= 0;
3688 bool changed
= true;
3689 vn_nary_op_iterator_type hin
;
3690 vn_phi_iterator_type hip
;
3691 vn_reference_iterator_type hir
;
3696 /* If the SCC has a single member, just visit it. */
3697 if (scc
.length () == 1)
3700 if (VN_INFO (use
)->use_processed
)
3702 /* We need to make sure it doesn't form a cycle itself, which can
3703 happen for self-referential PHI nodes. In that case we would
3704 end up inserting an expression with VN_TOP operands into the
3705 valid table which makes us derive bogus equivalences later.
3706 The cheapest way to check this is to assume it for all PHI nodes. */
3707 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3708 /* Fallthru to iteration. */ ;
3716 /* Iterate over the SCC with the optimistic table until it stops
3718 current_info
= optimistic_info
;
3723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3724 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3725 /* As we are value-numbering optimistically we have to
3726 clear the expression tables and the simplified expressions
3727 in each iteration until we converge. */
3728 optimistic_info
->nary
.empty ();
3729 optimistic_info
->phis
.empty ();
3730 optimistic_info
->references
.empty ();
3731 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3732 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3733 empty_alloc_pool (optimistic_info
->phis_pool
);
3734 empty_alloc_pool (optimistic_info
->references_pool
);
3735 FOR_EACH_VEC_ELT (scc
, i
, var
)
3736 VN_INFO (var
)->expr
= NULL_TREE
;
3737 FOR_EACH_VEC_ELT (scc
, i
, var
)
3738 changed
|= visit_use (var
);
3741 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3743 /* Finally, copy the contents of the no longer used optimistic
3744 table to the valid table. */
3745 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3746 copy_nary (nary
, valid_info
);
3747 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3748 copy_phi (phi
, valid_info
);
3749 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->references
,
3750 ref
, vn_reference_t
, hir
)
3751 copy_reference (ref
, valid_info
);
3753 current_info
= valid_info
;
3757 /* Pop the components of the found SCC for NAME off the SCC stack
3758 and process them. Returns true if all went well, false if
3759 we run into resource limits. */
3762 extract_and_process_scc_for_name (tree name
)
3764 vec
<tree
> scc
= vNULL
;
3767 /* Found an SCC, pop the components off the SCC stack and
3771 x
= sccstack
.pop ();
3773 VN_INFO (x
)->on_sccstack
= false;
3775 } while (x
!= name
);
3777 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3779 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3782 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3783 "SCC size %u exceeding %u\n", scc
.length (),
3784 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3790 if (scc
.length () > 1)
3793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3794 print_scc (dump_file
, scc
);
3803 /* Depth first search on NAME to discover and process SCC's in the SSA
3805 Execution of this algorithm relies on the fact that the SCC's are
3806 popped off the stack in topological order.
3807 Returns true if successful, false if we stopped processing SCC's due
3808 to resource constraints. */
3813 vec
<ssa_op_iter
> itervec
= vNULL
;
3814 vec
<tree
> namevec
= vNULL
;
3815 use_operand_p usep
= NULL
;
3822 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3823 VN_INFO (name
)->visited
= true;
3824 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3826 sccstack
.safe_push (name
);
3827 VN_INFO (name
)->on_sccstack
= true;
3828 defstmt
= SSA_NAME_DEF_STMT (name
);
3830 /* Recursively DFS on our operands, looking for SCC's. */
3831 if (!gimple_nop_p (defstmt
))
3833 /* Push a new iterator. */
3834 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3835 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3837 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3840 clear_and_done_ssa_iter (&iter
);
3844 /* If we are done processing uses of a name, go up the stack
3845 of iterators and process SCCs as we found them. */
3846 if (op_iter_done (&iter
))
3848 /* See if we found an SCC. */
3849 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3850 if (!extract_and_process_scc_for_name (name
))
3857 /* Check if we are done. */
3858 if (namevec
.is_empty ())
3865 /* Restore the last use walker and continue walking there. */
3867 name
= namevec
.pop ();
3868 memcpy (&iter
, &itervec
.last (),
3869 sizeof (ssa_op_iter
));
3871 goto continue_walking
;
3874 use
= USE_FROM_PTR (usep
);
3876 /* Since we handle phi nodes, we will sometimes get
3877 invariants in the use expression. */
3878 if (TREE_CODE (use
) == SSA_NAME
)
3880 if (! (VN_INFO (use
)->visited
))
3882 /* Recurse by pushing the current use walking state on
3883 the stack and starting over. */
3884 itervec
.safe_push (iter
);
3885 namevec
.safe_push (name
);
3890 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3891 VN_INFO (use
)->low
);
3893 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3894 && VN_INFO (use
)->on_sccstack
)
3896 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3897 VN_INFO (name
)->low
);
3901 usep
= op_iter_next_use (&iter
);
3905 /* Allocate a value number table. */
3908 allocate_vn_table (vn_tables_t table
)
3910 table
->phis
.create (23);
3911 table
->nary
.create (23);
3912 table
->references
.create (23);
3914 gcc_obstack_init (&table
->nary_obstack
);
3915 table
->phis_pool
= create_alloc_pool ("VN phis",
3916 sizeof (struct vn_phi_s
),
3918 table
->references_pool
= create_alloc_pool ("VN references",
3919 sizeof (struct vn_reference_s
),
3923 /* Free a value number table. */
3926 free_vn_table (vn_tables_t table
)
3928 table
->phis
.dispose ();
3929 table
->nary
.dispose ();
3930 table
->references
.dispose ();
3931 obstack_free (&table
->nary_obstack
, NULL
);
3932 free_alloc_pool (table
->phis_pool
);
3933 free_alloc_pool (table
->references_pool
);
3941 int *rpo_numbers_temp
;
3943 calculate_dominance_info (CDI_DOMINATORS
);
3944 sccstack
.create (0);
3945 constant_to_value_id
.create (23);
3947 constant_value_ids
= BITMAP_ALLOC (NULL
);
3952 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
3953 /* VEC_alloc doesn't actually grow it to the right size, it just
3954 preallocates the space to do so. */
3955 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
3956 gcc_obstack_init (&vn_ssa_aux_obstack
);
3958 shared_lookup_phiargs
.create (0);
3959 shared_lookup_references
.create (0);
3960 rpo_numbers
= XNEWVEC (int, last_basic_block
);
3961 rpo_numbers_temp
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3962 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
3964 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3965 the i'th block in RPO order is bb. We want to map bb's to RPO
3966 numbers, so we need to rearrange this array. */
3967 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
3968 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
3970 XDELETE (rpo_numbers_temp
);
3972 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
3974 /* Create the VN_INFO structures, and initialize value numbers to
3976 for (i
= 0; i
< num_ssa_names
; i
++)
3978 tree name
= ssa_name (i
);
3981 VN_INFO_GET (name
)->valnum
= VN_TOP
;
3982 VN_INFO (name
)->expr
= NULL_TREE
;
3983 VN_INFO (name
)->value_id
= 0;
3987 renumber_gimple_stmt_uids ();
3989 /* Create the valid and optimistic value numbering tables. */
3990 valid_info
= XCNEW (struct vn_tables_s
);
3991 allocate_vn_table (valid_info
);
3992 optimistic_info
= XCNEW (struct vn_tables_s
);
3993 allocate_vn_table (optimistic_info
);
4001 constant_to_value_id
.dispose ();
4002 BITMAP_FREE (constant_value_ids
);
4003 shared_lookup_phiargs
.release ();
4004 shared_lookup_references
.release ();
4005 XDELETEVEC (rpo_numbers
);
4007 for (i
= 0; i
< num_ssa_names
; i
++)
4009 tree name
= ssa_name (i
);
4011 && VN_INFO (name
)->needs_insertion
)
4012 release_ssa_name (name
);
4014 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4015 vn_ssa_aux_table
.release ();
4017 sccstack
.release ();
4018 free_vn_table (valid_info
);
4019 XDELETE (valid_info
);
4020 free_vn_table (optimistic_info
);
4021 XDELETE (optimistic_info
);
4024 /* Set *ID according to RESULT. */
4027 set_value_id_for_result (tree result
, unsigned int *id
)
4029 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4030 *id
= VN_INFO (result
)->value_id
;
4031 else if (result
&& is_gimple_min_invariant (result
))
4032 *id
= get_or_alloc_constant_value_id (result
);
4034 *id
= get_next_value_id ();
4037 /* Set the value ids in the valid hash tables. */
4040 set_hashtable_value_ids (void)
4042 vn_nary_op_iterator_type hin
;
4043 vn_phi_iterator_type hip
;
4044 vn_reference_iterator_type hir
;
4049 /* Now set the value ids of the things we had put in the hash
4052 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4053 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4055 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->phis
, vp
, vn_phi_t
, hip
)
4056 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4058 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->references
, vr
, vn_reference_t
, hir
)
4059 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4062 /* Do SCCVN. Returns true if it finished, false if we bailed out
4063 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4064 how we use the alias oracle walking during the VN process. */
4067 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4072 default_vn_walk_kind
= default_vn_walk_kind_
;
4075 current_info
= valid_info
;
4077 for (param
= DECL_ARGUMENTS (current_function_decl
);
4079 param
= DECL_CHAIN (param
))
4081 tree def
= ssa_default_def (cfun
, param
);
4083 VN_INFO (def
)->valnum
= def
;
4086 for (i
= 1; i
< num_ssa_names
; ++i
)
4088 tree name
= ssa_name (i
);
4090 && VN_INFO (name
)->visited
== false
4091 && !has_zero_uses (name
))
4099 /* Initialize the value ids. */
4101 for (i
= 1; i
< num_ssa_names
; ++i
)
4103 tree name
= ssa_name (i
);
4107 info
= VN_INFO (name
);
4108 if (info
->valnum
== name
4109 || info
->valnum
== VN_TOP
)
4110 info
->value_id
= get_next_value_id ();
4111 else if (is_gimple_min_invariant (info
->valnum
))
4112 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4116 for (i
= 1; i
< num_ssa_names
; ++i
)
4118 tree name
= ssa_name (i
);
4122 info
= VN_INFO (name
);
4123 if (TREE_CODE (info
->valnum
) == SSA_NAME
4124 && info
->valnum
!= name
4125 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4126 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4129 set_hashtable_value_ids ();
4131 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4133 fprintf (dump_file
, "Value numbers:\n");
4134 for (i
= 0; i
< num_ssa_names
; i
++)
4136 tree name
= ssa_name (i
);
4138 && VN_INFO (name
)->visited
4139 && SSA_VAL (name
) != name
)
4141 print_generic_expr (dump_file
, name
, 0);
4142 fprintf (dump_file
, " = ");
4143 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4144 fprintf (dump_file
, "\n");
4152 /* Return the maximum value id we have ever seen. */
4155 get_max_value_id (void)
4157 return next_value_id
;
4160 /* Return the next unique value id. */
4163 get_next_value_id (void)
4165 return next_value_id
++;
4169 /* Compare two expressions E1 and E2 and return true if they are equal. */
4172 expressions_equal_p (tree e1
, tree e2
)
4174 /* The obvious case. */
4178 /* If only one of them is null, they cannot be equal. */
4182 /* Now perform the actual comparison. */
4183 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4184 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4191 /* Return true if the nary operation NARY may trap. This is a copy
4192 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4195 vn_nary_may_trap (vn_nary_op_t nary
)
4198 tree rhs2
= NULL_TREE
;
4199 bool honor_nans
= false;
4200 bool honor_snans
= false;
4201 bool fp_operation
= false;
4202 bool honor_trapv
= false;
4206 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4207 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4208 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4211 fp_operation
= FLOAT_TYPE_P (type
);
4214 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4215 honor_snans
= flag_signaling_nans
!= 0;
4217 else if (INTEGRAL_TYPE_P (type
)
4218 && TYPE_OVERFLOW_TRAPS (type
))
4221 if (nary
->length
>= 2)
4223 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4225 honor_nans
, honor_snans
, rhs2
,
4231 for (i
= 0; i
< nary
->length
; ++i
)
4232 if (tree_could_trap_p (nary
->op
[i
]))