1 /* SCC value numbering for trees
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "stor-layout.h"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "tree-inline.h"
30 #include "hash-table.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-fold.h"
35 #include "gimple-expr.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "stringpool.h"
43 #include "tree-ssanames.h"
48 #include "alloc-pool.h"
52 #include "tree-ssa-propagate.h"
53 #include "tree-ssa-sccvn.h"
55 /* This algorithm is based on the SCC algorithm presented by Keith
56 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
57 (http://citeseer.ist.psu.edu/41805.html). In
58 straight line code, it is equivalent to a regular hash based value
59 numbering that is performed in reverse postorder.
61 For code with cycles, there are two alternatives, both of which
62 require keeping the hashtables separate from the actual list of
63 value numbers for SSA names.
65 1. Iterate value numbering in an RPO walk of the blocks, removing
66 all the entries from the hashtable after each iteration (but
67 keeping the SSA name->value number mapping between iterations).
68 Iterate until it does not change.
70 2. Perform value numbering as part of an SCC walk on the SSA graph,
71 iterating only the cycles in the SSA graph until they do not change
72 (using a separate, optimistic hashtable for value numbering the SCC
75 The second is not just faster in practice (because most SSA graph
76 cycles do not involve all the variables in the graph), it also has
79 One of these nice properties is that when we pop an SCC off the
80 stack, we are guaranteed to have processed all the operands coming from
81 *outside of that SCC*, so we do not need to do anything special to
82 ensure they have value numbers.
84 Another nice property is that the SCC walk is done as part of a DFS
85 of the SSA graph, which makes it easy to perform combining and
86 simplifying operations at the same time.
88 The code below is deliberately written in a way that makes it easy
89 to separate the SCC walk from the other work it does.
91 In order to propagate constants through the code, we track which
92 expressions contain constants, and use those while folding. In
93 theory, we could also track expressions whose value numbers are
94 replaced, in case we end up folding based on expression
97 In order to value number memory, we assign value numbers to vuses.
98 This enables us to note that, for example, stores to the same
99 address of the same value from the same starting memory states are
103 1. We can iterate only the changing portions of the SCC's, but
104 I have not seen an SCC big enough for this to be a win.
105 2. If you differentiate between phi nodes for loops and phi nodes
106 for if-then-else, you can properly consider phi nodes in different
107 blocks for equivalence.
108 3. We could value number vuses in more cases, particularly, whole
113 /* vn_nary_op hashtable helpers. */
115 struct vn_nary_op_hasher
: typed_noop_remove
<vn_nary_op_s
>
117 typedef vn_nary_op_s value_type
;
118 typedef vn_nary_op_s compare_type
;
119 static inline hashval_t
hash (const value_type
*);
120 static inline bool equal (const value_type
*, const compare_type
*);
123 /* Return the computed hashcode for nary operation P1. */
126 vn_nary_op_hasher::hash (const value_type
*vno1
)
128 return vno1
->hashcode
;
131 /* Compare nary operations P1 and P2 and return true if they are
135 vn_nary_op_hasher::equal (const value_type
*vno1
, const compare_type
*vno2
)
137 return vn_nary_op_eq (vno1
, vno2
);
140 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
141 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
144 /* vn_phi hashtable helpers. */
147 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
151 typedef vn_phi_s value_type
;
152 typedef vn_phi_s compare_type
;
153 static inline hashval_t
hash (const value_type
*);
154 static inline bool equal (const value_type
*, const compare_type
*);
155 static inline void remove (value_type
*);
158 /* Return the computed hashcode for phi operation P1. */
161 vn_phi_hasher::hash (const value_type
*vp1
)
163 return vp1
->hashcode
;
166 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
169 vn_phi_hasher::equal (const value_type
*vp1
, const compare_type
*vp2
)
171 return vn_phi_eq (vp1
, vp2
);
174 /* Free a phi operation structure VP. */
177 vn_phi_hasher::remove (value_type
*phi
)
179 phi
->phiargs
.release ();
182 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
183 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
186 /* Compare two reference operands P1 and P2 for equality. Return true if
187 they are equal, and false otherwise. */
190 vn_reference_op_eq (const void *p1
, const void *p2
)
192 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
193 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
195 return (vro1
->opcode
== vro2
->opcode
196 /* We do not care for differences in type qualification. */
197 && (vro1
->type
== vro2
->type
198 || (vro1
->type
&& vro2
->type
199 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
200 TYPE_MAIN_VARIANT (vro2
->type
))))
201 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
202 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
203 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
206 /* Free a reference operation structure VP. */
209 free_reference (vn_reference_s
*vr
)
211 vr
->operands
.release ();
215 /* vn_reference hashtable helpers. */
217 struct vn_reference_hasher
219 typedef vn_reference_s value_type
;
220 typedef vn_reference_s compare_type
;
221 static inline hashval_t
hash (const value_type
*);
222 static inline bool equal (const value_type
*, const compare_type
*);
223 static inline void remove (value_type
*);
226 /* Return the hashcode for a given reference operation P1. */
229 vn_reference_hasher::hash (const value_type
*vr1
)
231 return vr1
->hashcode
;
235 vn_reference_hasher::equal (const value_type
*v
, const compare_type
*c
)
237 return vn_reference_eq (v
, c
);
241 vn_reference_hasher::remove (value_type
*v
)
246 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
247 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
250 /* The set of hashtables and alloc_pool's for their items. */
252 typedef struct vn_tables_s
254 vn_nary_op_table_type nary
;
255 vn_phi_table_type phis
;
256 vn_reference_table_type references
;
257 struct obstack nary_obstack
;
258 alloc_pool phis_pool
;
259 alloc_pool references_pool
;
263 /* vn_constant hashtable helpers. */
265 struct vn_constant_hasher
: typed_free_remove
<vn_constant_s
>
267 typedef vn_constant_s value_type
;
268 typedef vn_constant_s compare_type
;
269 static inline hashval_t
hash (const value_type
*);
270 static inline bool equal (const value_type
*, const compare_type
*);
273 /* Hash table hash function for vn_constant_t. */
276 vn_constant_hasher::hash (const value_type
*vc1
)
278 return vc1
->hashcode
;
281 /* Hash table equality function for vn_constant_t. */
284 vn_constant_hasher::equal (const value_type
*vc1
, const compare_type
*vc2
)
286 if (vc1
->hashcode
!= vc2
->hashcode
)
289 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
292 static hash_table
<vn_constant_hasher
> constant_to_value_id
;
293 static bitmap constant_value_ids
;
296 /* Valid hashtables storing information we have proven to be
299 static vn_tables_t valid_info
;
301 /* Optimistic hashtables storing information we are making assumptions about
302 during iterations. */
304 static vn_tables_t optimistic_info
;
306 /* Pointer to the set of hashtables that is currently being used.
307 Should always point to either the optimistic_info, or the
310 static vn_tables_t current_info
;
313 /* Reverse post order index for each basic block. */
315 static int *rpo_numbers
;
317 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
319 /* This represents the top of the VN lattice, which is the universal
324 /* Unique counter for our value ids. */
326 static unsigned int next_value_id
;
328 /* Next DFS number and the stack for strongly connected component
331 static unsigned int next_dfs_num
;
332 static vec
<tree
> sccstack
;
336 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
337 are allocated on an obstack for locality reasons, and to free them
338 without looping over the vec. */
340 static vec
<vn_ssa_aux_t
> vn_ssa_aux_table
;
341 static struct obstack vn_ssa_aux_obstack
;
343 /* Return the value numbering information for a given SSA name. */
348 vn_ssa_aux_t res
= vn_ssa_aux_table
[SSA_NAME_VERSION (name
)];
349 gcc_checking_assert (res
);
353 /* Set the value numbering info for a given SSA name to a given
357 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
359 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = value
;
362 /* Initialize the value numbering info for a given SSA name.
363 This should be called just once for every SSA name. */
366 VN_INFO_GET (tree name
)
368 vn_ssa_aux_t newinfo
;
370 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
371 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
372 if (SSA_NAME_VERSION (name
) >= vn_ssa_aux_table
.length ())
373 vn_ssa_aux_table
.safe_grow (SSA_NAME_VERSION (name
) + 1);
374 vn_ssa_aux_table
[SSA_NAME_VERSION (name
)] = newinfo
;
379 /* Get the representative expression for the SSA_NAME NAME. Returns
380 the representative SSA_NAME if there is no expression associated with it. */
383 vn_get_expr_for (tree name
)
385 vn_ssa_aux_t vn
= VN_INFO (name
);
387 tree expr
= NULL_TREE
;
390 if (vn
->valnum
== VN_TOP
)
393 /* If the value-number is a constant it is the representative
395 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
398 /* Get to the information of the value of this SSA_NAME. */
399 vn
= VN_INFO (vn
->valnum
);
401 /* If the value-number is a constant it is the representative
403 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
406 /* Else if we have an expression, return it. */
407 if (vn
->expr
!= NULL_TREE
)
410 /* Otherwise use the defining statement to build the expression. */
411 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
413 /* If the value number is not an assignment use it directly. */
414 if (!is_gimple_assign (def_stmt
))
417 /* FIXME tuples. This is incomplete and likely will miss some
419 code
= gimple_assign_rhs_code (def_stmt
);
420 switch (TREE_CODE_CLASS (code
))
423 if ((code
== REALPART_EXPR
424 || code
== IMAGPART_EXPR
425 || code
== VIEW_CONVERT_EXPR
)
426 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt
),
428 expr
= fold_build1 (code
,
429 gimple_expr_type (def_stmt
),
430 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
434 expr
= fold_build1 (code
,
435 gimple_expr_type (def_stmt
),
436 gimple_assign_rhs1 (def_stmt
));
440 expr
= fold_build2 (code
,
441 gimple_expr_type (def_stmt
),
442 gimple_assign_rhs1 (def_stmt
),
443 gimple_assign_rhs2 (def_stmt
));
446 case tcc_exceptional
:
447 if (code
== CONSTRUCTOR
449 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))) == VECTOR_TYPE
)
450 expr
= gimple_assign_rhs1 (def_stmt
);
455 if (expr
== NULL_TREE
)
458 /* Cache the expression. */
464 /* Return the vn_kind the expression computed by the stmt should be
468 vn_get_stmt_kind (gimple stmt
)
470 switch (gimple_code (stmt
))
478 enum tree_code code
= gimple_assign_rhs_code (stmt
);
479 tree rhs1
= gimple_assign_rhs1 (stmt
);
480 switch (get_gimple_rhs_class (code
))
482 case GIMPLE_UNARY_RHS
:
483 case GIMPLE_BINARY_RHS
:
484 case GIMPLE_TERNARY_RHS
:
486 case GIMPLE_SINGLE_RHS
:
487 switch (TREE_CODE_CLASS (code
))
490 /* VOP-less references can go through unary case. */
491 if ((code
== REALPART_EXPR
492 || code
== IMAGPART_EXPR
493 || code
== VIEW_CONVERT_EXPR
494 || code
== BIT_FIELD_REF
)
495 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
499 case tcc_declaration
:
506 if (code
== ADDR_EXPR
)
507 return (is_gimple_min_invariant (rhs1
)
508 ? VN_CONSTANT
: VN_REFERENCE
);
509 else if (code
== CONSTRUCTOR
)
522 /* Lookup a value id for CONSTANT and return it. If it does not
526 get_constant_value_id (tree constant
)
528 vn_constant_s
**slot
;
529 struct vn_constant_s vc
;
531 vc
.hashcode
= vn_hash_constant_with_type (constant
);
532 vc
.constant
= constant
;
533 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, NO_INSERT
);
535 return (*slot
)->value_id
;
539 /* Lookup a value id for CONSTANT, and if it does not exist, create a
540 new one and return it. If it does exist, return it. */
543 get_or_alloc_constant_value_id (tree constant
)
545 vn_constant_s
**slot
;
546 struct vn_constant_s vc
;
549 vc
.hashcode
= vn_hash_constant_with_type (constant
);
550 vc
.constant
= constant
;
551 slot
= constant_to_value_id
.find_slot_with_hash (&vc
, vc
.hashcode
, INSERT
);
553 return (*slot
)->value_id
;
555 vcp
= XNEW (struct vn_constant_s
);
556 vcp
->hashcode
= vc
.hashcode
;
557 vcp
->constant
= constant
;
558 vcp
->value_id
= get_next_value_id ();
560 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
561 return vcp
->value_id
;
564 /* Return true if V is a value id for a constant. */
567 value_id_constant_p (unsigned int v
)
569 return bitmap_bit_p (constant_value_ids
, v
);
572 /* Compute the hash for a reference operand VRO1. */
575 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
577 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
579 result
= iterative_hash_expr (vro1
->op0
, result
);
581 result
= iterative_hash_expr (vro1
->op1
, result
);
583 result
= iterative_hash_expr (vro1
->op2
, result
);
587 /* Compute a hash for the reference operation VR1 and return it. */
590 vn_reference_compute_hash (const vn_reference_t vr1
)
592 hashval_t result
= 0;
594 vn_reference_op_t vro
;
595 HOST_WIDE_INT off
= -1;
598 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
600 if (vro
->opcode
== MEM_REF
)
602 else if (vro
->opcode
!= ADDR_EXPR
)
614 result
= iterative_hash_hashval_t (off
, result
);
617 && vro
->opcode
== ADDR_EXPR
)
621 tree op
= TREE_OPERAND (vro
->op0
, 0);
622 result
= iterative_hash_hashval_t (TREE_CODE (op
), result
);
623 result
= iterative_hash_expr (op
, result
);
627 result
= vn_reference_op_compute_hash (vro
, result
);
631 result
+= SSA_NAME_VERSION (vr1
->vuse
);
636 /* Return true if reference operations VR1 and VR2 are equivalent. This
637 means they have the same set of operands and vuses. */
640 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
644 if (vr1
->hashcode
!= vr2
->hashcode
)
647 /* Early out if this is not a hash collision. */
648 if (vr1
->hashcode
!= vr2
->hashcode
)
651 /* The VOP needs to be the same. */
652 if (vr1
->vuse
!= vr2
->vuse
)
655 /* If the operands are the same we are done. */
656 if (vr1
->operands
== vr2
->operands
)
659 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
662 if (INTEGRAL_TYPE_P (vr1
->type
)
663 && INTEGRAL_TYPE_P (vr2
->type
))
665 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
668 else if (INTEGRAL_TYPE_P (vr1
->type
)
669 && (TYPE_PRECISION (vr1
->type
)
670 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
672 else if (INTEGRAL_TYPE_P (vr2
->type
)
673 && (TYPE_PRECISION (vr2
->type
)
674 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
681 HOST_WIDE_INT off1
= 0, off2
= 0;
682 vn_reference_op_t vro1
, vro2
;
683 vn_reference_op_s tem1
, tem2
;
684 bool deref1
= false, deref2
= false;
685 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
687 if (vro1
->opcode
== MEM_REF
)
693 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
695 if (vro2
->opcode
== MEM_REF
)
703 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
705 memset (&tem1
, 0, sizeof (tem1
));
706 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
707 tem1
.type
= TREE_TYPE (tem1
.op0
);
708 tem1
.opcode
= TREE_CODE (tem1
.op0
);
712 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
714 memset (&tem2
, 0, sizeof (tem2
));
715 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
716 tem2
.type
= TREE_TYPE (tem2
.op0
);
717 tem2
.opcode
= TREE_CODE (tem2
.op0
);
721 if (deref1
!= deref2
)
723 if (!vn_reference_op_eq (vro1
, vro2
))
728 while (vr1
->operands
.length () != i
729 || vr2
->operands
.length () != j
);
734 /* Copy the operations present in load/store REF into RESULT, a vector of
735 vn_reference_op_s's. */
738 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
740 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
742 vn_reference_op_s temp
;
746 memset (&temp
, 0, sizeof (temp
));
747 temp
.type
= TREE_TYPE (ref
);
748 temp
.opcode
= TREE_CODE (ref
);
749 temp
.op0
= TMR_INDEX (ref
);
750 temp
.op1
= TMR_STEP (ref
);
751 temp
.op2
= TMR_OFFSET (ref
);
753 result
->quick_push (temp
);
755 memset (&temp
, 0, sizeof (temp
));
756 temp
.type
= NULL_TREE
;
757 temp
.opcode
= ERROR_MARK
;
758 temp
.op0
= TMR_INDEX2 (ref
);
760 result
->quick_push (temp
);
762 memset (&temp
, 0, sizeof (temp
));
763 temp
.type
= NULL_TREE
;
764 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
765 temp
.op0
= TMR_BASE (ref
);
767 result
->quick_push (temp
);
771 /* For non-calls, store the information that makes up the address. */
775 vn_reference_op_s temp
;
777 memset (&temp
, 0, sizeof (temp
));
778 temp
.type
= TREE_TYPE (ref
);
779 temp
.opcode
= TREE_CODE (ref
);
785 temp
.op0
= TREE_OPERAND (ref
, 1);
788 temp
.op0
= TREE_OPERAND (ref
, 1);
792 /* The base address gets its own vn_reference_op_s structure. */
793 temp
.op0
= TREE_OPERAND (ref
, 1);
794 if (tree_fits_shwi_p (TREE_OPERAND (ref
, 1)))
795 temp
.off
= tree_to_shwi (TREE_OPERAND (ref
, 1));
798 /* Record bits and position. */
799 temp
.op0
= TREE_OPERAND (ref
, 1);
800 temp
.op1
= TREE_OPERAND (ref
, 2);
803 /* The field decl is enough to unambiguously specify the field,
804 a matching type is not necessary and a mismatching type
805 is always a spurious difference. */
806 temp
.type
= NULL_TREE
;
807 temp
.op0
= TREE_OPERAND (ref
, 1);
808 temp
.op1
= TREE_OPERAND (ref
, 2);
810 tree this_offset
= component_ref_field_offset (ref
);
812 && TREE_CODE (this_offset
) == INTEGER_CST
)
814 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
815 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
818 = (wi::to_offset (this_offset
)
819 + wi::lrshift (wi::to_offset (bit_offset
),
820 LOG2_BITS_PER_UNIT
));
821 if (wi::fits_shwi_p (off
)
822 /* Probibit value-numbering zero offset components
823 of addresses the same before the pass folding
824 __builtin_object_size had a chance to run
825 (checking cfun->after_inlining does the
827 && (TREE_CODE (orig
) != ADDR_EXPR
829 || cfun
->after_inlining
))
830 temp
.off
= off
.to_shwi ();
835 case ARRAY_RANGE_REF
:
837 /* Record index as operand. */
838 temp
.op0
= TREE_OPERAND (ref
, 1);
839 /* Always record lower bounds and element size. */
840 temp
.op1
= array_ref_low_bound (ref
);
841 temp
.op2
= array_ref_element_size (ref
);
842 if (TREE_CODE (temp
.op0
) == INTEGER_CST
843 && TREE_CODE (temp
.op1
) == INTEGER_CST
844 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
846 offset_int off
= ((wi::to_offset (temp
.op0
)
847 - wi::to_offset (temp
.op1
))
848 * wi::to_offset (temp
.op2
));
849 if (wi::fits_shwi_p (off
))
850 temp
.off
= off
.to_shwi();
854 if (DECL_HARD_REGISTER (ref
))
863 /* Canonicalize decls to MEM[&decl] which is what we end up with
864 when valueizing MEM[ptr] with ptr = &decl. */
865 temp
.opcode
= MEM_REF
;
866 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
868 result
->safe_push (temp
);
869 temp
.opcode
= ADDR_EXPR
;
870 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
871 temp
.type
= TREE_TYPE (temp
.op0
);
885 if (is_gimple_min_invariant (ref
))
891 /* These are only interesting for their operands, their
892 existence, and their type. They will never be the last
893 ref in the chain of references (IE they require an
894 operand), so we don't have to put anything
895 for op* as it will be handled by the iteration */
897 case VIEW_CONVERT_EXPR
:
901 /* This is only interesting for its constant offset. */
902 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
907 result
->safe_push (temp
);
909 if (REFERENCE_CLASS_P (ref
)
910 || TREE_CODE (ref
) == MODIFY_EXPR
911 || TREE_CODE (ref
) == WITH_SIZE_EXPR
912 || (TREE_CODE (ref
) == ADDR_EXPR
913 && !is_gimple_min_invariant (ref
)))
914 ref
= TREE_OPERAND (ref
, 0);
920 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
921 operands in *OPS, the reference alias set SET and the reference type TYPE.
922 Return true if something useful was produced. */
925 ao_ref_init_from_vn_reference (ao_ref
*ref
,
926 alias_set_type set
, tree type
,
927 vec
<vn_reference_op_s
> ops
)
929 vn_reference_op_t op
;
931 tree base
= NULL_TREE
;
933 HOST_WIDE_INT offset
= 0;
934 HOST_WIDE_INT max_size
;
935 HOST_WIDE_INT size
= -1;
936 tree size_tree
= NULL_TREE
;
937 alias_set_type base_alias_set
= -1;
939 /* First get the final access size from just the outermost expression. */
941 if (op
->opcode
== COMPONENT_REF
)
942 size_tree
= DECL_SIZE (op
->op0
);
943 else if (op
->opcode
== BIT_FIELD_REF
)
947 enum machine_mode mode
= TYPE_MODE (type
);
949 size_tree
= TYPE_SIZE (type
);
951 size
= GET_MODE_BITSIZE (mode
);
953 if (size_tree
!= NULL_TREE
)
955 if (!tree_fits_uhwi_p (size_tree
))
958 size
= tree_to_uhwi (size_tree
);
961 /* Initially, maxsize is the same as the accessed element size.
962 In the following it will only grow (or become -1). */
965 /* Compute cumulative bit-offset for nested component-refs and array-refs,
966 and find the ultimate containing object. */
967 FOR_EACH_VEC_ELT (ops
, i
, op
)
971 /* These may be in the reference ops, but we cannot do anything
972 sensible with them here. */
974 /* Apart from ADDR_EXPR arguments to MEM_REF. */
975 if (base
!= NULL_TREE
976 && TREE_CODE (base
) == MEM_REF
978 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
980 vn_reference_op_t pop
= &ops
[i
-1];
981 base
= TREE_OPERAND (op
->op0
, 0);
988 offset
+= pop
->off
* BITS_PER_UNIT
;
996 /* Record the base objects. */
998 base_alias_set
= get_deref_alias_set (op
->op0
);
999 *op0_p
= build2 (MEM_REF
, op
->type
,
1000 NULL_TREE
, op
->op0
);
1001 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1012 /* And now the usual component-reference style ops. */
1014 offset
+= tree_to_shwi (op
->op1
);
1019 tree field
= op
->op0
;
1020 /* We do not have a complete COMPONENT_REF tree here so we
1021 cannot use component_ref_field_offset. Do the interesting
1025 || !tree_fits_uhwi_p (DECL_FIELD_OFFSET (field
)))
1029 offset
+= (tree_to_uhwi (DECL_FIELD_OFFSET (field
))
1031 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
1036 case ARRAY_RANGE_REF
:
1038 /* We recorded the lower bound and the element size. */
1039 if (!tree_fits_shwi_p (op
->op0
)
1040 || !tree_fits_shwi_p (op
->op1
)
1041 || !tree_fits_shwi_p (op
->op2
))
1045 HOST_WIDE_INT hindex
= tree_to_shwi (op
->op0
);
1046 hindex
-= tree_to_shwi (op
->op1
);
1047 hindex
*= tree_to_shwi (op
->op2
);
1048 hindex
*= BITS_PER_UNIT
;
1060 case VIEW_CONVERT_EXPR
:
1077 if (base
== NULL_TREE
)
1080 ref
->ref
= NULL_TREE
;
1082 ref
->offset
= offset
;
1084 ref
->max_size
= max_size
;
1085 ref
->ref_alias_set
= set
;
1086 if (base_alias_set
!= -1)
1087 ref
->base_alias_set
= base_alias_set
;
1089 ref
->base_alias_set
= get_alias_set (base
);
1090 /* We discount volatiles from value-numbering elsewhere. */
1091 ref
->volatile_p
= false;
1096 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1097 vn_reference_op_s's. */
1100 copy_reference_ops_from_call (gimple call
,
1101 vec
<vn_reference_op_s
> *result
)
1103 vn_reference_op_s temp
;
1105 tree lhs
= gimple_call_lhs (call
);
1107 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1108 different. By adding the lhs here in the vector, we ensure that the
1109 hashcode is different, guaranteeing a different value number. */
1110 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1112 memset (&temp
, 0, sizeof (temp
));
1113 temp
.opcode
= MODIFY_EXPR
;
1114 temp
.type
= TREE_TYPE (lhs
);
1117 result
->safe_push (temp
);
1120 /* Copy the type, opcode, function being called and static chain. */
1121 memset (&temp
, 0, sizeof (temp
));
1122 temp
.type
= gimple_call_return_type (call
);
1123 temp
.opcode
= CALL_EXPR
;
1124 temp
.op0
= gimple_call_fn (call
);
1125 temp
.op1
= gimple_call_chain (call
);
1127 result
->safe_push (temp
);
1129 /* Copy the call arguments. As they can be references as well,
1130 just chain them together. */
1131 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1133 tree callarg
= gimple_call_arg (call
, i
);
1134 copy_reference_ops_from_ref (callarg
, result
);
1138 /* Create a vector of vn_reference_op_s structures from CALL, a
1139 call statement. The vector is not shared. */
1141 static vec
<vn_reference_op_s
>
1142 create_reference_ops_from_call (gimple call
)
1144 vec
<vn_reference_op_s
> result
= vNULL
;
1146 copy_reference_ops_from_call (call
, &result
);
1150 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1151 *I_P to point to the last element of the replacement. */
1153 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1156 unsigned int i
= *i_p
;
1157 vn_reference_op_t op
= &(*ops
)[i
];
1158 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1160 HOST_WIDE_INT addr_offset
= 0;
1162 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1163 from .foo.bar to the preceding MEM_REF offset and replace the
1164 address with &OBJ. */
1165 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1167 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1168 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1170 offset_int off
= offset_int::from (mem_op
->op0
, SIGNED
);
1172 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1173 op
->op0
= build_fold_addr_expr (addr_base
);
1174 if (tree_fits_shwi_p (mem_op
->op0
))
1175 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1181 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1182 *I_P to point to the last element of the replacement. */
1184 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1187 unsigned int i
= *i_p
;
1188 vn_reference_op_t op
= &(*ops
)[i
];
1189 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1191 enum tree_code code
;
1194 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1195 if (!is_gimple_assign (def_stmt
))
1198 code
= gimple_assign_rhs_code (def_stmt
);
1199 if (code
!= ADDR_EXPR
1200 && code
!= POINTER_PLUS_EXPR
)
1203 off
= offset_int::from (mem_op
->op0
, SIGNED
);
1205 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1206 from .foo.bar to the preceding MEM_REF offset and replace the
1207 address with &OBJ. */
1208 if (code
== ADDR_EXPR
)
1210 tree addr
, addr_base
;
1211 HOST_WIDE_INT addr_offset
;
1213 addr
= gimple_assign_rhs1 (def_stmt
);
1214 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1217 || TREE_CODE (addr_base
) != MEM_REF
)
1221 off
+= mem_ref_offset (addr_base
);
1222 op
->op0
= TREE_OPERAND (addr_base
, 0);
1227 ptr
= gimple_assign_rhs1 (def_stmt
);
1228 ptroff
= gimple_assign_rhs2 (def_stmt
);
1229 if (TREE_CODE (ptr
) != SSA_NAME
1230 || TREE_CODE (ptroff
) != INTEGER_CST
)
1233 off
+= wi::to_offset (ptroff
);
1237 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1238 if (tree_fits_shwi_p (mem_op
->op0
))
1239 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1242 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1243 op
->op0
= SSA_VAL (op
->op0
);
1244 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1245 op
->opcode
= TREE_CODE (op
->op0
);
1248 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1249 vn_reference_maybe_forwprop_address (ops
, i_p
);
1250 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1251 vn_reference_fold_indirect (ops
, i_p
);
1254 /* Optimize the reference REF to a constant if possible or return
1255 NULL_TREE if not. */
1258 fully_constant_vn_reference_p (vn_reference_t ref
)
1260 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1261 vn_reference_op_t op
;
1263 /* Try to simplify the translated expression if it is
1264 a call to a builtin function with at most two arguments. */
1266 if (op
->opcode
== CALL_EXPR
1267 && TREE_CODE (op
->op0
) == ADDR_EXPR
1268 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1269 && DECL_BUILT_IN (TREE_OPERAND (op
->op0
, 0))
1270 && operands
.length () >= 2
1271 && operands
.length () <= 3)
1273 vn_reference_op_t arg0
, arg1
= NULL
;
1274 bool anyconst
= false;
1275 arg0
= &operands
[1];
1276 if (operands
.length () > 2)
1277 arg1
= &operands
[2];
1278 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1279 || (arg0
->opcode
== ADDR_EXPR
1280 && is_gimple_min_invariant (arg0
->op0
)))
1283 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1284 || (arg1
->opcode
== ADDR_EXPR
1285 && is_gimple_min_invariant (arg1
->op0
))))
1289 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1292 arg1
? arg1
->op0
: NULL
);
1294 && TREE_CODE (folded
) == NOP_EXPR
)
1295 folded
= TREE_OPERAND (folded
, 0);
1297 && is_gimple_min_invariant (folded
))
1302 /* Simplify reads from constant strings. */
1303 else if (op
->opcode
== ARRAY_REF
1304 && TREE_CODE (op
->op0
) == INTEGER_CST
1305 && integer_zerop (op
->op1
)
1306 && operands
.length () == 2)
1308 vn_reference_op_t arg0
;
1309 arg0
= &operands
[1];
1310 if (arg0
->opcode
== STRING_CST
1311 && (TYPE_MODE (op
->type
)
1312 == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0
->op0
))))
1313 && GET_MODE_CLASS (TYPE_MODE (op
->type
)) == MODE_INT
1314 && GET_MODE_SIZE (TYPE_MODE (op
->type
)) == 1
1315 && tree_int_cst_sgn (op
->op0
) >= 0
1316 && compare_tree_int (op
->op0
, TREE_STRING_LENGTH (arg0
->op0
)) < 0)
1317 return build_int_cst_type (op
->type
,
1318 (TREE_STRING_POINTER (arg0
->op0
)
1319 [TREE_INT_CST_LOW (op
->op0
)]));
1325 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1326 structures into their value numbers. This is done in-place, and
1327 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1328 whether any operands were valueized. */
1330 static vec
<vn_reference_op_s
>
1331 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
)
1333 vn_reference_op_t vro
;
1336 *valueized_anything
= false;
1338 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1340 if (vro
->opcode
== SSA_NAME
1341 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1343 tree tem
= SSA_VAL (vro
->op0
);
1344 if (tem
!= vro
->op0
)
1346 *valueized_anything
= true;
1349 /* If it transforms from an SSA_NAME to a constant, update
1351 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1352 vro
->opcode
= TREE_CODE (vro
->op0
);
1354 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1356 tree tem
= SSA_VAL (vro
->op1
);
1357 if (tem
!= vro
->op1
)
1359 *valueized_anything
= true;
1363 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1365 tree tem
= SSA_VAL (vro
->op2
);
1366 if (tem
!= vro
->op2
)
1368 *valueized_anything
= true;
1372 /* If it transforms from an SSA_NAME to an address, fold with
1373 a preceding indirect reference. */
1376 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1377 && orig
[i
- 1].opcode
== MEM_REF
)
1378 vn_reference_fold_indirect (&orig
, &i
);
1380 && vro
->opcode
== SSA_NAME
1381 && orig
[i
- 1].opcode
== MEM_REF
)
1382 vn_reference_maybe_forwprop_address (&orig
, &i
);
1383 /* If it transforms a non-constant ARRAY_REF into a constant
1384 one, adjust the constant offset. */
1385 else if (vro
->opcode
== ARRAY_REF
1387 && TREE_CODE (vro
->op0
) == INTEGER_CST
1388 && TREE_CODE (vro
->op1
) == INTEGER_CST
1389 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1391 offset_int off
= ((wi::to_offset (vro
->op0
)
1392 - wi::to_offset (vro
->op1
))
1393 * wi::to_offset (vro
->op2
));
1394 if (wi::fits_shwi_p (off
))
1395 vro
->off
= off
.to_shwi ();
1402 static vec
<vn_reference_op_s
>
1403 valueize_refs (vec
<vn_reference_op_s
> orig
)
1406 return valueize_refs_1 (orig
, &tem
);
1409 static vec
<vn_reference_op_s
> shared_lookup_references
;
1411 /* Create a vector of vn_reference_op_s structures from REF, a
1412 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1413 this function. *VALUEIZED_ANYTHING will specify whether any
1414 operands were valueized. */
1416 static vec
<vn_reference_op_s
>
1417 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1421 shared_lookup_references
.truncate (0);
1422 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1423 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1424 valueized_anything
);
1425 return shared_lookup_references
;
1428 /* Create a vector of vn_reference_op_s structures from CALL, a
1429 call statement. The vector is shared among all callers of
1432 static vec
<vn_reference_op_s
>
1433 valueize_shared_reference_ops_from_call (gimple call
)
1437 shared_lookup_references
.truncate (0);
1438 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1439 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1440 return shared_lookup_references
;
1443 /* Lookup a SCCVN reference operation VR in the current hash table.
1444 Returns the resulting value number if it exists in the hash table,
1445 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1446 vn_reference_t stored in the hashtable if something is found. */
1449 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1451 vn_reference_s
**slot
;
1454 hash
= vr
->hashcode
;
1455 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1456 if (!slot
&& current_info
== optimistic_info
)
1457 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1461 *vnresult
= (vn_reference_t
)*slot
;
1462 return ((vn_reference_t
)*slot
)->result
;
1468 static tree
*last_vuse_ptr
;
1469 static vn_lookup_kind vn_walk_kind
;
1470 static vn_lookup_kind default_vn_walk_kind
;
1472 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1473 with the current VUSE and performs the expression lookup. */
1476 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
,
1477 unsigned int cnt
, void *vr_
)
1479 vn_reference_t vr
= (vn_reference_t
)vr_
;
1480 vn_reference_s
**slot
;
1483 /* This bounds the stmt walks we perform on reference lookups
1484 to O(1) instead of O(N) where N is the number of dominating
1486 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1490 *last_vuse_ptr
= vuse
;
1492 /* Fixup vuse and hash. */
1494 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1495 vr
->vuse
= SSA_VAL (vuse
);
1497 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1499 hash
= vr
->hashcode
;
1500 slot
= current_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1501 if (!slot
&& current_info
== optimistic_info
)
1502 slot
= valid_info
->references
.find_slot_with_hash (vr
, hash
, NO_INSERT
);
1509 /* Lookup an existing or insert a new vn_reference entry into the
1510 value table for the VUSE, SET, TYPE, OPERANDS reference which
1511 has the value VALUE which is either a constant or an SSA name. */
1513 static vn_reference_t
1514 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1517 vec
<vn_reference_op_s
,
1521 struct vn_reference_s vr1
;
1522 vn_reference_t result
;
1525 vr1
.operands
= operands
;
1528 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1529 if (vn_reference_lookup_1 (&vr1
, &result
))
1531 if (TREE_CODE (value
) == SSA_NAME
)
1532 value_id
= VN_INFO (value
)->value_id
;
1534 value_id
= get_or_alloc_constant_value_id (value
);
1535 return vn_reference_insert_pieces (vuse
, set
, type
,
1536 operands
.copy (), value
, value_id
);
1539 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1540 from the statement defining VUSE and if not successful tries to
1541 translate *REFP and VR_ through an aggregate copy at the definition
1545 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
,
1546 bool disambiguate_only
)
1548 vn_reference_t vr
= (vn_reference_t
)vr_
;
1549 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1551 HOST_WIDE_INT offset
, maxsize
;
1552 static vec
<vn_reference_op_s
>
1555 bool lhs_ref_ok
= false;
1557 /* First try to disambiguate after value-replacing in the definitions LHS. */
1558 if (is_gimple_assign (def_stmt
))
1560 vec
<vn_reference_op_s
> tem
;
1561 tree lhs
= gimple_assign_lhs (def_stmt
);
1562 bool valueized_anything
= false;
1563 /* Avoid re-allocation overhead. */
1564 lhs_ops
.truncate (0);
1565 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1567 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
);
1568 gcc_assert (lhs_ops
== tem
);
1569 if (valueized_anything
)
1571 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1572 get_alias_set (lhs
),
1573 TREE_TYPE (lhs
), lhs_ops
);
1575 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1580 ao_ref_init (&lhs_ref
, lhs
);
1584 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
1585 && gimple_call_num_args (def_stmt
) <= 4)
1587 /* For builtin calls valueize its arguments and call the
1588 alias oracle again. Valueization may improve points-to
1589 info of pointers and constify size and position arguments.
1590 Originally this was motivated by PR61034 which has
1591 conditional calls to free falsely clobbering ref because
1592 of imprecise points-to info of the argument. */
1594 bool valueized_anything
;
1595 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1597 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
1598 if (TREE_CODE (oldargs
[i
]) == SSA_NAME
1599 && VN_INFO (oldargs
[i
])->valnum
!= oldargs
[i
])
1601 gimple_call_set_arg (def_stmt
, i
, VN_INFO (oldargs
[i
])->valnum
);
1602 valueized_anything
= true;
1605 if (valueized_anything
)
1607 bool res
= call_may_clobber_ref_p_1 (def_stmt
, ref
);
1608 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
1609 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
1615 if (disambiguate_only
)
1618 base
= ao_ref_base (ref
);
1619 offset
= ref
->offset
;
1620 maxsize
= ref
->max_size
;
1622 /* If we cannot constrain the size of the reference we cannot
1623 test if anything kills it. */
1627 /* We can't deduce anything useful from clobbers. */
1628 if (gimple_clobber_p (def_stmt
))
1631 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1632 from that definition.
1634 if (is_gimple_reg_type (vr
->type
)
1635 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
1636 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1637 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2))
1638 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1640 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1642 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1643 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1644 size2
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2)) * 8;
1645 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1646 == tree_to_uhwi (gimple_call_arg (def_stmt
, 2))
1648 && operand_equal_p (base
, base2
, 0)
1649 && offset2
<= offset
1650 && offset2
+ size2
>= offset
+ maxsize
)
1652 tree val
= build_zero_cst (vr
->type
);
1653 return vn_reference_lookup_or_insert_for_pieces
1654 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1658 /* 2) Assignment from an empty CONSTRUCTOR. */
1659 else if (is_gimple_reg_type (vr
->type
)
1660 && gimple_assign_single_p (def_stmt
)
1661 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1662 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1665 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1666 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1667 &offset2
, &size2
, &maxsize2
);
1669 && operand_equal_p (base
, base2
, 0)
1670 && offset2
<= offset
1671 && offset2
+ size2
>= offset
+ maxsize
)
1673 tree val
= build_zero_cst (vr
->type
);
1674 return vn_reference_lookup_or_insert_for_pieces
1675 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1679 /* 3) Assignment from a constant. We can use folds native encode/interpret
1680 routines to extract the assigned bits. */
1681 else if (vn_walk_kind
== VN_WALKREWRITE
1682 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
1683 && ref
->size
== maxsize
1684 && maxsize
% BITS_PER_UNIT
== 0
1685 && offset
% BITS_PER_UNIT
== 0
1686 && is_gimple_reg_type (vr
->type
)
1687 && gimple_assign_single_p (def_stmt
)
1688 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
1691 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1692 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1693 &offset2
, &size2
, &maxsize2
);
1695 && maxsize2
== size2
1696 && size2
% BITS_PER_UNIT
== 0
1697 && offset2
% BITS_PER_UNIT
== 0
1698 && operand_equal_p (base
, base2
, 0)
1699 && offset2
<= offset
1700 && offset2
+ size2
>= offset
+ maxsize
)
1702 /* We support up to 512-bit values (for V8DFmode). */
1703 unsigned char buffer
[64];
1706 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
1707 buffer
, sizeof (buffer
));
1710 tree val
= native_interpret_expr (vr
->type
,
1712 + ((offset
- offset2
)
1714 ref
->size
/ BITS_PER_UNIT
);
1716 return vn_reference_lookup_or_insert_for_pieces
1717 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1722 /* 4) Assignment from an SSA name which definition we may be able
1723 to access pieces from. */
1724 else if (ref
->size
== maxsize
1725 && is_gimple_reg_type (vr
->type
)
1726 && gimple_assign_single_p (def_stmt
)
1727 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
1729 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1730 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs1
);
1731 if (is_gimple_assign (def_stmt2
)
1732 && (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
1733 || gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
)
1734 && types_compatible_p (vr
->type
, TREE_TYPE (TREE_TYPE (rhs1
))))
1737 HOST_WIDE_INT offset2
, size2
, maxsize2
, off
;
1738 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1739 &offset2
, &size2
, &maxsize2
);
1740 off
= offset
- offset2
;
1742 && maxsize2
== size2
1743 && operand_equal_p (base
, base2
, 0)
1744 && offset2
<= offset
1745 && offset2
+ size2
>= offset
+ maxsize
)
1747 tree val
= NULL_TREE
;
1749 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1
))));
1750 if (gimple_assign_rhs_code (def_stmt2
) == COMPLEX_EXPR
)
1753 val
= gimple_assign_rhs1 (def_stmt2
);
1754 else if (off
== elsz
)
1755 val
= gimple_assign_rhs2 (def_stmt2
);
1757 else if (gimple_assign_rhs_code (def_stmt2
) == CONSTRUCTOR
1760 tree ctor
= gimple_assign_rhs1 (def_stmt2
);
1761 unsigned i
= off
/ elsz
;
1762 if (i
< CONSTRUCTOR_NELTS (ctor
))
1764 constructor_elt
*elt
= CONSTRUCTOR_ELT (ctor
, i
);
1765 if (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
1767 if (TREE_CODE (TREE_TYPE (elt
->value
))
1774 return vn_reference_lookup_or_insert_for_pieces
1775 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
1780 /* 5) For aggregate copies translate the reference through them if
1781 the copy kills ref. */
1782 else if (vn_walk_kind
== VN_WALKREWRITE
1783 && gimple_assign_single_p (def_stmt
)
1784 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1785 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
1786 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1789 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1791 auto_vec
<vn_reference_op_s
> rhs
;
1792 vn_reference_op_t vro
;
1798 /* See if the assignment kills REF. */
1799 base2
= ao_ref_base (&lhs_ref
);
1800 offset2
= lhs_ref
.offset
;
1801 size2
= lhs_ref
.size
;
1802 maxsize2
= lhs_ref
.max_size
;
1804 || (base
!= base2
&& !operand_equal_p (base
, base2
, 0))
1806 || offset2
+ size2
< offset
+ maxsize
)
1809 /* Find the common base of ref and the lhs. lhs_ops already
1810 contains valueized operands for the lhs. */
1811 i
= vr
->operands
.length () - 1;
1812 j
= lhs_ops
.length () - 1;
1813 while (j
>= 0 && i
>= 0
1814 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
1820 /* ??? The innermost op should always be a MEM_REF and we already
1821 checked that the assignment to the lhs kills vr. Thus for
1822 aggregate copies using char[] types the vn_reference_op_eq
1823 may fail when comparing types for compatibility. But we really
1824 don't care here - further lookups with the rewritten operands
1825 will simply fail if we messed up types too badly. */
1826 if (j
== 0 && i
>= 0
1827 && lhs_ops
[0].opcode
== MEM_REF
1828 && lhs_ops
[0].off
!= -1
1829 && (lhs_ops
[0].off
== vr
->operands
[i
].off
))
1832 /* i now points to the first additional op.
1833 ??? LHS may not be completely contained in VR, one or more
1834 VIEW_CONVERT_EXPRs could be in its way. We could at least
1835 try handling outermost VIEW_CONVERT_EXPRs. */
1839 /* Now re-write REF to be based on the rhs of the assignment. */
1840 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1841 /* We need to pre-pend vr->operands[0..i] to rhs. */
1842 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
1844 vec
<vn_reference_op_s
> old
= vr
->operands
;
1845 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
1846 if (old
== shared_lookup_references
1847 && vr
->operands
!= old
)
1848 shared_lookup_references
= vNULL
;
1851 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
1852 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
1853 vr
->operands
[i
+ 1 + j
] = *vro
;
1854 vr
->operands
= valueize_refs (vr
->operands
);
1855 vr
->hashcode
= vn_reference_compute_hash (vr
);
1857 /* Adjust *ref from the new operands. */
1858 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1860 /* This can happen with bitfields. */
1861 if (ref
->size
!= r
.size
)
1865 /* Do not update last seen VUSE after translating. */
1866 last_vuse_ptr
= NULL
;
1868 /* Keep looking for the adjusted *REF / VR pair. */
1872 /* 6) For memcpy copies translate the reference through them if
1873 the copy kills ref. */
1874 else if (vn_walk_kind
== VN_WALKREWRITE
1875 && is_gimple_reg_type (vr
->type
)
1876 /* ??? Handle BCOPY as well. */
1877 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
1878 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
1879 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
1880 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
1881 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
1882 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
1883 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
1884 && tree_fits_uhwi_p (gimple_call_arg (def_stmt
, 2)))
1888 HOST_WIDE_INT rhs_offset
, copy_size
, lhs_offset
;
1889 vn_reference_op_s op
;
1893 /* Only handle non-variable, addressable refs. */
1894 if (ref
->size
!= maxsize
1895 || offset
% BITS_PER_UNIT
!= 0
1896 || ref
->size
% BITS_PER_UNIT
!= 0)
1899 /* Extract a pointer base and an offset for the destination. */
1900 lhs
= gimple_call_arg (def_stmt
, 0);
1902 if (TREE_CODE (lhs
) == SSA_NAME
)
1903 lhs
= SSA_VAL (lhs
);
1904 if (TREE_CODE (lhs
) == ADDR_EXPR
)
1906 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
1910 if (TREE_CODE (tem
) == MEM_REF
1911 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1913 lhs
= TREE_OPERAND (tem
, 0);
1914 lhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1916 else if (DECL_P (tem
))
1917 lhs
= build_fold_addr_expr (tem
);
1921 if (TREE_CODE (lhs
) != SSA_NAME
1922 && TREE_CODE (lhs
) != ADDR_EXPR
)
1925 /* Extract a pointer base and an offset for the source. */
1926 rhs
= gimple_call_arg (def_stmt
, 1);
1928 if (TREE_CODE (rhs
) == SSA_NAME
)
1929 rhs
= SSA_VAL (rhs
);
1930 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1932 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
1936 if (TREE_CODE (tem
) == MEM_REF
1937 && tree_fits_uhwi_p (TREE_OPERAND (tem
, 1)))
1939 rhs
= TREE_OPERAND (tem
, 0);
1940 rhs_offset
+= tree_to_uhwi (TREE_OPERAND (tem
, 1));
1942 else if (DECL_P (tem
))
1943 rhs
= build_fold_addr_expr (tem
);
1947 if (TREE_CODE (rhs
) != SSA_NAME
1948 && TREE_CODE (rhs
) != ADDR_EXPR
)
1951 copy_size
= tree_to_uhwi (gimple_call_arg (def_stmt
, 2));
1953 /* The bases of the destination and the references have to agree. */
1954 if ((TREE_CODE (base
) != MEM_REF
1956 || (TREE_CODE (base
) == MEM_REF
1957 && (TREE_OPERAND (base
, 0) != lhs
1958 || !tree_fits_uhwi_p (TREE_OPERAND (base
, 1))))
1960 && (TREE_CODE (lhs
) != ADDR_EXPR
1961 || TREE_OPERAND (lhs
, 0) != base
)))
1964 /* And the access has to be contained within the memcpy destination. */
1965 at
= offset
/ BITS_PER_UNIT
;
1966 if (TREE_CODE (base
) == MEM_REF
)
1967 at
+= tree_to_uhwi (TREE_OPERAND (base
, 1));
1969 || lhs_offset
+ copy_size
< at
+ maxsize
/ BITS_PER_UNIT
)
1972 /* Make room for 2 operands in the new reference. */
1973 if (vr
->operands
.length () < 2)
1975 vec
<vn_reference_op_s
> old
= vr
->operands
;
1976 vr
->operands
.safe_grow_cleared (2);
1977 if (old
== shared_lookup_references
1978 && vr
->operands
!= old
)
1979 shared_lookup_references
.create (0);
1982 vr
->operands
.truncate (2);
1984 /* The looked-through reference is a simple MEM_REF. */
1985 memset (&op
, 0, sizeof (op
));
1987 op
.opcode
= MEM_REF
;
1988 op
.op0
= build_int_cst (ptr_type_node
, at
- rhs_offset
);
1989 op
.off
= at
- lhs_offset
+ rhs_offset
;
1990 vr
->operands
[0] = op
;
1991 op
.type
= TREE_TYPE (rhs
);
1992 op
.opcode
= TREE_CODE (rhs
);
1995 vr
->operands
[1] = op
;
1996 vr
->hashcode
= vn_reference_compute_hash (vr
);
1998 /* Adjust *ref from the new operands. */
1999 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2001 /* This can happen with bitfields. */
2002 if (ref
->size
!= r
.size
)
2006 /* Do not update last seen VUSE after translating. */
2007 last_vuse_ptr
= NULL
;
2009 /* Keep looking for the adjusted *REF / VR pair. */
2013 /* Bail out and stop walking. */
2017 /* Lookup a reference operation by it's parts, in the current hash table.
2018 Returns the resulting value number if it exists in the hash table,
2019 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2020 vn_reference_t stored in the hashtable if something is found. */
2023 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2024 vec
<vn_reference_op_s
> operands
,
2025 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2027 struct vn_reference_s vr1
;
2035 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2036 shared_lookup_references
.truncate (0);
2037 shared_lookup_references
.safe_grow (operands
.length ());
2038 memcpy (shared_lookup_references
.address (),
2039 operands
.address (),
2040 sizeof (vn_reference_op_s
)
2041 * operands
.length ());
2042 vr1
.operands
= operands
= shared_lookup_references
2043 = valueize_refs (shared_lookup_references
);
2046 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2047 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2050 vn_reference_lookup_1 (&vr1
, vnresult
);
2052 && kind
!= VN_NOWALK
2056 vn_walk_kind
= kind
;
2057 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2059 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2060 vn_reference_lookup_2
,
2061 vn_reference_lookup_3
, &vr1
);
2062 if (vr1
.operands
!= operands
)
2063 vr1
.operands
.release ();
2067 return (*vnresult
)->result
;
2072 /* Lookup OP in the current hash table, and return the resulting value
2073 number if it exists in the hash table. Return NULL_TREE if it does
2074 not exist in the hash table or if the result field of the structure
2075 was NULL.. VNRESULT will be filled in with the vn_reference_t
2076 stored in the hashtable if one exists. */
2079 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2080 vn_reference_t
*vnresult
)
2082 vec
<vn_reference_op_s
> operands
;
2083 struct vn_reference_s vr1
;
2085 bool valuezied_anything
;
2090 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2091 vr1
.operands
= operands
2092 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2093 vr1
.type
= TREE_TYPE (op
);
2094 vr1
.set
= get_alias_set (op
);
2095 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2096 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2099 if (kind
!= VN_NOWALK
2102 vn_reference_t wvnresult
;
2104 /* Make sure to use a valueized reference if we valueized anything.
2105 Otherwise preserve the full reference for advanced TBAA. */
2106 if (!valuezied_anything
2107 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2109 ao_ref_init (&r
, op
);
2110 vn_walk_kind
= kind
;
2112 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2113 vn_reference_lookup_2
,
2114 vn_reference_lookup_3
, &vr1
);
2115 if (vr1
.operands
!= operands
)
2116 vr1
.operands
.release ();
2120 *vnresult
= wvnresult
;
2121 return wvnresult
->result
;
2127 return vn_reference_lookup_1 (&vr1
, vnresult
);
2131 /* Insert OP into the current hash table with a value number of
2132 RESULT, and return the resulting reference structure we created. */
2135 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2137 vn_reference_s
**slot
;
2141 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2142 if (TREE_CODE (result
) == SSA_NAME
)
2143 vr1
->value_id
= VN_INFO (result
)->value_id
;
2145 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2146 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2147 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2148 vr1
->type
= TREE_TYPE (op
);
2149 vr1
->set
= get_alias_set (op
);
2150 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2151 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2152 vr1
->result_vdef
= vdef
;
2154 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2157 /* Because we lookup stores using vuses, and value number failures
2158 using the vdefs (see visit_reference_op_store for how and why),
2159 it's possible that on failure we may try to insert an already
2160 inserted store. This is not wrong, there is no ssa name for a
2161 store that we could use as a differentiator anyway. Thus, unlike
2162 the other lookup functions, you cannot gcc_assert (!*slot)
2165 /* But free the old slot in case of a collision. */
2167 free_reference (*slot
);
2173 /* Insert a reference by it's pieces into the current hash table with
2174 a value number of RESULT. Return the resulting reference
2175 structure we created. */
2178 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2179 vec
<vn_reference_op_s
> operands
,
2180 tree result
, unsigned int value_id
)
2183 vn_reference_s
**slot
;
2186 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2187 vr1
->value_id
= value_id
;
2188 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2189 vr1
->operands
= valueize_refs (operands
);
2192 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2193 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2194 result
= SSA_VAL (result
);
2195 vr1
->result
= result
;
2197 slot
= current_info
->references
.find_slot_with_hash (vr1
, vr1
->hashcode
,
2200 /* At this point we should have all the things inserted that we have
2201 seen before, and we should never try inserting something that
2203 gcc_assert (!*slot
);
2205 free_reference (*slot
);
2211 /* Compute and return the hash value for nary operation VBO1. */
2214 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2219 for (i
= 0; i
< vno1
->length
; ++i
)
2220 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2221 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2223 if (vno1
->length
== 2
2224 && commutative_tree_code (vno1
->opcode
)
2225 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
2227 tree temp
= vno1
->op
[0];
2228 vno1
->op
[0] = vno1
->op
[1];
2232 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
2233 for (i
= 0; i
< vno1
->length
; ++i
)
2234 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
2239 /* Compare nary operations VNO1 and VNO2 and return true if they are
2243 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2247 if (vno1
->hashcode
!= vno2
->hashcode
)
2250 if (vno1
->length
!= vno2
->length
)
2253 if (vno1
->opcode
!= vno2
->opcode
2254 || !types_compatible_p (vno1
->type
, vno2
->type
))
2257 for (i
= 0; i
< vno1
->length
; ++i
)
2258 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2264 /* Initialize VNO from the pieces provided. */
2267 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2268 enum tree_code code
, tree type
, tree
*ops
)
2271 vno
->length
= length
;
2273 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2276 /* Initialize VNO from OP. */
2279 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2283 vno
->opcode
= TREE_CODE (op
);
2284 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2285 vno
->type
= TREE_TYPE (op
);
2286 for (i
= 0; i
< vno
->length
; ++i
)
2287 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2290 /* Return the number of operands for a vn_nary ops structure from STMT. */
2293 vn_nary_length_from_stmt (gimple stmt
)
2295 switch (gimple_assign_rhs_code (stmt
))
2299 case VIEW_CONVERT_EXPR
:
2306 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2309 return gimple_num_ops (stmt
) - 1;
2313 /* Initialize VNO from STMT. */
2316 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple stmt
)
2320 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2321 vno
->type
= gimple_expr_type (stmt
);
2322 switch (vno
->opcode
)
2326 case VIEW_CONVERT_EXPR
:
2328 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2333 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2334 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2335 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2339 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2340 for (i
= 0; i
< vno
->length
; ++i
)
2341 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
2345 gcc_checking_assert (!gimple_assign_single_p (stmt
));
2346 vno
->length
= gimple_num_ops (stmt
) - 1;
2347 for (i
= 0; i
< vno
->length
; ++i
)
2348 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
2352 /* Compute the hashcode for VNO and look for it in the hash table;
2353 return the resulting value number if it exists in the hash table.
2354 Return NULL_TREE if it does not exist in the hash table or if the
2355 result field of the operation is NULL. VNRESULT will contain the
2356 vn_nary_op_t from the hashtable if it exists. */
2359 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
2361 vn_nary_op_s
**slot
;
2366 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2367 slot
= current_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2368 if (!slot
&& current_info
== optimistic_info
)
2369 slot
= valid_info
->nary
.find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
2374 return (*slot
)->result
;
2377 /* Lookup a n-ary operation by its pieces and return the resulting value
2378 number if it exists in the hash table. Return NULL_TREE if it does
2379 not exist in the hash table or if the result field of the operation
2380 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2384 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
2385 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
2387 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
2388 sizeof_vn_nary_op (length
));
2389 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2390 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2393 /* Lookup OP in the current hash table, and return the resulting value
2394 number if it exists in the hash table. Return NULL_TREE if it does
2395 not exist in the hash table or if the result field of the operation
2396 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2400 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
2403 = XALLOCAVAR (struct vn_nary_op_s
,
2404 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
2405 init_vn_nary_op_from_op (vno1
, op
);
2406 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2409 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2410 value number if it exists in the hash table. Return NULL_TREE if
2411 it does not exist in the hash table. VNRESULT will contain the
2412 vn_nary_op_t from the hashtable if it exists. */
2415 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
2418 = XALLOCAVAR (struct vn_nary_op_s
,
2419 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
2420 init_vn_nary_op_from_stmt (vno1
, stmt
);
2421 return vn_nary_op_lookup_1 (vno1
, vnresult
);
2424 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2427 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
2429 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
2432 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2436 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
2438 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
,
2439 ¤t_info
->nary_obstack
);
2441 vno1
->value_id
= value_id
;
2442 vno1
->length
= length
;
2443 vno1
->result
= result
;
2448 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2449 VNO->HASHCODE first. */
2452 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type table
,
2455 vn_nary_op_s
**slot
;
2458 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
2460 slot
= table
.find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
2461 gcc_assert (!*slot
);
2467 /* Insert a n-ary operation into the current hash table using it's
2468 pieces. Return the vn_nary_op_t structure we created and put in
2472 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
2473 tree type
, tree
*ops
,
2474 tree result
, unsigned int value_id
)
2476 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
2477 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
2478 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2481 /* Insert OP into the current hash table with a value number of
2482 RESULT. Return the vn_nary_op_t structure we created and put in
2486 vn_nary_op_insert (tree op
, tree result
)
2488 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2491 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
2492 init_vn_nary_op_from_op (vno1
, op
);
2493 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2496 /* Insert the rhs of STMT into the current hash table with a value number of
2500 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
2503 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
2504 result
, VN_INFO (result
)->value_id
);
2505 init_vn_nary_op_from_stmt (vno1
, stmt
);
2506 return vn_nary_op_insert_into (vno1
, current_info
->nary
, true);
2509 /* Compute a hashcode for PHI operation VP1 and return it. */
2511 static inline hashval_t
2512 vn_phi_compute_hash (vn_phi_t vp1
)
2519 result
= vp1
->block
->index
;
2521 /* If all PHI arguments are constants we need to distinguish
2522 the PHI node via its type. */
2524 result
+= vn_hash_type (type
);
2526 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2528 if (phi1op
== VN_TOP
)
2530 result
= iterative_hash_expr (phi1op
, result
);
2536 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2539 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
2541 if (vp1
->hashcode
!= vp2
->hashcode
)
2544 if (vp1
->block
== vp2
->block
)
2549 /* If the PHI nodes do not have compatible types
2550 they are not the same. */
2551 if (!types_compatible_p (vp1
->type
, vp2
->type
))
2554 /* Any phi in the same block will have it's arguments in the
2555 same edge order, because of how we store phi nodes. */
2556 FOR_EACH_VEC_ELT (vp1
->phiargs
, i
, phi1op
)
2558 tree phi2op
= vp2
->phiargs
[i
];
2559 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
2561 if (!expressions_equal_p (phi1op
, phi2op
))
2569 static vec
<tree
> shared_lookup_phiargs
;
2571 /* Lookup PHI in the current hash table, and return the resulting
2572 value number if it exists in the hash table. Return NULL_TREE if
2573 it does not exist in the hash table. */
2576 vn_phi_lookup (gimple phi
)
2579 struct vn_phi_s vp1
;
2582 shared_lookup_phiargs
.truncate (0);
2584 /* Canonicalize the SSA_NAME's to their value number. */
2585 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2587 tree def
= PHI_ARG_DEF (phi
, i
);
2588 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2589 shared_lookup_phiargs
.safe_push (def
);
2591 vp1
.type
= TREE_TYPE (gimple_phi_result (phi
));
2592 vp1
.phiargs
= shared_lookup_phiargs
;
2593 vp1
.block
= gimple_bb (phi
);
2594 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
2595 slot
= current_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2596 if (!slot
&& current_info
== optimistic_info
)
2597 slot
= valid_info
->phis
.find_slot_with_hash (&vp1
, vp1
.hashcode
, NO_INSERT
);
2600 return (*slot
)->result
;
2603 /* Insert PHI into the current hash table with a value number of
2607 vn_phi_insert (gimple phi
, tree result
)
2610 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2612 vec
<tree
> args
= vNULL
;
2614 /* Canonicalize the SSA_NAME's to their value number. */
2615 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2617 tree def
= PHI_ARG_DEF (phi
, i
);
2618 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
2619 args
.safe_push (def
);
2621 vp1
->value_id
= VN_INFO (result
)->value_id
;
2622 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
2623 vp1
->phiargs
= args
;
2624 vp1
->block
= gimple_bb (phi
);
2625 vp1
->result
= result
;
2626 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
2628 slot
= current_info
->phis
.find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
2630 /* Because we iterate over phi operations more than once, it's
2631 possible the slot might already exist here, hence no assert.*/
2637 /* Print set of components in strongly connected component SCC to OUT. */
2640 print_scc (FILE *out
, vec
<tree
> scc
)
2645 fprintf (out
, "SCC consists of:");
2646 FOR_EACH_VEC_ELT (scc
, i
, var
)
2649 print_generic_expr (out
, var
, 0);
2651 fprintf (out
, "\n");
2654 /* Set the value number of FROM to TO, return true if it has changed
2658 set_ssa_val_to (tree from
, tree to
)
2660 tree currval
= SSA_VAL (from
);
2661 HOST_WIDE_INT toff
, coff
;
2665 if (currval
== from
)
2667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2669 fprintf (dump_file
, "Not changing value number of ");
2670 print_generic_expr (dump_file
, from
, 0);
2671 fprintf (dump_file
, " from VARYING to ");
2672 print_generic_expr (dump_file
, to
, 0);
2673 fprintf (dump_file
, "\n");
2677 else if (TREE_CODE (to
) == SSA_NAME
2678 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
2682 /* The only thing we allow as value numbers are VN_TOP, ssa_names
2683 and invariants. So assert that here. */
2684 gcc_assert (to
!= NULL_TREE
2686 || TREE_CODE (to
) == SSA_NAME
2687 || is_gimple_min_invariant (to
)));
2689 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2691 fprintf (dump_file
, "Setting value number of ");
2692 print_generic_expr (dump_file
, from
, 0);
2693 fprintf (dump_file
, " to ");
2694 print_generic_expr (dump_file
, to
, 0);
2698 && !operand_equal_p (currval
, to
, 0)
2699 /* ??? For addresses involving volatile objects or types operand_equal_p
2700 does not reliably detect ADDR_EXPRs as equal. We know we are only
2701 getting invariant gimple addresses here, so can use
2702 get_addr_base_and_unit_offset to do this comparison. */
2703 && !(TREE_CODE (currval
) == ADDR_EXPR
2704 && TREE_CODE (to
) == ADDR_EXPR
2705 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
2706 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
2709 VN_INFO (from
)->valnum
= to
;
2710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2711 fprintf (dump_file
, " (changed)\n");
2714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2715 fprintf (dump_file
, "\n");
2719 /* Mark as processed all the definitions in the defining stmt of USE, or
2723 mark_use_processed (tree use
)
2727 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2729 if (SSA_NAME_IS_DEFAULT_DEF (use
) || gimple_code (stmt
) == GIMPLE_PHI
)
2731 VN_INFO (use
)->use_processed
= true;
2735 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2737 tree def
= DEF_FROM_PTR (defp
);
2739 VN_INFO (def
)->use_processed
= true;
2743 /* Set all definitions in STMT to value number to themselves.
2744 Return true if a value number changed. */
2747 defs_to_varying (gimple stmt
)
2749 bool changed
= false;
2753 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2755 tree def
= DEF_FROM_PTR (defp
);
2756 changed
|= set_ssa_val_to (def
, def
);
2761 static bool expr_has_constants (tree expr
);
2762 static tree
valueize_expr (tree expr
);
2764 /* Visit a copy between LHS and RHS, return true if the value number
2768 visit_copy (tree lhs
, tree rhs
)
2770 /* The copy may have a more interesting constant filled expression
2771 (we don't, since we know our RHS is just an SSA name). */
2772 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
2773 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
2775 /* And finally valueize. */
2776 rhs
= SSA_VAL (rhs
);
2778 return set_ssa_val_to (lhs
, rhs
);
2781 /* Visit a nary operator RHS, value number it, and return true if the
2782 value number of LHS has changed as a result. */
2785 visit_nary_op (tree lhs
, gimple stmt
)
2787 bool changed
= false;
2788 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
2791 changed
= set_ssa_val_to (lhs
, result
);
2794 changed
= set_ssa_val_to (lhs
, lhs
);
2795 vn_nary_op_insert_stmt (stmt
, lhs
);
2801 /* Visit a call STMT storing into LHS. Return true if the value number
2802 of the LHS has changed as a result. */
2805 visit_reference_op_call (tree lhs
, gimple stmt
)
2807 bool changed
= false;
2808 struct vn_reference_s vr1
;
2809 vn_reference_t vnresult
= NULL
;
2810 tree vuse
= gimple_vuse (stmt
);
2811 tree vdef
= gimple_vdef (stmt
);
2813 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2814 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
2817 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2818 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
2819 vr1
.type
= gimple_expr_type (stmt
);
2821 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2822 vn_reference_lookup_1 (&vr1
, &vnresult
);
2826 if (vnresult
->result_vdef
&& vdef
)
2827 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
2829 if (!vnresult
->result
&& lhs
)
2830 vnresult
->result
= lhs
;
2832 if (vnresult
->result
&& lhs
)
2834 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
2836 if (VN_INFO (vnresult
->result
)->has_constants
)
2837 VN_INFO (lhs
)->has_constants
= true;
2842 vn_reference_s
**slot
;
2845 changed
|= set_ssa_val_to (vdef
, vdef
);
2847 changed
|= set_ssa_val_to (lhs
, lhs
);
2848 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2849 vr2
->vuse
= vr1
.vuse
;
2850 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
2851 vr2
->type
= vr1
.type
;
2853 vr2
->hashcode
= vr1
.hashcode
;
2855 vr2
->result_vdef
= vdef
;
2856 slot
= current_info
->references
.find_slot_with_hash (vr2
, vr2
->hashcode
,
2859 free_reference (*slot
);
2866 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2867 and return true if the value number of the LHS has changed as a result. */
2870 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
2872 bool changed
= false;
2876 last_vuse
= gimple_vuse (stmt
);
2877 last_vuse_ptr
= &last_vuse
;
2878 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
2879 default_vn_walk_kind
, NULL
);
2880 last_vuse_ptr
= NULL
;
2882 /* If we have a VCE, try looking up its operand as it might be stored in
2883 a different type. */
2884 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
2885 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
2886 default_vn_walk_kind
, NULL
);
2888 /* We handle type-punning through unions by value-numbering based
2889 on offset and size of the access. Be prepared to handle a
2890 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
2892 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
2894 /* We will be setting the value number of lhs to the value number
2895 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2896 So first simplify and lookup this expression to see if it
2897 is already available. */
2898 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2899 if ((CONVERT_EXPR_P (val
)
2900 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2901 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2903 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2904 if ((CONVERT_EXPR_P (tem
)
2905 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2906 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2907 TREE_TYPE (val
), tem
)))
2911 if (!is_gimple_min_invariant (val
)
2912 && TREE_CODE (val
) != SSA_NAME
)
2913 result
= vn_nary_op_lookup (val
, NULL
);
2914 /* If the expression is not yet available, value-number lhs to
2915 a new SSA_NAME we create. */
2918 result
= make_temp_ssa_name (TREE_TYPE (lhs
), gimple_build_nop (),
2920 /* Initialize value-number information properly. */
2921 VN_INFO_GET (result
)->valnum
= result
;
2922 VN_INFO (result
)->value_id
= get_next_value_id ();
2923 VN_INFO (result
)->expr
= val
;
2924 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2925 VN_INFO (result
)->needs_insertion
= true;
2926 /* As all "inserted" statements are singleton SCCs, insert
2927 to the valid table. This is strictly needed to
2928 avoid re-generating new value SSA_NAMEs for the same
2929 expression during SCC iteration over and over (the
2930 optimistic table gets cleared after each iteration).
2931 We do not need to insert into the optimistic table, as
2932 lookups there will fall back to the valid table. */
2933 if (current_info
== optimistic_info
)
2935 current_info
= valid_info
;
2936 vn_nary_op_insert (val
, result
);
2937 current_info
= optimistic_info
;
2940 vn_nary_op_insert (val
, result
);
2941 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2943 fprintf (dump_file
, "Inserting name ");
2944 print_generic_expr (dump_file
, result
, 0);
2945 fprintf (dump_file
, " for expression ");
2946 print_generic_expr (dump_file
, val
, 0);
2947 fprintf (dump_file
, "\n");
2954 changed
= set_ssa_val_to (lhs
, result
);
2955 if (TREE_CODE (result
) == SSA_NAME
2956 && VN_INFO (result
)->has_constants
)
2958 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2959 VN_INFO (lhs
)->has_constants
= true;
2964 changed
= set_ssa_val_to (lhs
, lhs
);
2965 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
2972 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2973 and return true if the value number of the LHS has changed as a result. */
2976 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2978 bool changed
= false;
2979 vn_reference_t vnresult
= NULL
;
2980 tree result
, assign
;
2981 bool resultsame
= false;
2982 tree vuse
= gimple_vuse (stmt
);
2983 tree vdef
= gimple_vdef (stmt
);
2985 /* First we want to lookup using the *vuses* from the store and see
2986 if there the last store to this location with the same address
2989 The vuses represent the memory state before the store. If the
2990 memory state, address, and value of the store is the same as the
2991 last store to this location, then this store will produce the
2992 same memory state as that store.
2994 In this case the vdef versions for this store are value numbered to those
2995 vuse versions, since they represent the same memory state after
2998 Otherwise, the vdefs for the store are used when inserting into
2999 the table, since the store generates a new memory state. */
3001 result
= vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, NULL
);
3005 if (TREE_CODE (result
) == SSA_NAME
)
3006 result
= SSA_VAL (result
);
3007 if (TREE_CODE (op
) == SSA_NAME
)
3009 resultsame
= expressions_equal_p (result
, op
);
3012 if (!result
|| !resultsame
)
3014 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3015 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
);
3018 VN_INFO (vdef
)->use_processed
= true;
3019 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
3023 if (!result
|| !resultsame
)
3025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3027 fprintf (dump_file
, "No store match\n");
3028 fprintf (dump_file
, "Value numbering store ");
3029 print_generic_expr (dump_file
, lhs
, 0);
3030 fprintf (dump_file
, " to ");
3031 print_generic_expr (dump_file
, op
, 0);
3032 fprintf (dump_file
, "\n");
3034 /* Have to set value numbers before insert, since insert is
3035 going to valueize the references in-place. */
3038 changed
|= set_ssa_val_to (vdef
, vdef
);
3041 /* Do not insert structure copies into the tables. */
3042 if (is_gimple_min_invariant (op
)
3043 || is_gimple_reg (op
))
3044 vn_reference_insert (lhs
, op
, vdef
, NULL
);
3046 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
3047 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
3051 /* We had a match, so value number the vdef to have the value
3052 number of the vuse it came from. */
3054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3055 fprintf (dump_file
, "Store matched earlier value,"
3056 "value numbering store vdefs to matching vuses.\n");
3058 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
3064 /* Visit and value number PHI, return true if the value number
3068 visit_phi (gimple phi
)
3070 bool changed
= false;
3072 tree sameval
= VN_TOP
;
3073 bool allsame
= true;
3076 /* TODO: We could check for this in init_sccvn, and replace this
3077 with a gcc_assert. */
3078 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
3079 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3081 /* See if all non-TOP arguments have the same value. TOP is
3082 equivalent to everything, so we can ignore it. */
3083 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3085 tree def
= PHI_ARG_DEF (phi
, i
);
3087 if (TREE_CODE (def
) == SSA_NAME
)
3088 def
= SSA_VAL (def
);
3091 if (sameval
== VN_TOP
)
3097 if (!expressions_equal_p (def
, sameval
))
3105 /* If all value numbered to the same value, the phi node has that
3109 if (is_gimple_min_invariant (sameval
))
3111 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
3112 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3116 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3117 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
3120 if (TREE_CODE (sameval
) == SSA_NAME
)
3121 return visit_copy (PHI_RESULT (phi
), sameval
);
3123 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
3126 /* Otherwise, see if it is equivalent to a phi node in this block. */
3127 result
= vn_phi_lookup (phi
);
3130 if (TREE_CODE (result
) == SSA_NAME
)
3131 changed
= visit_copy (PHI_RESULT (phi
), result
);
3133 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
3137 vn_phi_insert (phi
, PHI_RESULT (phi
));
3138 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
3139 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
3140 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
3146 /* Return true if EXPR contains constants. */
3149 expr_has_constants (tree expr
)
3151 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3154 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
3157 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
3158 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
3159 /* Constants inside reference ops are rarely interesting, but
3160 it can take a lot of looking to find them. */
3162 case tcc_declaration
:
3165 return is_gimple_min_invariant (expr
);
3170 /* Return true if STMT contains constants. */
3173 stmt_has_constants (gimple stmt
)
3177 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3180 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3182 case GIMPLE_TERNARY_RHS
:
3183 tem
= gimple_assign_rhs3 (stmt
);
3184 if (TREE_CODE (tem
) == SSA_NAME
)
3185 tem
= SSA_VAL (tem
);
3186 if (is_gimple_min_invariant (tem
))
3190 case GIMPLE_BINARY_RHS
:
3191 tem
= gimple_assign_rhs2 (stmt
);
3192 if (TREE_CODE (tem
) == SSA_NAME
)
3193 tem
= SSA_VAL (tem
);
3194 if (is_gimple_min_invariant (tem
))
3198 case GIMPLE_SINGLE_RHS
:
3199 /* Constants inside reference ops are rarely interesting, but
3200 it can take a lot of looking to find them. */
3201 case GIMPLE_UNARY_RHS
:
3202 tem
= gimple_assign_rhs1 (stmt
);
3203 if (TREE_CODE (tem
) == SSA_NAME
)
3204 tem
= SSA_VAL (tem
);
3205 return is_gimple_min_invariant (tem
);
3213 /* Replace SSA_NAMES in expr with their value numbers, and return the
3215 This is performed in place. */
3218 valueize_expr (tree expr
)
3220 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3223 TREE_OPERAND (expr
, 1) = vn_valueize (TREE_OPERAND (expr
, 1));
3226 TREE_OPERAND (expr
, 0) = vn_valueize (TREE_OPERAND (expr
, 0));
3233 /* Simplify the binary expression RHS, and return the result if
3237 simplify_binary_expression (gimple stmt
)
3239 tree result
= NULL_TREE
;
3240 tree op0
= gimple_assign_rhs1 (stmt
);
3241 tree op1
= gimple_assign_rhs2 (stmt
);
3242 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3244 /* This will not catch every single case we could combine, but will
3245 catch those with constants. The goal here is to simultaneously
3246 combine constants between expressions, but avoid infinite
3247 expansion of expressions during simplification. */
3248 if (TREE_CODE (op0
) == SSA_NAME
)
3250 if (VN_INFO (op0
)->has_constants
3251 || TREE_CODE_CLASS (code
) == tcc_comparison
3252 || code
== COMPLEX_EXPR
)
3253 op0
= valueize_expr (vn_get_expr_for (op0
));
3255 op0
= vn_valueize (op0
);
3258 if (TREE_CODE (op1
) == SSA_NAME
)
3260 if (VN_INFO (op1
)->has_constants
3261 || code
== COMPLEX_EXPR
)
3262 op1
= valueize_expr (vn_get_expr_for (op1
));
3264 op1
= vn_valueize (op1
);
3267 /* Pointer plus constant can be represented as invariant address.
3268 Do so to allow further propatation, see also tree forwprop. */
3269 if (code
== POINTER_PLUS_EXPR
3270 && tree_fits_uhwi_p (op1
)
3271 && TREE_CODE (op0
) == ADDR_EXPR
3272 && is_gimple_min_invariant (op0
))
3273 return build_invariant_address (TREE_TYPE (op0
),
3274 TREE_OPERAND (op0
, 0),
3275 tree_to_uhwi (op1
));
3277 /* Avoid folding if nothing changed. */
3278 if (op0
== gimple_assign_rhs1 (stmt
)
3279 && op1
== gimple_assign_rhs2 (stmt
))
3282 fold_defer_overflow_warnings ();
3284 result
= fold_binary (code
, gimple_expr_type (stmt
), op0
, op1
);
3286 STRIP_USELESS_TYPE_CONVERSION (result
);
3288 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
3291 /* Make sure result is not a complex expression consisting
3292 of operators of operators (IE (a + b) + (a + c))
3293 Otherwise, we will end up with unbounded expressions if
3294 fold does anything at all. */
3295 if (result
&& valid_gimple_rhs_p (result
))
3301 /* Simplify the unary expression RHS, and return the result if
3305 simplify_unary_expression (gimple stmt
)
3307 tree result
= NULL_TREE
;
3308 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
3309 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3311 /* We handle some tcc_reference codes here that are all
3312 GIMPLE_ASSIGN_SINGLE codes. */
3313 if (code
== REALPART_EXPR
3314 || code
== IMAGPART_EXPR
3315 || code
== VIEW_CONVERT_EXPR
3316 || code
== BIT_FIELD_REF
)
3317 op0
= TREE_OPERAND (op0
, 0);
3319 if (TREE_CODE (op0
) != SSA_NAME
)
3323 if (VN_INFO (op0
)->has_constants
)
3324 op0
= valueize_expr (vn_get_expr_for (op0
));
3325 else if (CONVERT_EXPR_CODE_P (code
)
3326 || code
== REALPART_EXPR
3327 || code
== IMAGPART_EXPR
3328 || code
== VIEW_CONVERT_EXPR
3329 || code
== BIT_FIELD_REF
)
3331 /* We want to do tree-combining on conversion-like expressions.
3332 Make sure we feed only SSA_NAMEs or constants to fold though. */
3333 tree tem
= valueize_expr (vn_get_expr_for (op0
));
3334 if (UNARY_CLASS_P (tem
)
3335 || BINARY_CLASS_P (tem
)
3336 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
3337 || TREE_CODE (tem
) == SSA_NAME
3338 || TREE_CODE (tem
) == CONSTRUCTOR
3339 || is_gimple_min_invariant (tem
))
3343 /* Avoid folding if nothing changed, but remember the expression. */
3344 if (op0
== orig_op0
)
3347 if (code
== BIT_FIELD_REF
)
3349 tree rhs
= gimple_assign_rhs1 (stmt
);
3350 result
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (rhs
),
3351 op0
, TREE_OPERAND (rhs
, 1), TREE_OPERAND (rhs
, 2));
3354 result
= fold_unary_ignore_overflow (code
, gimple_expr_type (stmt
), op0
);
3357 STRIP_USELESS_TYPE_CONVERSION (result
);
3358 if (valid_gimple_rhs_p (result
))
3365 /* Try to simplify RHS using equivalences and constant folding. */
3368 try_to_simplify (gimple stmt
)
3370 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3373 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3374 in this case, there is no point in doing extra work. */
3375 if (code
== SSA_NAME
)
3378 /* First try constant folding based on our current lattice. */
3379 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
);
3381 && (TREE_CODE (tem
) == SSA_NAME
3382 || is_gimple_min_invariant (tem
)))
3385 /* If that didn't work try combining multiple statements. */
3386 switch (TREE_CODE_CLASS (code
))
3389 /* Fallthrough for some unary codes that can operate on registers. */
3390 if (!(code
== REALPART_EXPR
3391 || code
== IMAGPART_EXPR
3392 || code
== VIEW_CONVERT_EXPR
3393 || code
== BIT_FIELD_REF
))
3395 /* We could do a little more with unary ops, if they expand
3396 into binary ops, but it's debatable whether it is worth it. */
3398 return simplify_unary_expression (stmt
);
3400 case tcc_comparison
:
3402 return simplify_binary_expression (stmt
);
3411 /* Visit and value number USE, return true if the value number
3415 visit_use (tree use
)
3417 bool changed
= false;
3418 gimple stmt
= SSA_NAME_DEF_STMT (use
);
3420 mark_use_processed (use
);
3422 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
3423 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3424 && !SSA_NAME_IS_DEFAULT_DEF (use
))
3426 fprintf (dump_file
, "Value numbering ");
3427 print_generic_expr (dump_file
, use
, 0);
3428 fprintf (dump_file
, " stmt = ");
3429 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3432 /* Handle uninitialized uses. */
3433 if (SSA_NAME_IS_DEFAULT_DEF (use
))
3434 changed
= set_ssa_val_to (use
, use
);
3437 if (gimple_code (stmt
) == GIMPLE_PHI
)
3438 changed
= visit_phi (stmt
);
3439 else if (gimple_has_volatile_ops (stmt
))
3440 changed
= defs_to_varying (stmt
);
3441 else if (is_gimple_assign (stmt
))
3443 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3444 tree lhs
= gimple_assign_lhs (stmt
);
3445 tree rhs1
= gimple_assign_rhs1 (stmt
);
3448 /* Shortcut for copies. Simplifying copies is pointless,
3449 since we copy the expression and value they represent. */
3450 if (code
== SSA_NAME
3451 && TREE_CODE (lhs
) == SSA_NAME
)
3453 changed
= visit_copy (lhs
, rhs1
);
3456 simplified
= try_to_simplify (stmt
);
3459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3461 fprintf (dump_file
, "RHS ");
3462 print_gimple_expr (dump_file
, stmt
, 0, 0);
3463 fprintf (dump_file
, " simplified to ");
3464 print_generic_expr (dump_file
, simplified
, 0);
3465 if (TREE_CODE (lhs
) == SSA_NAME
)
3466 fprintf (dump_file
, " has constants %d\n",
3467 expr_has_constants (simplified
));
3469 fprintf (dump_file
, "\n");
3472 /* Setting value numbers to constants will occasionally
3473 screw up phi congruence because constants are not
3474 uniquely associated with a single ssa name that can be
3477 && is_gimple_min_invariant (simplified
)
3478 && TREE_CODE (lhs
) == SSA_NAME
)
3480 VN_INFO (lhs
)->expr
= simplified
;
3481 VN_INFO (lhs
)->has_constants
= true;
3482 changed
= set_ssa_val_to (lhs
, simplified
);
3486 && TREE_CODE (simplified
) == SSA_NAME
3487 && TREE_CODE (lhs
) == SSA_NAME
)
3489 changed
= visit_copy (lhs
, simplified
);
3492 else if (simplified
)
3494 if (TREE_CODE (lhs
) == SSA_NAME
)
3496 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
3497 /* We have to unshare the expression or else
3498 valuizing may change the IL stream. */
3499 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
3502 else if (stmt_has_constants (stmt
)
3503 && TREE_CODE (lhs
) == SSA_NAME
)
3504 VN_INFO (lhs
)->has_constants
= true;
3505 else if (TREE_CODE (lhs
) == SSA_NAME
)
3507 /* We reset expr and constantness here because we may
3508 have been value numbering optimistically, and
3509 iterating. They may become non-constant in this case,
3510 even if they were optimistically constant. */
3512 VN_INFO (lhs
)->has_constants
= false;
3513 VN_INFO (lhs
)->expr
= NULL_TREE
;
3516 if ((TREE_CODE (lhs
) == SSA_NAME
3517 /* We can substitute SSA_NAMEs that are live over
3518 abnormal edges with their constant value. */
3519 && !(gimple_assign_copy_p (stmt
)
3520 && is_gimple_min_invariant (rhs1
))
3522 && is_gimple_min_invariant (simplified
))
3523 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3524 /* Stores or copies from SSA_NAMEs that are live over
3525 abnormal edges are a problem. */
3526 || (code
== SSA_NAME
3527 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
3528 changed
= defs_to_varying (stmt
);
3529 else if (REFERENCE_CLASS_P (lhs
)
3531 changed
= visit_reference_op_store (lhs
, rhs1
, stmt
);
3532 else if (TREE_CODE (lhs
) == SSA_NAME
)
3534 if ((gimple_assign_copy_p (stmt
)
3535 && is_gimple_min_invariant (rhs1
))
3537 && is_gimple_min_invariant (simplified
)))
3539 VN_INFO (lhs
)->has_constants
= true;
3541 changed
= set_ssa_val_to (lhs
, simplified
);
3543 changed
= set_ssa_val_to (lhs
, rhs1
);
3547 /* First try to lookup the simplified expression. */
3550 enum gimple_rhs_class rhs_class
;
3553 rhs_class
= get_gimple_rhs_class (TREE_CODE (simplified
));
3554 if ((rhs_class
== GIMPLE_UNARY_RHS
3555 || rhs_class
== GIMPLE_BINARY_RHS
3556 || rhs_class
== GIMPLE_TERNARY_RHS
)
3557 && valid_gimple_rhs_p (simplified
))
3559 tree result
= vn_nary_op_lookup (simplified
, NULL
);
3562 changed
= set_ssa_val_to (lhs
, result
);
3568 /* Otherwise visit the original statement. */
3569 switch (vn_get_stmt_kind (stmt
))
3572 changed
= visit_nary_op (lhs
, stmt
);
3575 changed
= visit_reference_op_load (lhs
, rhs1
, stmt
);
3578 changed
= defs_to_varying (stmt
);
3584 changed
= defs_to_varying (stmt
);
3586 else if (is_gimple_call (stmt
))
3588 tree lhs
= gimple_call_lhs (stmt
);
3590 /* ??? We could try to simplify calls. */
3592 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3594 if (stmt_has_constants (stmt
))
3595 VN_INFO (lhs
)->has_constants
= true;
3598 /* We reset expr and constantness here because we may
3599 have been value numbering optimistically, and
3600 iterating. They may become non-constant in this case,
3601 even if they were optimistically constant. */
3602 VN_INFO (lhs
)->has_constants
= false;
3603 VN_INFO (lhs
)->expr
= NULL_TREE
;
3606 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3608 changed
= defs_to_varying (stmt
);
3613 if (!gimple_call_internal_p (stmt
)
3614 && (/* Calls to the same function with the same vuse
3615 and the same operands do not necessarily return the same
3616 value, unless they're pure or const. */
3617 gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
)
3618 /* If calls have a vdef, subsequent calls won't have
3619 the same incoming vuse. So, if 2 calls with vdef have the
3620 same vuse, we know they're not subsequent.
3621 We can value number 2 calls to the same function with the
3622 same vuse and the same operands which are not subsequent
3623 the same, because there is no code in the program that can
3624 compare the 2 values... */
3625 || (gimple_vdef (stmt
)
3626 /* ... unless the call returns a pointer which does
3627 not alias with anything else. In which case the
3628 information that the values are distinct are encoded
3630 && !(gimple_call_return_flags (stmt
) & ERF_NOALIAS
))))
3631 changed
= visit_reference_op_call (lhs
, stmt
);
3633 changed
= defs_to_varying (stmt
);
3636 changed
= defs_to_varying (stmt
);
3642 /* Compare two operands by reverse postorder index */
3645 compare_ops (const void *pa
, const void *pb
)
3647 const tree opa
= *((const tree
*)pa
);
3648 const tree opb
= *((const tree
*)pb
);
3649 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
3650 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
3654 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
3655 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3656 else if (gimple_nop_p (opstmta
))
3658 else if (gimple_nop_p (opstmtb
))
3661 bba
= gimple_bb (opstmta
);
3662 bbb
= gimple_bb (opstmtb
);
3665 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3673 if (gimple_code (opstmta
) == GIMPLE_PHI
3674 && gimple_code (opstmtb
) == GIMPLE_PHI
)
3675 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3676 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
3678 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
3680 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
3681 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
3683 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
3685 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
3688 /* Sort an array containing members of a strongly connected component
3689 SCC so that the members are ordered by RPO number.
3690 This means that when the sort is complete, iterating through the
3691 array will give you the members in RPO order. */
3694 sort_scc (vec
<tree
> scc
)
3696 scc
.qsort (compare_ops
);
3699 /* Insert the no longer used nary ONARY to the hash INFO. */
3702 copy_nary (vn_nary_op_t onary
, vn_tables_t info
)
3704 size_t size
= sizeof_vn_nary_op (onary
->length
);
3705 vn_nary_op_t nary
= alloc_vn_nary_op_noinit (onary
->length
,
3706 &info
->nary_obstack
);
3707 memcpy (nary
, onary
, size
);
3708 vn_nary_op_insert_into (nary
, info
->nary
, false);
3711 /* Insert the no longer used phi OPHI to the hash INFO. */
3714 copy_phi (vn_phi_t ophi
, vn_tables_t info
)
3716 vn_phi_t phi
= (vn_phi_t
) pool_alloc (info
->phis_pool
);
3718 memcpy (phi
, ophi
, sizeof (*phi
));
3719 ophi
->phiargs
.create (0);
3720 slot
= info
->phis
.find_slot_with_hash (phi
, phi
->hashcode
, INSERT
);
3721 gcc_assert (!*slot
);
3725 /* Insert the no longer used reference OREF to the hash INFO. */
3728 copy_reference (vn_reference_t oref
, vn_tables_t info
)
3731 vn_reference_s
**slot
;
3732 ref
= (vn_reference_t
) pool_alloc (info
->references_pool
);
3733 memcpy (ref
, oref
, sizeof (*ref
));
3734 oref
->operands
.create (0);
3735 slot
= info
->references
.find_slot_with_hash (ref
, ref
->hashcode
, INSERT
);
3737 free_reference (*slot
);
3741 /* Process a strongly connected component in the SSA graph. */
3744 process_scc (vec
<tree
> scc
)
3748 unsigned int iterations
= 0;
3749 bool changed
= true;
3750 vn_nary_op_iterator_type hin
;
3751 vn_phi_iterator_type hip
;
3752 vn_reference_iterator_type hir
;
3757 /* If the SCC has a single member, just visit it. */
3758 if (scc
.length () == 1)
3761 if (VN_INFO (use
)->use_processed
)
3763 /* We need to make sure it doesn't form a cycle itself, which can
3764 happen for self-referential PHI nodes. In that case we would
3765 end up inserting an expression with VN_TOP operands into the
3766 valid table which makes us derive bogus equivalences later.
3767 The cheapest way to check this is to assume it for all PHI nodes. */
3768 if (gimple_code (SSA_NAME_DEF_STMT (use
)) == GIMPLE_PHI
)
3769 /* Fallthru to iteration. */ ;
3777 /* Iterate over the SCC with the optimistic table until it stops
3779 current_info
= optimistic_info
;
3784 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3785 fprintf (dump_file
, "Starting iteration %d\n", iterations
);
3786 /* As we are value-numbering optimistically we have to
3787 clear the expression tables and the simplified expressions
3788 in each iteration until we converge. */
3789 optimistic_info
->nary
.empty ();
3790 optimistic_info
->phis
.empty ();
3791 optimistic_info
->references
.empty ();
3792 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
3793 gcc_obstack_init (&optimistic_info
->nary_obstack
);
3794 empty_alloc_pool (optimistic_info
->phis_pool
);
3795 empty_alloc_pool (optimistic_info
->references_pool
);
3796 FOR_EACH_VEC_ELT (scc
, i
, var
)
3797 VN_INFO (var
)->expr
= NULL_TREE
;
3798 FOR_EACH_VEC_ELT (scc
, i
, var
)
3799 changed
|= visit_use (var
);
3802 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
3804 /* Finally, copy the contents of the no longer used optimistic
3805 table to the valid table. */
3806 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->nary
, nary
, vn_nary_op_t
, hin
)
3807 copy_nary (nary
, valid_info
);
3808 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->phis
, phi
, vn_phi_t
, hip
)
3809 copy_phi (phi
, valid_info
);
3810 FOR_EACH_HASH_TABLE_ELEMENT (optimistic_info
->references
,
3811 ref
, vn_reference_t
, hir
)
3812 copy_reference (ref
, valid_info
);
3814 current_info
= valid_info
;
3818 /* Pop the components of the found SCC for NAME off the SCC stack
3819 and process them. Returns true if all went well, false if
3820 we run into resource limits. */
3823 extract_and_process_scc_for_name (tree name
)
3828 /* Found an SCC, pop the components off the SCC stack and
3832 x
= sccstack
.pop ();
3834 VN_INFO (x
)->on_sccstack
= false;
3836 } while (x
!= name
);
3838 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
3840 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
3843 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
3844 "SCC size %u exceeding %u\n", scc
.length (),
3845 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
3850 if (scc
.length () > 1)
3853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3854 print_scc (dump_file
, scc
);
3861 /* Depth first search on NAME to discover and process SCC's in the SSA
3863 Execution of this algorithm relies on the fact that the SCC's are
3864 popped off the stack in topological order.
3865 Returns true if successful, false if we stopped processing SCC's due
3866 to resource constraints. */
3871 vec
<ssa_op_iter
> itervec
= vNULL
;
3872 vec
<tree
> namevec
= vNULL
;
3873 use_operand_p usep
= NULL
;
3880 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
3881 VN_INFO (name
)->visited
= true;
3882 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
3884 sccstack
.safe_push (name
);
3885 VN_INFO (name
)->on_sccstack
= true;
3886 defstmt
= SSA_NAME_DEF_STMT (name
);
3888 /* Recursively DFS on our operands, looking for SCC's. */
3889 if (!gimple_nop_p (defstmt
))
3891 /* Push a new iterator. */
3892 if (gimple_code (defstmt
) == GIMPLE_PHI
)
3893 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
3895 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
3898 clear_and_done_ssa_iter (&iter
);
3902 /* If we are done processing uses of a name, go up the stack
3903 of iterators and process SCCs as we found them. */
3904 if (op_iter_done (&iter
))
3906 /* See if we found an SCC. */
3907 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
3908 if (!extract_and_process_scc_for_name (name
))
3915 /* Check if we are done. */
3916 if (namevec
.is_empty ())
3923 /* Restore the last use walker and continue walking there. */
3925 name
= namevec
.pop ();
3926 memcpy (&iter
, &itervec
.last (),
3927 sizeof (ssa_op_iter
));
3929 goto continue_walking
;
3932 use
= USE_FROM_PTR (usep
);
3934 /* Since we handle phi nodes, we will sometimes get
3935 invariants in the use expression. */
3936 if (TREE_CODE (use
) == SSA_NAME
)
3938 if (! (VN_INFO (use
)->visited
))
3940 /* Recurse by pushing the current use walking state on
3941 the stack and starting over. */
3942 itervec
.safe_push (iter
);
3943 namevec
.safe_push (name
);
3948 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3949 VN_INFO (use
)->low
);
3951 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3952 && VN_INFO (use
)->on_sccstack
)
3954 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3955 VN_INFO (name
)->low
);
3959 usep
= op_iter_next_use (&iter
);
3963 /* Allocate a value number table. */
3966 allocate_vn_table (vn_tables_t table
)
3968 table
->phis
.create (23);
3969 table
->nary
.create (23);
3970 table
->references
.create (23);
3972 gcc_obstack_init (&table
->nary_obstack
);
3973 table
->phis_pool
= create_alloc_pool ("VN phis",
3974 sizeof (struct vn_phi_s
),
3976 table
->references_pool
= create_alloc_pool ("VN references",
3977 sizeof (struct vn_reference_s
),
3981 /* Free a value number table. */
3984 free_vn_table (vn_tables_t table
)
3986 table
->phis
.dispose ();
3987 table
->nary
.dispose ();
3988 table
->references
.dispose ();
3989 obstack_free (&table
->nary_obstack
, NULL
);
3990 free_alloc_pool (table
->phis_pool
);
3991 free_alloc_pool (table
->references_pool
);
3999 int *rpo_numbers_temp
;
4001 calculate_dominance_info (CDI_DOMINATORS
);
4002 sccstack
.create (0);
4003 constant_to_value_id
.create (23);
4005 constant_value_ids
= BITMAP_ALLOC (NULL
);
4010 vn_ssa_aux_table
.create (num_ssa_names
+ 1);
4011 /* VEC_alloc doesn't actually grow it to the right size, it just
4012 preallocates the space to do so. */
4013 vn_ssa_aux_table
.safe_grow_cleared (num_ssa_names
+ 1);
4014 gcc_obstack_init (&vn_ssa_aux_obstack
);
4016 shared_lookup_phiargs
.create (0);
4017 shared_lookup_references
.create (0);
4018 rpo_numbers
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
4020 XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
4021 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
4023 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4024 the i'th block in RPO order is bb. We want to map bb's to RPO
4025 numbers, so we need to rearrange this array. */
4026 for (j
= 0; j
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; j
++)
4027 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
4029 XDELETE (rpo_numbers_temp
);
4031 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
4033 /* Create the VN_INFO structures, and initialize value numbers to
4035 for (i
= 0; i
< num_ssa_names
; i
++)
4037 tree name
= ssa_name (i
);
4040 VN_INFO_GET (name
)->valnum
= VN_TOP
;
4041 VN_INFO (name
)->expr
= NULL_TREE
;
4042 VN_INFO (name
)->value_id
= 0;
4046 renumber_gimple_stmt_uids ();
4048 /* Create the valid and optimistic value numbering tables. */
4049 valid_info
= XCNEW (struct vn_tables_s
);
4050 allocate_vn_table (valid_info
);
4051 optimistic_info
= XCNEW (struct vn_tables_s
);
4052 allocate_vn_table (optimistic_info
);
4060 constant_to_value_id
.dispose ();
4061 BITMAP_FREE (constant_value_ids
);
4062 shared_lookup_phiargs
.release ();
4063 shared_lookup_references
.release ();
4064 XDELETEVEC (rpo_numbers
);
4066 for (i
= 0; i
< num_ssa_names
; i
++)
4068 tree name
= ssa_name (i
);
4070 && VN_INFO (name
)->needs_insertion
)
4071 release_ssa_name (name
);
4073 obstack_free (&vn_ssa_aux_obstack
, NULL
);
4074 vn_ssa_aux_table
.release ();
4076 sccstack
.release ();
4077 free_vn_table (valid_info
);
4078 XDELETE (valid_info
);
4079 free_vn_table (optimistic_info
);
4080 XDELETE (optimistic_info
);
4083 /* Set *ID according to RESULT. */
4086 set_value_id_for_result (tree result
, unsigned int *id
)
4088 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4089 *id
= VN_INFO (result
)->value_id
;
4090 else if (result
&& is_gimple_min_invariant (result
))
4091 *id
= get_or_alloc_constant_value_id (result
);
4093 *id
= get_next_value_id ();
4096 /* Set the value ids in the valid hash tables. */
4099 set_hashtable_value_ids (void)
4101 vn_nary_op_iterator_type hin
;
4102 vn_phi_iterator_type hip
;
4103 vn_reference_iterator_type hir
;
4108 /* Now set the value ids of the things we had put in the hash
4111 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4112 set_value_id_for_result (vno
->result
, &vno
->value_id
);
4114 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->phis
, vp
, vn_phi_t
, hip
)
4115 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4117 FOR_EACH_HASH_TABLE_ELEMENT (valid_info
->references
, vr
, vn_reference_t
, hir
)
4118 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4121 /* Do SCCVN. Returns true if it finished, false if we bailed out
4122 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4123 how we use the alias oracle walking during the VN process. */
4126 run_scc_vn (vn_lookup_kind default_vn_walk_kind_
)
4131 default_vn_walk_kind
= default_vn_walk_kind_
;
4134 current_info
= valid_info
;
4136 for (param
= DECL_ARGUMENTS (current_function_decl
);
4138 param
= DECL_CHAIN (param
))
4140 tree def
= ssa_default_def (cfun
, param
);
4142 VN_INFO (def
)->valnum
= def
;
4145 for (i
= 1; i
< num_ssa_names
; ++i
)
4147 tree name
= ssa_name (i
);
4149 && VN_INFO (name
)->visited
== false
4150 && !has_zero_uses (name
))
4158 /* Initialize the value ids. */
4160 for (i
= 1; i
< num_ssa_names
; ++i
)
4162 tree name
= ssa_name (i
);
4166 info
= VN_INFO (name
);
4167 if (info
->valnum
== name
4168 || info
->valnum
== VN_TOP
)
4169 info
->value_id
= get_next_value_id ();
4170 else if (is_gimple_min_invariant (info
->valnum
))
4171 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
4175 for (i
= 1; i
< num_ssa_names
; ++i
)
4177 tree name
= ssa_name (i
);
4181 info
= VN_INFO (name
);
4182 if (TREE_CODE (info
->valnum
) == SSA_NAME
4183 && info
->valnum
!= name
4184 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
4185 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
4188 set_hashtable_value_ids ();
4190 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4192 fprintf (dump_file
, "Value numbers:\n");
4193 for (i
= 0; i
< num_ssa_names
; i
++)
4195 tree name
= ssa_name (i
);
4197 && VN_INFO (name
)->visited
4198 && SSA_VAL (name
) != name
)
4200 print_generic_expr (dump_file
, name
, 0);
4201 fprintf (dump_file
, " = ");
4202 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
4203 fprintf (dump_file
, "\n");
4211 /* Return the maximum value id we have ever seen. */
4214 get_max_value_id (void)
4216 return next_value_id
;
4219 /* Return the next unique value id. */
4222 get_next_value_id (void)
4224 return next_value_id
++;
4228 /* Compare two expressions E1 and E2 and return true if they are equal. */
4231 expressions_equal_p (tree e1
, tree e2
)
4233 /* The obvious case. */
4237 /* If only one of them is null, they cannot be equal. */
4241 /* Now perform the actual comparison. */
4242 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4243 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4250 /* Return true if the nary operation NARY may trap. This is a copy
4251 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4254 vn_nary_may_trap (vn_nary_op_t nary
)
4257 tree rhs2
= NULL_TREE
;
4258 bool honor_nans
= false;
4259 bool honor_snans
= false;
4260 bool fp_operation
= false;
4261 bool honor_trapv
= false;
4265 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4266 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4267 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4270 fp_operation
= FLOAT_TYPE_P (type
);
4273 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4274 honor_snans
= flag_signaling_nans
!= 0;
4276 else if (INTEGRAL_TYPE_P (type
)
4277 && TYPE_OVERFLOW_TRAPS (type
))
4280 if (nary
->length
>= 2)
4282 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4284 honor_nans
, honor_snans
, rhs2
,
4290 for (i
= 0; i
< nary
->length
; ++i
)
4291 if (tree_could_trap_p (nary
->op
[i
]))