1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
37 #include "tree-iterator.h"
39 #include "alloc-pool.h"
40 #include "tree-pass.h"
43 #include "langhooks.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-sccvn.h"
49 /* This algorithm is based on the SCC algorithm presented by Keith
50 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
51 (http://citeseer.ist.psu.edu/41805.html). In
52 straight line code, it is equivalent to a regular hash based value
53 numbering that is performed in reverse postorder.
55 For code with cycles, there are two alternatives, both of which
56 require keeping the hashtables separate from the actual list of
57 value numbers for SSA names.
59 1. Iterate value numbering in an RPO walk of the blocks, removing
60 all the entries from the hashtable after each iteration (but
61 keeping the SSA name->value number mapping between iterations).
62 Iterate until it does not change.
64 2. Perform value numbering as part of an SCC walk on the SSA graph,
65 iterating only the cycles in the SSA graph until they do not change
66 (using a separate, optimistic hashtable for value numbering the SCC
69 The second is not just faster in practice (because most SSA graph
70 cycles do not involve all the variables in the graph), it also has
73 One of these nice properties is that when we pop an SCC off the
74 stack, we are guaranteed to have processed all the operands coming from
75 *outside of that SCC*, so we do not need to do anything special to
76 ensure they have value numbers.
78 Another nice property is that the SCC walk is done as part of a DFS
79 of the SSA graph, which makes it easy to perform combining and
80 simplifying operations at the same time.
82 The code below is deliberately written in a way that makes it easy
83 to separate the SCC walk from the other work it does.
85 In order to propagate constants through the code, we track which
86 expressions contain constants, and use those while folding. In
87 theory, we could also track expressions whose value numbers are
88 replaced, in case we end up folding based on expression
91 In order to value number memory, we assign value numbers to vuses.
92 This enables us to note that, for example, stores to the same
93 address of the same value from the same starting memory states are
97 1. We can iterate only the changing portions of the SCC's, but
98 I have not seen an SCC big enough for this to be a win.
99 2. If you differentiate between phi nodes for loops and phi nodes
100 for if-then-else, you can properly consider phi nodes in different
101 blocks for equivalence.
102 3. We could value number vuses in more cases, particularly, whole
106 /* The set of hashtables and alloc_pool's for their items. */
108 typedef struct vn_tables_s
113 struct obstack nary_obstack
;
114 alloc_pool phis_pool
;
115 alloc_pool references_pool
;
118 static htab_t constant_to_value_id
;
119 static bitmap constant_value_ids
;
122 /* Valid hashtables storing information we have proven to be
125 static vn_tables_t valid_info
;
127 /* Optimistic hashtables storing information we are making assumptions about
128 during iterations. */
130 static vn_tables_t optimistic_info
;
132 /* Pointer to the set of hashtables that is currently being used.
133 Should always point to either the optimistic_info, or the
136 static vn_tables_t current_info
;
139 /* Reverse post order index for each basic block. */
141 static int *rpo_numbers
;
143 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
145 /* This represents the top of the VN lattice, which is the universal
150 /* Unique counter for our value ids. */
152 static unsigned int next_value_id
;
154 /* Next DFS number and the stack for strongly connected component
157 static unsigned int next_dfs_num
;
158 static VEC (tree
, heap
) *sccstack
;
160 static bool may_insert
;
163 DEF_VEC_P(vn_ssa_aux_t
);
164 DEF_VEC_ALLOC_P(vn_ssa_aux_t
, heap
);
166 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
167 are allocated on an obstack for locality reasons, and to free them
168 without looping over the VEC. */
170 static VEC (vn_ssa_aux_t
, heap
) *vn_ssa_aux_table
;
171 static struct obstack vn_ssa_aux_obstack
;
173 /* Return the value numbering information for a given SSA name. */
178 vn_ssa_aux_t res
= VEC_index (vn_ssa_aux_t
, vn_ssa_aux_table
,
179 SSA_NAME_VERSION (name
));
184 /* Set the value numbering info for a given SSA name to a given
188 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
190 VEC_replace (vn_ssa_aux_t
, vn_ssa_aux_table
,
191 SSA_NAME_VERSION (name
), value
);
194 /* Initialize the value numbering info for a given SSA name.
195 This should be called just once for every SSA name. */
198 VN_INFO_GET (tree name
)
200 vn_ssa_aux_t newinfo
;
202 newinfo
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
203 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
204 if (SSA_NAME_VERSION (name
) >= VEC_length (vn_ssa_aux_t
, vn_ssa_aux_table
))
205 VEC_safe_grow (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
,
206 SSA_NAME_VERSION (name
) + 1);
207 VEC_replace (vn_ssa_aux_t
, vn_ssa_aux_table
,
208 SSA_NAME_VERSION (name
), newinfo
);
213 /* Get the representative expression for the SSA_NAME NAME. Returns
214 the representative SSA_NAME if there is no expression associated with it. */
217 vn_get_expr_for (tree name
)
219 vn_ssa_aux_t vn
= VN_INFO (name
);
221 tree expr
= NULL_TREE
;
223 if (vn
->valnum
== VN_TOP
)
226 /* If the value-number is a constant it is the representative
228 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
231 /* Get to the information of the value of this SSA_NAME. */
232 vn
= VN_INFO (vn
->valnum
);
234 /* If the value-number is a constant it is the representative
236 if (TREE_CODE (vn
->valnum
) != SSA_NAME
)
239 /* Else if we have an expression, return it. */
240 if (vn
->expr
!= NULL_TREE
)
243 /* Otherwise use the defining statement to build the expression. */
244 def_stmt
= SSA_NAME_DEF_STMT (vn
->valnum
);
246 /* If the value number is a default-definition or a PHI result
248 if (gimple_nop_p (def_stmt
)
249 || gimple_code (def_stmt
) == GIMPLE_PHI
)
252 if (!is_gimple_assign (def_stmt
))
255 /* FIXME tuples. This is incomplete and likely will miss some
257 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)))
260 if ((gimple_assign_rhs_code (def_stmt
) == VIEW_CONVERT_EXPR
261 || gimple_assign_rhs_code (def_stmt
) == REALPART_EXPR
262 || gimple_assign_rhs_code (def_stmt
) == IMAGPART_EXPR
)
263 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
264 expr
= fold_build1 (gimple_assign_rhs_code (def_stmt
),
265 gimple_expr_type (def_stmt
),
266 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
270 expr
= fold_build1 (gimple_assign_rhs_code (def_stmt
),
271 gimple_expr_type (def_stmt
),
272 gimple_assign_rhs1 (def_stmt
));
276 expr
= fold_build2 (gimple_assign_rhs_code (def_stmt
),
277 gimple_expr_type (def_stmt
),
278 gimple_assign_rhs1 (def_stmt
),
279 gimple_assign_rhs2 (def_stmt
));
284 if (expr
== NULL_TREE
)
287 /* Cache the expression. */
294 /* Free a phi operation structure VP. */
299 vn_phi_t phi
= (vn_phi_t
) vp
;
300 VEC_free (tree
, heap
, phi
->phiargs
);
303 /* Free a reference operation structure VP. */
306 free_reference (void *vp
)
308 vn_reference_t vr
= (vn_reference_t
) vp
;
309 VEC_free (vn_reference_op_s
, heap
, vr
->operands
);
312 /* Hash table equality function for vn_constant_t. */
315 vn_constant_eq (const void *p1
, const void *p2
)
317 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
318 const struct vn_constant_s
*vc2
= (const struct vn_constant_s
*) p2
;
320 if (vc1
->hashcode
!= vc2
->hashcode
)
323 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
326 /* Hash table hash function for vn_constant_t. */
329 vn_constant_hash (const void *p1
)
331 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
332 return vc1
->hashcode
;
335 /* Lookup a value id for CONSTANT and return it. If it does not
339 get_constant_value_id (tree constant
)
342 struct vn_constant_s vc
;
344 vc
.hashcode
= vn_hash_constant_with_type (constant
);
345 vc
.constant
= constant
;
346 slot
= htab_find_slot_with_hash (constant_to_value_id
, &vc
,
347 vc
.hashcode
, NO_INSERT
);
349 return ((vn_constant_t
)*slot
)->value_id
;
353 /* Lookup a value id for CONSTANT, and if it does not exist, create a
354 new one and return it. If it does exist, return it. */
357 get_or_alloc_constant_value_id (tree constant
)
360 struct vn_constant_s vc
;
363 vc
.hashcode
= vn_hash_constant_with_type (constant
);
364 vc
.constant
= constant
;
365 slot
= htab_find_slot_with_hash (constant_to_value_id
, &vc
,
366 vc
.hashcode
, INSERT
);
368 return ((vn_constant_t
)*slot
)->value_id
;
370 vcp
= XNEW (struct vn_constant_s
);
371 vcp
->hashcode
= vc
.hashcode
;
372 vcp
->constant
= constant
;
373 vcp
->value_id
= get_next_value_id ();
374 *slot
= (void *) vcp
;
375 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
376 return vcp
->value_id
;
379 /* Return true if V is a value id for a constant. */
382 value_id_constant_p (unsigned int v
)
384 return bitmap_bit_p (constant_value_ids
, v
);
387 /* Compare two reference operands P1 and P2 for equality. Return true if
388 they are equal, and false otherwise. */
391 vn_reference_op_eq (const void *p1
, const void *p2
)
393 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
394 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
396 return vro1
->opcode
== vro2
->opcode
397 && types_compatible_p (vro1
->type
, vro2
->type
)
398 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
399 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
400 && expressions_equal_p (vro1
->op2
, vro2
->op2
);
403 /* Compute the hash for a reference operand VRO1. */
406 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, hashval_t result
)
408 result
= iterative_hash_hashval_t (vro1
->opcode
, result
);
410 result
= iterative_hash_expr (vro1
->op0
, result
);
412 result
= iterative_hash_expr (vro1
->op1
, result
);
414 result
= iterative_hash_expr (vro1
->op2
, result
);
418 /* Return the hashcode for a given reference operation P1. */
421 vn_reference_hash (const void *p1
)
423 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
424 return vr1
->hashcode
;
427 /* Compute a hash for the reference operation VR1 and return it. */
430 vn_reference_compute_hash (const vn_reference_t vr1
)
432 hashval_t result
= 0;
434 vn_reference_op_t vro
;
436 for (i
= 0; VEC_iterate (vn_reference_op_s
, vr1
->operands
, i
, vro
); i
++)
437 result
= vn_reference_op_compute_hash (vro
, result
);
439 result
+= SSA_NAME_VERSION (vr1
->vuse
);
444 /* Return true if reference operations P1 and P2 are equivalent. This
445 means they have the same set of operands and vuses. */
448 vn_reference_eq (const void *p1
, const void *p2
)
451 vn_reference_op_t vro
;
453 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
454 const_vn_reference_t
const vr2
= (const_vn_reference_t
) p2
;
455 if (vr1
->hashcode
!= vr2
->hashcode
)
458 /* Early out if this is not a hash collision. */
459 if (vr1
->hashcode
!= vr2
->hashcode
)
462 /* The VOP needs to be the same. */
463 if (vr1
->vuse
!= vr2
->vuse
)
466 /* If the operands are the same we are done. */
467 if (vr1
->operands
== vr2
->operands
)
470 /* We require that address operands be canonicalized in a way that
471 two memory references will have the same operands if they are
473 if (VEC_length (vn_reference_op_s
, vr1
->operands
)
474 != VEC_length (vn_reference_op_s
, vr2
->operands
))
477 for (i
= 0; VEC_iterate (vn_reference_op_s
, vr1
->operands
, i
, vro
); i
++)
478 if (!vn_reference_op_eq (VEC_index (vn_reference_op_s
, vr2
->operands
, i
),
485 /* Copy the operations present in load/store REF into RESULT, a vector of
486 vn_reference_op_s's. */
489 copy_reference_ops_from_ref (tree ref
, VEC(vn_reference_op_s
, heap
) **result
)
491 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
493 vn_reference_op_s temp
;
496 base
= TMR_SYMBOL (ref
) ? TMR_SYMBOL (ref
) : TMR_BASE (ref
);
498 base
= build_int_cst (ptr_type_node
, 0);
500 memset (&temp
, 0, sizeof (temp
));
501 /* We do not care for spurious type qualifications. */
502 temp
.type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
503 temp
.opcode
= TREE_CODE (ref
);
504 temp
.op0
= TMR_INDEX (ref
);
505 temp
.op1
= TMR_STEP (ref
);
506 temp
.op2
= TMR_OFFSET (ref
);
507 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
509 memset (&temp
, 0, sizeof (temp
));
510 temp
.type
= NULL_TREE
;
511 temp
.opcode
= TREE_CODE (base
);
513 temp
.op1
= TMR_ORIGINAL (ref
);
514 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
518 /* For non-calls, store the information that makes up the address. */
522 vn_reference_op_s temp
;
524 memset (&temp
, 0, sizeof (temp
));
525 /* We do not care for spurious type qualifications. */
526 temp
.type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
527 temp
.opcode
= TREE_CODE (ref
);
531 case ALIGN_INDIRECT_REF
:
533 /* The only operand is the address, which gets its own
534 vn_reference_op_s structure. */
536 case MISALIGNED_INDIRECT_REF
:
537 temp
.op0
= TREE_OPERAND (ref
, 1);
540 /* Record bits and position. */
541 temp
.op0
= TREE_OPERAND (ref
, 1);
542 temp
.op1
= TREE_OPERAND (ref
, 2);
545 /* The field decl is enough to unambiguously specify the field,
546 a matching type is not necessary and a mismatching type
547 is always a spurious difference. */
548 temp
.type
= NULL_TREE
;
549 temp
.op0
= TREE_OPERAND (ref
, 1);
550 temp
.op1
= TREE_OPERAND (ref
, 2);
551 /* If this is a reference to a union member, record the union
552 member size as operand. Do so only if we are doing
553 expression insertion (during FRE), as PRE currently gets
554 confused with this. */
556 && temp
.op1
== NULL_TREE
557 && TREE_CODE (DECL_CONTEXT (temp
.op0
)) == UNION_TYPE
558 && integer_zerop (DECL_FIELD_OFFSET (temp
.op0
))
559 && integer_zerop (DECL_FIELD_BIT_OFFSET (temp
.op0
))
560 && host_integerp (DECL_SIZE (temp
.op0
), 0))
561 temp
.op0
= DECL_SIZE (temp
.op0
);
563 case ARRAY_RANGE_REF
:
565 /* Record index as operand. */
566 temp
.op0
= TREE_OPERAND (ref
, 1);
567 /* Always record lower bounds and element size. */
568 temp
.op1
= array_ref_low_bound (ref
);
569 temp
.op2
= array_ref_element_size (ref
);
585 if (is_gimple_min_invariant (ref
))
591 /* These are only interesting for their operands, their
592 existence, and their type. They will never be the last
593 ref in the chain of references (IE they require an
594 operand), so we don't have to put anything
595 for op* as it will be handled by the iteration */
598 case VIEW_CONVERT_EXPR
:
603 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
605 if (REFERENCE_CLASS_P (ref
)
606 || (TREE_CODE (ref
) == ADDR_EXPR
607 && !is_gimple_min_invariant (ref
)))
608 ref
= TREE_OPERAND (ref
, 0);
614 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
615 operands in *OPS, the reference alias set SET and the reference type TYPE.
616 Return true if something useful was produced. */
619 ao_ref_init_from_vn_reference (ao_ref
*ref
,
620 alias_set_type set
, tree type
,
621 VEC (vn_reference_op_s
, heap
) *ops
)
623 vn_reference_op_t op
;
625 tree base
= NULL_TREE
;
627 HOST_WIDE_INT offset
= 0;
628 HOST_WIDE_INT max_size
;
629 HOST_WIDE_INT size
= -1;
630 tree size_tree
= NULL_TREE
;
632 /* First get the final access size from just the outermost expression. */
633 op
= VEC_index (vn_reference_op_s
, ops
, 0);
634 if (op
->opcode
== COMPONENT_REF
)
636 if (TREE_CODE (op
->op0
) == INTEGER_CST
)
639 size_tree
= DECL_SIZE (op
->op0
);
641 else if (op
->opcode
== BIT_FIELD_REF
)
645 enum machine_mode mode
= TYPE_MODE (type
);
647 size_tree
= TYPE_SIZE (type
);
649 size
= GET_MODE_BITSIZE (mode
);
651 if (size_tree
!= NULL_TREE
)
653 if (!host_integerp (size_tree
, 1))
656 size
= TREE_INT_CST_LOW (size_tree
);
659 /* Initially, maxsize is the same as the accessed element size.
660 In the following it will only grow (or become -1). */
663 /* Compute cumulative bit-offset for nested component-refs and array-refs,
664 and find the ultimate containing object. */
665 for (i
= 0; VEC_iterate (vn_reference_op_s
, ops
, i
, op
); ++i
)
669 /* These may be in the reference ops, but we cannot do anything
670 sensible with them here. */
675 /* Record the base objects. */
676 case ALIGN_INDIRECT_REF
:
678 *op0_p
= build1 (op
->opcode
, op
->type
, NULL_TREE
);
679 op0_p
= &TREE_OPERAND (*op0_p
, 0);
682 case MISALIGNED_INDIRECT_REF
:
683 *op0_p
= build2 (MISALIGNED_INDIRECT_REF
, op
->type
,
685 op0_p
= &TREE_OPERAND (*op0_p
, 0);
695 /* And now the usual component-reference style ops. */
697 offset
+= tree_low_cst (op
->op1
, 0);
702 tree field
= op
->op0
;
703 /* We do not have a complete COMPONENT_REF tree here so we
704 cannot use component_ref_field_offset. Do the interesting
707 /* Our union trick, done for offset zero only. */
708 if (TREE_CODE (field
) == INTEGER_CST
)
711 || !host_integerp (DECL_FIELD_OFFSET (field
), 1))
715 offset
+= (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field
))
717 offset
+= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field
));
722 case ARRAY_RANGE_REF
:
724 /* We recorded the lower bound and the element size. */
725 if (!host_integerp (op
->op0
, 0)
726 || !host_integerp (op
->op1
, 0)
727 || !host_integerp (op
->op2
, 0))
731 HOST_WIDE_INT hindex
= TREE_INT_CST_LOW (op
->op0
);
732 hindex
-= TREE_INT_CST_LOW (op
->op1
);
733 hindex
*= TREE_INT_CST_LOW (op
->op2
);
734 hindex
*= BITS_PER_UNIT
;
746 case VIEW_CONVERT_EXPR
:
763 if (base
== NULL_TREE
)
766 ref
->ref
= NULL_TREE
;
768 ref
->offset
= offset
;
770 ref
->max_size
= max_size
;
771 ref
->ref_alias_set
= set
;
772 ref
->base_alias_set
= -1;
777 /* Copy the operations present in load/store/call REF into RESULT, a vector of
778 vn_reference_op_s's. */
781 copy_reference_ops_from_call (gimple call
,
782 VEC(vn_reference_op_s
, heap
) **result
)
784 vn_reference_op_s temp
;
787 /* Copy the type, opcode, function being called and static chain. */
788 memset (&temp
, 0, sizeof (temp
));
789 temp
.type
= gimple_call_return_type (call
);
790 temp
.opcode
= CALL_EXPR
;
791 temp
.op0
= gimple_call_fn (call
);
792 temp
.op1
= gimple_call_chain (call
);
793 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
795 /* Copy the call arguments. As they can be references as well,
796 just chain them together. */
797 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
799 tree callarg
= gimple_call_arg (call
, i
);
800 copy_reference_ops_from_ref (callarg
, result
);
804 /* Create a vector of vn_reference_op_s structures from REF, a
805 REFERENCE_CLASS_P tree. The vector is not shared. */
807 static VEC(vn_reference_op_s
, heap
) *
808 create_reference_ops_from_ref (tree ref
)
810 VEC (vn_reference_op_s
, heap
) *result
= NULL
;
812 copy_reference_ops_from_ref (ref
, &result
);
816 /* Create a vector of vn_reference_op_s structures from CALL, a
817 call statement. The vector is not shared. */
819 static VEC(vn_reference_op_s
, heap
) *
820 create_reference_ops_from_call (gimple call
)
822 VEC (vn_reference_op_s
, heap
) *result
= NULL
;
824 copy_reference_ops_from_call (call
, &result
);
828 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
829 *I_P to point to the last element of the replacement. */
831 vn_reference_fold_indirect (VEC (vn_reference_op_s
, heap
) **ops
,
834 VEC(vn_reference_op_s
, heap
) *mem
= NULL
;
835 vn_reference_op_t op
;
836 unsigned int i
= *i_p
;
839 /* Get ops for the addressed object. */
840 op
= VEC_index (vn_reference_op_s
, *ops
, i
);
841 /* ??? If this is our usual typeof &ARRAY vs. &ARRAY[0] problem, work
842 around it to avoid later ICEs. */
843 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op
->op0
, 0))) == ARRAY_TYPE
844 && TREE_CODE (TREE_TYPE (TREE_TYPE (op
->op0
))) != ARRAY_TYPE
)
846 vn_reference_op_s aref
;
848 aref
.type
= TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (op
->op0
)));
849 aref
.opcode
= ARRAY_REF
;
850 aref
.op0
= integer_zero_node
;
851 if ((dom
= TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (op
->op0
, 0))))
852 && TYPE_MIN_VALUE (dom
))
853 aref
.op0
= TYPE_MIN_VALUE (dom
);
855 aref
.op2
= TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (op
->op0
)));
856 VEC_safe_push (vn_reference_op_s
, heap
, mem
, &aref
);
858 copy_reference_ops_from_ref (TREE_OPERAND (op
->op0
, 0), &mem
);
860 /* Do the replacement - we should have at least one op in mem now. */
861 if (VEC_length (vn_reference_op_s
, mem
) == 1)
863 VEC_replace (vn_reference_op_s
, *ops
, i
- 1,
864 VEC_index (vn_reference_op_s
, mem
, 0));
865 VEC_ordered_remove (vn_reference_op_s
, *ops
, i
);
868 else if (VEC_length (vn_reference_op_s
, mem
) == 2)
870 VEC_replace (vn_reference_op_s
, *ops
, i
- 1,
871 VEC_index (vn_reference_op_s
, mem
, 0));
872 VEC_replace (vn_reference_op_s
, *ops
, i
,
873 VEC_index (vn_reference_op_s
, mem
, 1));
875 else if (VEC_length (vn_reference_op_s
, mem
) > 2)
877 VEC_replace (vn_reference_op_s
, *ops
, i
- 1,
878 VEC_index (vn_reference_op_s
, mem
, 0));
879 VEC_replace (vn_reference_op_s
, *ops
, i
,
880 VEC_index (vn_reference_op_s
, mem
, 1));
881 /* ??? There is no VEC_splice. */
882 for (j
= 2; VEC_iterate (vn_reference_op_s
, mem
, j
, op
); j
++)
883 VEC_safe_insert (vn_reference_op_s
, heap
, *ops
, ++i
, op
);
888 VEC_free (vn_reference_op_s
, heap
, mem
);
892 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
893 structures into their value numbers. This is done in-place, and
894 the vector passed in is returned. */
896 static VEC (vn_reference_op_s
, heap
) *
897 valueize_refs (VEC (vn_reference_op_s
, heap
) *orig
)
899 vn_reference_op_t vro
;
902 for (i
= 0; VEC_iterate (vn_reference_op_s
, orig
, i
, vro
); i
++)
904 if (vro
->opcode
== SSA_NAME
905 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
907 vro
->op0
= SSA_VAL (vro
->op0
);
908 /* If it transforms from an SSA_NAME to a constant, update
910 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
911 vro
->opcode
= TREE_CODE (vro
->op0
);
912 /* If it transforms from an SSA_NAME to an address, fold with
913 a preceding indirect reference. */
914 if (i
> 0 && TREE_CODE (vro
->op0
) == ADDR_EXPR
915 && VEC_index (vn_reference_op_s
,
916 orig
, i
- 1)->opcode
== INDIRECT_REF
)
918 vn_reference_fold_indirect (&orig
, &i
);
922 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
923 vro
->op1
= SSA_VAL (vro
->op1
);
924 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
925 vro
->op2
= SSA_VAL (vro
->op2
);
931 static VEC(vn_reference_op_s
, heap
) *shared_lookup_references
;
933 /* Create a vector of vn_reference_op_s structures from REF, a
934 REFERENCE_CLASS_P tree. The vector is shared among all callers of
937 static VEC(vn_reference_op_s
, heap
) *
938 valueize_shared_reference_ops_from_ref (tree ref
)
942 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
943 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
944 shared_lookup_references
= valueize_refs (shared_lookup_references
);
945 return shared_lookup_references
;
948 /* Create a vector of vn_reference_op_s structures from CALL, a
949 call statement. The vector is shared among all callers of
952 static VEC(vn_reference_op_s
, heap
) *
953 valueize_shared_reference_ops_from_call (gimple call
)
957 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
958 copy_reference_ops_from_call (call
, &shared_lookup_references
);
959 shared_lookup_references
= valueize_refs (shared_lookup_references
);
960 return shared_lookup_references
;
963 /* Lookup a SCCVN reference operation VR in the current hash table.
964 Returns the resulting value number if it exists in the hash table,
965 NULL_TREE otherwise. VNRESULT will be filled in with the actual
966 vn_reference_t stored in the hashtable if something is found. */
969 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
975 slot
= htab_find_slot_with_hash (current_info
->references
, vr
,
977 if (!slot
&& current_info
== optimistic_info
)
978 slot
= htab_find_slot_with_hash (valid_info
->references
, vr
,
983 *vnresult
= (vn_reference_t
)*slot
;
984 return ((vn_reference_t
)*slot
)->result
;
990 static tree
*last_vuse_ptr
;
992 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
993 with the current VUSE and performs the expression lookup. */
996 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
, void *vr_
)
998 vn_reference_t vr
= (vn_reference_t
)vr_
;
1003 *last_vuse_ptr
= vuse
;
1005 /* Fixup vuse and hash. */
1007 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1008 vr
->vuse
= SSA_VAL (vuse
);
1010 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1012 hash
= vr
->hashcode
;
1013 slot
= htab_find_slot_with_hash (current_info
->references
, vr
,
1015 if (!slot
&& current_info
== optimistic_info
)
1016 slot
= htab_find_slot_with_hash (valid_info
->references
, vr
,
1024 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1025 from the statement defining VUSE and if not successful tries to
1026 translate *REFP and VR_ through an aggregate copy at the defintion
1030 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
)
1032 vn_reference_t vr
= (vn_reference_t
)vr_
;
1033 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1036 HOST_WIDE_INT offset
, maxsize
;
1038 base
= ao_ref_base (ref
);
1039 offset
= ref
->offset
;
1040 maxsize
= ref
->max_size
;
1042 /* If we cannot constrain the size of the reference we cannot
1043 test if anything kills it. */
1047 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1048 from that defintion.
1050 if (is_gimple_reg_type (vr
->type
)
1051 && is_gimple_call (def_stmt
)
1052 && (fndecl
= gimple_call_fndecl (def_stmt
))
1053 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1054 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET
1055 && integer_zerop (gimple_call_arg (def_stmt
, 1))
1056 && host_integerp (gimple_call_arg (def_stmt
, 2), 1)
1057 && TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
)
1059 tree ref2
= TREE_OPERAND (gimple_call_arg (def_stmt
, 0), 0);
1061 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1062 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
);
1063 size2
= TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2)) * 8;
1064 if ((unsigned HOST_WIDE_INT
)size2
/ 8
1065 == TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 2))
1066 && operand_equal_p (base
, base2
, 0)
1067 && offset2
<= offset
1068 && offset2
+ size2
>= offset
+ maxsize
)
1070 tree val
= fold_convert (vr
->type
, integer_zero_node
);
1071 unsigned int value_id
= get_or_alloc_constant_value_id (val
);
1072 return vn_reference_insert_pieces (vuse
, vr
->set
, vr
->type
,
1073 VEC_copy (vn_reference_op_s
,
1074 heap
, vr
->operands
),
1079 /* 2) Assignment from an empty CONSTRUCTOR. */
1080 else if (is_gimple_reg_type (vr
->type
)
1081 && gimple_assign_single_p (def_stmt
)
1082 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
1083 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
1086 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1087 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1088 &offset2
, &size2
, &maxsize2
);
1089 if (operand_equal_p (base
, base2
, 0)
1090 && offset2
<= offset
1091 && offset2
+ size2
>= offset
+ maxsize
)
1093 tree val
= fold_convert (vr
->type
, integer_zero_node
);
1094 unsigned int value_id
= get_or_alloc_constant_value_id (val
);
1095 return vn_reference_insert_pieces (vuse
, vr
->set
, vr
->type
,
1096 VEC_copy (vn_reference_op_s
,
1097 heap
, vr
->operands
),
1102 /* For aggregate copies translate the reference through them if
1103 the copy kills ref. */
1104 else if (gimple_assign_single_p (def_stmt
)
1105 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
1106 || INDIRECT_REF_P (gimple_assign_rhs1 (def_stmt
))
1107 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
1110 HOST_WIDE_INT offset2
, size2
, maxsize2
;
1112 VEC (vn_reference_op_s
, heap
) *lhs
= NULL
, *rhs
= NULL
;
1113 vn_reference_op_t vro
;
1116 /* See if the assignment kills REF. */
1117 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
1118 &offset2
, &size2
, &maxsize2
);
1119 if (!operand_equal_p (base
, base2
, 0)
1121 || offset2
+ size2
< offset
+ maxsize
)
1124 /* Find the common base of ref and the lhs. */
1125 copy_reference_ops_from_ref (gimple_assign_lhs (def_stmt
), &lhs
);
1126 i
= VEC_length (vn_reference_op_s
, vr
->operands
) - 1;
1127 j
= VEC_length (vn_reference_op_s
, lhs
) - 1;
1128 while (j
>= 0 && i
>= 0
1129 && vn_reference_op_eq (VEC_index (vn_reference_op_s
,
1131 VEC_index (vn_reference_op_s
, lhs
, j
)))
1137 VEC_free (vn_reference_op_s
, heap
, lhs
);
1138 /* i now points to the first additional op.
1139 ??? LHS may not be completely contained in VR, one or more
1140 VIEW_CONVERT_EXPRs could be in its way. We could at least
1141 try handling outermost VIEW_CONVERT_EXPRs. */
1145 /* Now re-write REF to be based on the rhs of the assignment. */
1146 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
1147 /* We need to pre-pend vr->operands[0..i] to rhs. */
1148 if (i
+ 1 + VEC_length (vn_reference_op_s
, rhs
)
1149 > VEC_length (vn_reference_op_s
, vr
->operands
))
1151 VEC (vn_reference_op_s
, heap
) *old
= vr
->operands
;
1152 VEC_safe_grow (vn_reference_op_s
, heap
, vr
->operands
,
1153 i
+ 1 + VEC_length (vn_reference_op_s
, rhs
));
1154 if (old
== shared_lookup_references
1155 && vr
->operands
!= old
)
1156 shared_lookup_references
= NULL
;
1159 VEC_truncate (vn_reference_op_s
, vr
->operands
,
1160 i
+ 1 + VEC_length (vn_reference_op_s
, rhs
));
1161 for (j
= 0; VEC_iterate (vn_reference_op_s
, rhs
, j
, vro
); ++j
)
1162 VEC_replace (vn_reference_op_s
, vr
->operands
, i
+ 1 + j
, vro
);
1163 VEC_free (vn_reference_op_s
, heap
, rhs
);
1164 vr
->hashcode
= vn_reference_compute_hash (vr
);
1166 /* Adjust *ref from the new operands. */
1167 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
1169 /* This can happen with bitfields. */
1170 if (ref
->size
!= r
.size
)
1174 /* Do not update last seen VUSE after translating. */
1175 last_vuse_ptr
= NULL
;
1177 /* Keep looking for the adjusted *REF / VR pair. */
1181 /* Bail out and stop walking. */
1185 /* Lookup a reference operation by it's parts, in the current hash table.
1186 Returns the resulting value number if it exists in the hash table,
1187 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1188 vn_reference_t stored in the hashtable if something is found. */
1191 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
1192 VEC (vn_reference_op_s
, heap
) *operands
,
1193 vn_reference_t
*vnresult
, bool maywalk
)
1195 struct vn_reference_s vr1
;
1202 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1203 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
1204 VEC_safe_grow (vn_reference_op_s
, heap
, shared_lookup_references
,
1205 VEC_length (vn_reference_op_s
, operands
));
1206 memcpy (VEC_address (vn_reference_op_s
, shared_lookup_references
),
1207 VEC_address (vn_reference_op_s
, operands
),
1208 sizeof (vn_reference_op_s
)
1209 * VEC_length (vn_reference_op_s
, operands
));
1210 vr1
.operands
= operands
= shared_lookup_references
1211 = valueize_refs (shared_lookup_references
);
1214 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1215 vn_reference_lookup_1 (&vr1
, vnresult
);
1222 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
1224 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1225 vn_reference_lookup_2
,
1226 vn_reference_lookup_3
, &vr1
);
1227 if (vr1
.operands
!= operands
)
1228 VEC_free (vn_reference_op_s
, heap
, vr1
.operands
);
1232 return (*vnresult
)->result
;
1237 /* Lookup OP in the current hash table, and return the resulting value
1238 number if it exists in the hash table. Return NULL_TREE if it does
1239 not exist in the hash table or if the result field of the structure
1240 was NULL.. VNRESULT will be filled in with the vn_reference_t
1241 stored in the hashtable if one exists. */
1244 vn_reference_lookup (tree op
, tree vuse
, bool maywalk
,
1245 vn_reference_t
*vnresult
)
1247 VEC (vn_reference_op_s
, heap
) *operands
;
1248 struct vn_reference_s vr1
;
1253 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1254 vr1
.operands
= operands
= valueize_shared_reference_ops_from_ref (op
);
1255 vr1
.type
= TREE_TYPE (op
);
1256 vr1
.set
= get_alias_set (op
);
1257 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1262 vn_reference_t wvnresult
;
1264 ao_ref_init (&r
, op
);
1266 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
1267 vn_reference_lookup_2
,
1268 vn_reference_lookup_3
, &vr1
);
1269 if (vr1
.operands
!= operands
)
1270 VEC_free (vn_reference_op_s
, heap
, vr1
.operands
);
1274 *vnresult
= wvnresult
;
1275 return wvnresult
->result
;
1281 return vn_reference_lookup_1 (&vr1
, vnresult
);
1285 /* Insert OP into the current hash table with a value number of
1286 RESULT, and return the resulting reference structure we created. */
1289 vn_reference_insert (tree op
, tree result
, tree vuse
)
1294 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
1295 if (TREE_CODE (result
) == SSA_NAME
)
1296 vr1
->value_id
= VN_INFO (result
)->value_id
;
1298 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
1299 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1300 vr1
->operands
= valueize_refs (create_reference_ops_from_ref (op
));
1301 vr1
->type
= TREE_TYPE (op
);
1302 vr1
->set
= get_alias_set (op
);
1303 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
1304 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
1306 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
1309 /* Because we lookup stores using vuses, and value number failures
1310 using the vdefs (see visit_reference_op_store for how and why),
1311 it's possible that on failure we may try to insert an already
1312 inserted store. This is not wrong, there is no ssa name for a
1313 store that we could use as a differentiator anyway. Thus, unlike
1314 the other lookup functions, you cannot gcc_assert (!*slot)
1317 /* But free the old slot in case of a collision. */
1319 free_reference (*slot
);
1325 /* Insert a reference by it's pieces into the current hash table with
1326 a value number of RESULT. Return the resulting reference
1327 structure we created. */
1330 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
1331 VEC (vn_reference_op_s
, heap
) *operands
,
1332 tree result
, unsigned int value_id
)
1338 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
1339 vr1
->value_id
= value_id
;
1340 vr1
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1341 vr1
->operands
= valueize_refs (operands
);
1344 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
1345 if (result
&& TREE_CODE (result
) == SSA_NAME
)
1346 result
= SSA_VAL (result
);
1347 vr1
->result
= result
;
1349 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
1352 /* At this point we should have all the things inserted that we have
1353 seen before, and we should never try inserting something that
1355 gcc_assert (!*slot
);
1357 free_reference (*slot
);
1363 /* Compute and return the hash value for nary operation VBO1. */
1366 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
1371 for (i
= 0; i
< vno1
->length
; ++i
)
1372 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
1373 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
1375 if (vno1
->length
== 2
1376 && commutative_tree_code (vno1
->opcode
)
1377 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
1379 tree temp
= vno1
->op
[0];
1380 vno1
->op
[0] = vno1
->op
[1];
1384 hash
= iterative_hash_hashval_t (vno1
->opcode
, 0);
1385 for (i
= 0; i
< vno1
->length
; ++i
)
1386 hash
= iterative_hash_expr (vno1
->op
[i
], hash
);
1391 /* Return the computed hashcode for nary operation P1. */
1394 vn_nary_op_hash (const void *p1
)
1396 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
1397 return vno1
->hashcode
;
1400 /* Compare nary operations P1 and P2 and return true if they are
1404 vn_nary_op_eq (const void *p1
, const void *p2
)
1406 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
1407 const_vn_nary_op_t
const vno2
= (const_vn_nary_op_t
) p2
;
1410 if (vno1
->hashcode
!= vno2
->hashcode
)
1413 if (vno1
->opcode
!= vno2
->opcode
1414 || !types_compatible_p (vno1
->type
, vno2
->type
))
1417 for (i
= 0; i
< vno1
->length
; ++i
)
1418 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
1424 /* Lookup a n-ary operation by its pieces and return the resulting value
1425 number if it exists in the hash table. Return NULL_TREE if it does
1426 not exist in the hash table or if the result field of the operation
1427 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1431 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
1432 tree type
, tree op0
, tree op1
, tree op2
,
1433 tree op3
, vn_nary_op_t
*vnresult
)
1436 struct vn_nary_op_s vno1
;
1440 vno1
.length
= length
;
1446 vno1
.hashcode
= vn_nary_op_compute_hash (&vno1
);
1447 slot
= htab_find_slot_with_hash (current_info
->nary
, &vno1
, vno1
.hashcode
,
1449 if (!slot
&& current_info
== optimistic_info
)
1450 slot
= htab_find_slot_with_hash (valid_info
->nary
, &vno1
, vno1
.hashcode
,
1455 *vnresult
= (vn_nary_op_t
)*slot
;
1456 return ((vn_nary_op_t
)*slot
)->result
;
1459 /* Lookup OP in the current hash table, and return the resulting value
1460 number if it exists in the hash table. Return NULL_TREE if it does
1461 not exist in the hash table or if the result field of the operation
1462 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1466 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
1469 struct vn_nary_op_s vno1
;
1474 vno1
.opcode
= TREE_CODE (op
);
1475 vno1
.length
= TREE_CODE_LENGTH (TREE_CODE (op
));
1476 vno1
.type
= TREE_TYPE (op
);
1477 for (i
= 0; i
< vno1
.length
; ++i
)
1478 vno1
.op
[i
] = TREE_OPERAND (op
, i
);
1479 vno1
.hashcode
= vn_nary_op_compute_hash (&vno1
);
1480 slot
= htab_find_slot_with_hash (current_info
->nary
, &vno1
, vno1
.hashcode
,
1482 if (!slot
&& current_info
== optimistic_info
)
1483 slot
= htab_find_slot_with_hash (valid_info
->nary
, &vno1
, vno1
.hashcode
,
1488 *vnresult
= (vn_nary_op_t
)*slot
;
1489 return ((vn_nary_op_t
)*slot
)->result
;
1492 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1493 value number if it exists in the hash table. Return NULL_TREE if
1494 it does not exist in the hash table. VNRESULT will contain the
1495 vn_nary_op_t from the hashtable if it exists. */
1498 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
1501 struct vn_nary_op_s vno1
;
1506 vno1
.opcode
= gimple_assign_rhs_code (stmt
);
1507 vno1
.length
= gimple_num_ops (stmt
) - 1;
1508 vno1
.type
= gimple_expr_type (stmt
);
1509 for (i
= 0; i
< vno1
.length
; ++i
)
1510 vno1
.op
[i
] = gimple_op (stmt
, i
+ 1);
1511 if (vno1
.opcode
== REALPART_EXPR
1512 || vno1
.opcode
== IMAGPART_EXPR
1513 || vno1
.opcode
== VIEW_CONVERT_EXPR
)
1514 vno1
.op
[0] = TREE_OPERAND (vno1
.op
[0], 0);
1515 vno1
.hashcode
= vn_nary_op_compute_hash (&vno1
);
1516 slot
= htab_find_slot_with_hash (current_info
->nary
, &vno1
, vno1
.hashcode
,
1518 if (!slot
&& current_info
== optimistic_info
)
1519 slot
= htab_find_slot_with_hash (valid_info
->nary
, &vno1
, vno1
.hashcode
,
1524 *vnresult
= (vn_nary_op_t
)*slot
;
1525 return ((vn_nary_op_t
)*slot
)->result
;
1528 /* Insert a n-ary operation into the current hash table using it's
1529 pieces. Return the vn_nary_op_t structure we created and put in
1533 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
1534 tree type
, tree op0
,
1535 tree op1
, tree op2
, tree op3
,
1537 unsigned int value_id
)
1542 vno1
= (vn_nary_op_t
) obstack_alloc (¤t_info
->nary_obstack
,
1543 (sizeof (struct vn_nary_op_s
)
1544 - sizeof (tree
) * (4 - length
)));
1545 vno1
->value_id
= value_id
;
1546 vno1
->opcode
= code
;
1547 vno1
->length
= length
;
1557 vno1
->result
= result
;
1558 vno1
->hashcode
= vn_nary_op_compute_hash (vno1
);
1559 slot
= htab_find_slot_with_hash (current_info
->nary
, vno1
, vno1
->hashcode
,
1561 gcc_assert (!*slot
);
1568 /* Insert OP into the current hash table with a value number of
1569 RESULT. Return the vn_nary_op_t structure we created and put in
1573 vn_nary_op_insert (tree op
, tree result
)
1575 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
1580 vno1
= (vn_nary_op_t
) obstack_alloc (¤t_info
->nary_obstack
,
1581 (sizeof (struct vn_nary_op_s
)
1582 - sizeof (tree
) * (4 - length
)));
1583 vno1
->value_id
= VN_INFO (result
)->value_id
;
1584 vno1
->opcode
= TREE_CODE (op
);
1585 vno1
->length
= length
;
1586 vno1
->type
= TREE_TYPE (op
);
1587 for (i
= 0; i
< vno1
->length
; ++i
)
1588 vno1
->op
[i
] = TREE_OPERAND (op
, i
);
1589 vno1
->result
= result
;
1590 vno1
->hashcode
= vn_nary_op_compute_hash (vno1
);
1591 slot
= htab_find_slot_with_hash (current_info
->nary
, vno1
, vno1
->hashcode
,
1593 gcc_assert (!*slot
);
1599 /* Insert the rhs of STMT into the current hash table with a value number of
1603 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
1605 unsigned length
= gimple_num_ops (stmt
) - 1;
1610 vno1
= (vn_nary_op_t
) obstack_alloc (¤t_info
->nary_obstack
,
1611 (sizeof (struct vn_nary_op_s
)
1612 - sizeof (tree
) * (4 - length
)));
1613 vno1
->value_id
= VN_INFO (result
)->value_id
;
1614 vno1
->opcode
= gimple_assign_rhs_code (stmt
);
1615 vno1
->length
= length
;
1616 vno1
->type
= gimple_expr_type (stmt
);
1617 for (i
= 0; i
< vno1
->length
; ++i
)
1618 vno1
->op
[i
] = gimple_op (stmt
, i
+ 1);
1619 if (vno1
->opcode
== REALPART_EXPR
1620 || vno1
->opcode
== IMAGPART_EXPR
1621 || vno1
->opcode
== VIEW_CONVERT_EXPR
)
1622 vno1
->op
[0] = TREE_OPERAND (vno1
->op
[0], 0);
1623 vno1
->result
= result
;
1624 vno1
->hashcode
= vn_nary_op_compute_hash (vno1
);
1625 slot
= htab_find_slot_with_hash (current_info
->nary
, vno1
, vno1
->hashcode
,
1627 gcc_assert (!*slot
);
1633 /* Compute a hashcode for PHI operation VP1 and return it. */
1635 static inline hashval_t
1636 vn_phi_compute_hash (vn_phi_t vp1
)
1643 result
= vp1
->block
->index
;
1645 /* If all PHI arguments are constants we need to distinguish
1646 the PHI node via its type. */
1647 type
= TREE_TYPE (VEC_index (tree
, vp1
->phiargs
, 0));
1648 result
+= (INTEGRAL_TYPE_P (type
)
1649 + (INTEGRAL_TYPE_P (type
)
1650 ? TYPE_PRECISION (type
) + TYPE_UNSIGNED (type
) : 0));
1652 for (i
= 0; VEC_iterate (tree
, vp1
->phiargs
, i
, phi1op
); i
++)
1654 if (phi1op
== VN_TOP
)
1656 result
= iterative_hash_expr (phi1op
, result
);
1662 /* Return the computed hashcode for phi operation P1. */
1665 vn_phi_hash (const void *p1
)
1667 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
1668 return vp1
->hashcode
;
1671 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1674 vn_phi_eq (const void *p1
, const void *p2
)
1676 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
1677 const_vn_phi_t
const vp2
= (const_vn_phi_t
) p2
;
1679 if (vp1
->hashcode
!= vp2
->hashcode
)
1682 if (vp1
->block
== vp2
->block
)
1687 /* If the PHI nodes do not have compatible types
1688 they are not the same. */
1689 if (!types_compatible_p (TREE_TYPE (VEC_index (tree
, vp1
->phiargs
, 0)),
1690 TREE_TYPE (VEC_index (tree
, vp2
->phiargs
, 0))))
1693 /* Any phi in the same block will have it's arguments in the
1694 same edge order, because of how we store phi nodes. */
1695 for (i
= 0; VEC_iterate (tree
, vp1
->phiargs
, i
, phi1op
); i
++)
1697 tree phi2op
= VEC_index (tree
, vp2
->phiargs
, i
);
1698 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
1700 if (!expressions_equal_p (phi1op
, phi2op
))
1708 static VEC(tree
, heap
) *shared_lookup_phiargs
;
1710 /* Lookup PHI in the current hash table, and return the resulting
1711 value number if it exists in the hash table. Return NULL_TREE if
1712 it does not exist in the hash table. */
1715 vn_phi_lookup (gimple phi
)
1718 struct vn_phi_s vp1
;
1721 VEC_truncate (tree
, shared_lookup_phiargs
, 0);
1723 /* Canonicalize the SSA_NAME's to their value number. */
1724 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1726 tree def
= PHI_ARG_DEF (phi
, i
);
1727 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
1728 VEC_safe_push (tree
, heap
, shared_lookup_phiargs
, def
);
1730 vp1
.phiargs
= shared_lookup_phiargs
;
1731 vp1
.block
= gimple_bb (phi
);
1732 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
1733 slot
= htab_find_slot_with_hash (current_info
->phis
, &vp1
, vp1
.hashcode
,
1735 if (!slot
&& current_info
== optimistic_info
)
1736 slot
= htab_find_slot_with_hash (valid_info
->phis
, &vp1
, vp1
.hashcode
,
1740 return ((vn_phi_t
)*slot
)->result
;
1743 /* Insert PHI into the current hash table with a value number of
1747 vn_phi_insert (gimple phi
, tree result
)
1750 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
1752 VEC (tree
, heap
) *args
= NULL
;
1754 /* Canonicalize the SSA_NAME's to their value number. */
1755 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1757 tree def
= PHI_ARG_DEF (phi
, i
);
1758 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
1759 VEC_safe_push (tree
, heap
, args
, def
);
1761 vp1
->value_id
= VN_INFO (result
)->value_id
;
1762 vp1
->phiargs
= args
;
1763 vp1
->block
= gimple_bb (phi
);
1764 vp1
->result
= result
;
1765 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
1767 slot
= htab_find_slot_with_hash (current_info
->phis
, vp1
, vp1
->hashcode
,
1770 /* Because we iterate over phi operations more than once, it's
1771 possible the slot might already exist here, hence no assert.*/
1777 /* Print set of components in strongly connected component SCC to OUT. */
1780 print_scc (FILE *out
, VEC (tree
, heap
) *scc
)
1785 fprintf (out
, "SCC consists of: ");
1786 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
1788 print_generic_expr (out
, var
, 0);
1791 fprintf (out
, "\n");
1794 /* Set the value number of FROM to TO, return true if it has changed
1798 set_ssa_val_to (tree from
, tree to
)
1803 && TREE_CODE (to
) == SSA_NAME
1804 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
1807 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1808 and invariants. So assert that here. */
1809 gcc_assert (to
!= NULL_TREE
1811 || TREE_CODE (to
) == SSA_NAME
1812 || is_gimple_min_invariant (to
)));
1814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1816 fprintf (dump_file
, "Setting value number of ");
1817 print_generic_expr (dump_file
, from
, 0);
1818 fprintf (dump_file
, " to ");
1819 print_generic_expr (dump_file
, to
, 0);
1822 currval
= SSA_VAL (from
);
1824 if (currval
!= to
&& !operand_equal_p (currval
, to
, OEP_PURE_SAME
))
1826 VN_INFO (from
)->valnum
= to
;
1827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1828 fprintf (dump_file
, " (changed)\n");
1831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1832 fprintf (dump_file
, "\n");
1836 /* Set all definitions in STMT to value number to themselves.
1837 Return true if a value number changed. */
1840 defs_to_varying (gimple stmt
)
1842 bool changed
= false;
1846 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1848 tree def
= DEF_FROM_PTR (defp
);
1850 VN_INFO (def
)->use_processed
= true;
1851 changed
|= set_ssa_val_to (def
, def
);
1856 static bool expr_has_constants (tree expr
);
1857 static tree
valueize_expr (tree expr
);
1859 /* Visit a copy between LHS and RHS, return true if the value number
1863 visit_copy (tree lhs
, tree rhs
)
1865 /* Follow chains of copies to their destination. */
1866 while (TREE_CODE (rhs
) == SSA_NAME
1867 && SSA_VAL (rhs
) != rhs
)
1868 rhs
= SSA_VAL (rhs
);
1870 /* The copy may have a more interesting constant filled expression
1871 (we don't, since we know our RHS is just an SSA name). */
1872 if (TREE_CODE (rhs
) == SSA_NAME
)
1874 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
1875 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
1878 return set_ssa_val_to (lhs
, rhs
);
1881 /* Visit a unary operator RHS, value number it, and return true if the
1882 value number of LHS has changed as a result. */
1885 visit_unary_op (tree lhs
, gimple stmt
)
1887 bool changed
= false;
1888 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
1892 changed
= set_ssa_val_to (lhs
, result
);
1896 changed
= set_ssa_val_to (lhs
, lhs
);
1897 vn_nary_op_insert_stmt (stmt
, lhs
);
1903 /* Visit a binary operator RHS, value number it, and return true if the
1904 value number of LHS has changed as a result. */
1907 visit_binary_op (tree lhs
, gimple stmt
)
1909 bool changed
= false;
1910 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
1914 changed
= set_ssa_val_to (lhs
, result
);
1918 changed
= set_ssa_val_to (lhs
, lhs
);
1919 vn_nary_op_insert_stmt (stmt
, lhs
);
1925 /* Visit a call STMT storing into LHS. Return true if the value number
1926 of the LHS has changed as a result. */
1929 visit_reference_op_call (tree lhs
, gimple stmt
)
1931 bool changed
= false;
1932 struct vn_reference_s vr1
;
1934 tree vuse
= gimple_vuse (stmt
);
1936 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1937 vr1
.operands
= valueize_shared_reference_ops_from_call (stmt
);
1938 vr1
.type
= gimple_expr_type (stmt
);
1940 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1941 result
= vn_reference_lookup_1 (&vr1
, NULL
);
1944 changed
= set_ssa_val_to (lhs
, result
);
1945 if (TREE_CODE (result
) == SSA_NAME
1946 && VN_INFO (result
)->has_constants
)
1947 VN_INFO (lhs
)->has_constants
= true;
1953 changed
= set_ssa_val_to (lhs
, lhs
);
1954 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
1955 vr2
->vuse
= vr1
.vuse
;
1956 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
1957 vr2
->type
= vr1
.type
;
1959 vr2
->hashcode
= vr1
.hashcode
;
1961 slot
= htab_find_slot_with_hash (current_info
->references
,
1962 vr2
, vr2
->hashcode
, INSERT
);
1964 free_reference (*slot
);
1971 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1972 and return true if the value number of the LHS has changed as a result. */
1975 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
1977 bool changed
= false;
1981 last_vuse
= gimple_vuse (stmt
);
1982 last_vuse_ptr
= &last_vuse
;
1983 result
= vn_reference_lookup (op
, gimple_vuse (stmt
), true, NULL
);
1984 last_vuse_ptr
= NULL
;
1986 /* If we have a VCE, try looking up its operand as it might be stored in
1987 a different type. */
1988 if (!result
&& TREE_CODE (op
) == VIEW_CONVERT_EXPR
)
1989 result
= vn_reference_lookup (TREE_OPERAND (op
, 0), gimple_vuse (stmt
),
1992 /* We handle type-punning through unions by value-numbering based
1993 on offset and size of the access. Be prepared to handle a
1994 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1996 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
1998 /* We will be setting the value number of lhs to the value number
1999 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2000 So first simplify and lookup this expression to see if it
2001 is already available. */
2002 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
2003 if ((CONVERT_EXPR_P (val
)
2004 || TREE_CODE (val
) == VIEW_CONVERT_EXPR
)
2005 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
)
2007 tree tem
= valueize_expr (vn_get_expr_for (TREE_OPERAND (val
, 0)));
2008 if ((CONVERT_EXPR_P (tem
)
2009 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
)
2010 && (tem
= fold_unary_ignore_overflow (TREE_CODE (val
),
2011 TREE_TYPE (val
), tem
)))
2015 if (!is_gimple_min_invariant (val
)
2016 && TREE_CODE (val
) != SSA_NAME
)
2017 result
= vn_nary_op_lookup (val
, NULL
);
2018 /* If the expression is not yet available, value-number lhs to
2019 a new SSA_NAME we create. */
2020 if (!result
&& may_insert
)
2022 result
= make_ssa_name (SSA_NAME_VAR (lhs
), NULL
);
2023 /* Initialize value-number information properly. */
2024 VN_INFO_GET (result
)->valnum
= result
;
2025 VN_INFO (result
)->value_id
= get_next_value_id ();
2026 VN_INFO (result
)->expr
= val
;
2027 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
2028 VN_INFO (result
)->needs_insertion
= true;
2029 /* As all "inserted" statements are singleton SCCs, insert
2030 to the valid table. This is strictly needed to
2031 avoid re-generating new value SSA_NAMEs for the same
2032 expression during SCC iteration over and over (the
2033 optimistic table gets cleared after each iteration).
2034 We do not need to insert into the optimistic table, as
2035 lookups there will fall back to the valid table. */
2036 if (current_info
== optimistic_info
)
2038 current_info
= valid_info
;
2039 vn_nary_op_insert (val
, result
);
2040 current_info
= optimistic_info
;
2043 vn_nary_op_insert (val
, result
);
2044 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2046 fprintf (dump_file
, "Inserting name ");
2047 print_generic_expr (dump_file
, result
, 0);
2048 fprintf (dump_file
, " for expression ");
2049 print_generic_expr (dump_file
, val
, 0);
2050 fprintf (dump_file
, "\n");
2057 changed
= set_ssa_val_to (lhs
, result
);
2058 if (TREE_CODE (result
) == SSA_NAME
2059 && VN_INFO (result
)->has_constants
)
2061 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
2062 VN_INFO (lhs
)->has_constants
= true;
2067 changed
= set_ssa_val_to (lhs
, lhs
);
2068 vn_reference_insert (op
, lhs
, last_vuse
);
2075 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2076 and return true if the value number of the LHS has changed as a result. */
2079 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
2081 bool changed
= false;
2083 bool resultsame
= false;
2085 /* First we want to lookup using the *vuses* from the store and see
2086 if there the last store to this location with the same address
2089 The vuses represent the memory state before the store. If the
2090 memory state, address, and value of the store is the same as the
2091 last store to this location, then this store will produce the
2092 same memory state as that store.
2094 In this case the vdef versions for this store are value numbered to those
2095 vuse versions, since they represent the same memory state after
2098 Otherwise, the vdefs for the store are used when inserting into
2099 the table, since the store generates a new memory state. */
2101 result
= vn_reference_lookup (lhs
, gimple_vuse (stmt
), false, NULL
);
2105 if (TREE_CODE (result
) == SSA_NAME
)
2106 result
= SSA_VAL (result
);
2107 if (TREE_CODE (op
) == SSA_NAME
)
2109 resultsame
= expressions_equal_p (result
, op
);
2112 if (!result
|| !resultsame
)
2116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2118 fprintf (dump_file
, "No store match\n");
2119 fprintf (dump_file
, "Value numbering store ");
2120 print_generic_expr (dump_file
, lhs
, 0);
2121 fprintf (dump_file
, " to ");
2122 print_generic_expr (dump_file
, op
, 0);
2123 fprintf (dump_file
, "\n");
2125 /* Have to set value numbers before insert, since insert is
2126 going to valueize the references in-place. */
2127 if ((vdef
= gimple_vdef (stmt
)))
2129 VN_INFO (vdef
)->use_processed
= true;
2130 changed
|= set_ssa_val_to (vdef
, vdef
);
2133 /* Do not insert structure copies into the tables. */
2134 if (is_gimple_min_invariant (op
)
2135 || is_gimple_reg (op
))
2136 vn_reference_insert (lhs
, op
, vdef
);
2140 /* We had a match, so value number the vdef to have the value
2141 number of the vuse it came from. */
2144 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2145 fprintf (dump_file
, "Store matched earlier value,"
2146 "value numbering store vdefs to matching vuses.\n");
2148 def
= gimple_vdef (stmt
);
2149 use
= gimple_vuse (stmt
);
2151 VN_INFO (def
)->use_processed
= true;
2152 changed
|= set_ssa_val_to (def
, SSA_VAL (use
));
2158 /* Visit and value number PHI, return true if the value number
2162 visit_phi (gimple phi
)
2164 bool changed
= false;
2166 tree sameval
= VN_TOP
;
2167 bool allsame
= true;
2170 /* TODO: We could check for this in init_sccvn, and replace this
2171 with a gcc_assert. */
2172 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
2173 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
2175 /* See if all non-TOP arguments have the same value. TOP is
2176 equivalent to everything, so we can ignore it. */
2177 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2179 tree def
= PHI_ARG_DEF (phi
, i
);
2181 if (TREE_CODE (def
) == SSA_NAME
)
2182 def
= SSA_VAL (def
);
2185 if (sameval
== VN_TOP
)
2191 if (!expressions_equal_p (def
, sameval
))
2199 /* If all value numbered to the same value, the phi node has that
2203 if (is_gimple_min_invariant (sameval
))
2205 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
2206 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
2210 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
2211 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
2214 if (TREE_CODE (sameval
) == SSA_NAME
)
2215 return visit_copy (PHI_RESULT (phi
), sameval
);
2217 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
2220 /* Otherwise, see if it is equivalent to a phi node in this block. */
2221 result
= vn_phi_lookup (phi
);
2224 if (TREE_CODE (result
) == SSA_NAME
)
2225 changed
= visit_copy (PHI_RESULT (phi
), result
);
2227 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
2231 vn_phi_insert (phi
, PHI_RESULT (phi
));
2232 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
2233 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
2234 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
2240 /* Return true if EXPR contains constants. */
2243 expr_has_constants (tree expr
)
2245 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
2248 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
2251 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
2252 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
2253 /* Constants inside reference ops are rarely interesting, but
2254 it can take a lot of looking to find them. */
2256 case tcc_declaration
:
2259 return is_gimple_min_invariant (expr
);
2264 /* Return true if STMT contains constants. */
2267 stmt_has_constants (gimple stmt
)
2269 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2272 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2274 case GIMPLE_UNARY_RHS
:
2275 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
2277 case GIMPLE_BINARY_RHS
:
2278 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
2279 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
)));
2280 case GIMPLE_SINGLE_RHS
:
2281 /* Constants inside reference ops are rarely interesting, but
2282 it can take a lot of looking to find them. */
2283 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
2290 /* Replace SSA_NAMES in expr with their value numbers, and return the
2292 This is performed in place. */
2295 valueize_expr (tree expr
)
2297 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
2300 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
2301 && SSA_VAL (TREE_OPERAND (expr
, 0)) != VN_TOP
)
2302 TREE_OPERAND (expr
, 0) = SSA_VAL (TREE_OPERAND (expr
, 0));
2305 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
2306 && SSA_VAL (TREE_OPERAND (expr
, 0)) != VN_TOP
)
2307 TREE_OPERAND (expr
, 0) = SSA_VAL (TREE_OPERAND (expr
, 0));
2308 if (TREE_CODE (TREE_OPERAND (expr
, 1)) == SSA_NAME
2309 && SSA_VAL (TREE_OPERAND (expr
, 1)) != VN_TOP
)
2310 TREE_OPERAND (expr
, 1) = SSA_VAL (TREE_OPERAND (expr
, 1));
2318 /* Simplify the binary expression RHS, and return the result if
2322 simplify_binary_expression (gimple stmt
)
2324 tree result
= NULL_TREE
;
2325 tree op0
= gimple_assign_rhs1 (stmt
);
2326 tree op1
= gimple_assign_rhs2 (stmt
);
2328 /* This will not catch every single case we could combine, but will
2329 catch those with constants. The goal here is to simultaneously
2330 combine constants between expressions, but avoid infinite
2331 expansion of expressions during simplification. */
2332 if (TREE_CODE (op0
) == SSA_NAME
)
2334 if (VN_INFO (op0
)->has_constants
2335 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)) == tcc_comparison
)
2336 op0
= valueize_expr (vn_get_expr_for (op0
));
2337 else if (SSA_VAL (op0
) != VN_TOP
&& SSA_VAL (op0
) != op0
)
2338 op0
= SSA_VAL (op0
);
2341 if (TREE_CODE (op1
) == SSA_NAME
)
2343 if (VN_INFO (op1
)->has_constants
)
2344 op1
= valueize_expr (vn_get_expr_for (op1
));
2345 else if (SSA_VAL (op1
) != VN_TOP
&& SSA_VAL (op1
) != op1
)
2346 op1
= SSA_VAL (op1
);
2349 /* Avoid folding if nothing changed. */
2350 if (op0
== gimple_assign_rhs1 (stmt
)
2351 && op1
== gimple_assign_rhs2 (stmt
))
2354 fold_defer_overflow_warnings ();
2356 result
= fold_binary (gimple_assign_rhs_code (stmt
),
2357 gimple_expr_type (stmt
), op0
, op1
);
2359 STRIP_USELESS_TYPE_CONVERSION (result
);
2361 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
2364 /* Make sure result is not a complex expression consisting
2365 of operators of operators (IE (a + b) + (a + c))
2366 Otherwise, we will end up with unbounded expressions if
2367 fold does anything at all. */
2368 if (result
&& valid_gimple_rhs_p (result
))
2374 /* Simplify the unary expression RHS, and return the result if
2378 simplify_unary_expression (gimple stmt
)
2380 tree result
= NULL_TREE
;
2381 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
2383 /* We handle some tcc_reference codes here that are all
2384 GIMPLE_ASSIGN_SINGLE codes. */
2385 if (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
2386 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
2387 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
)
2388 op0
= TREE_OPERAND (op0
, 0);
2390 if (TREE_CODE (op0
) != SSA_NAME
)
2394 if (VN_INFO (op0
)->has_constants
)
2395 op0
= valueize_expr (vn_get_expr_for (op0
));
2396 else if (gimple_assign_cast_p (stmt
)
2397 || gimple_assign_rhs_code (stmt
) == REALPART_EXPR
2398 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
2399 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
)
2401 /* We want to do tree-combining on conversion-like expressions.
2402 Make sure we feed only SSA_NAMEs or constants to fold though. */
2403 tree tem
= valueize_expr (vn_get_expr_for (op0
));
2404 if (UNARY_CLASS_P (tem
)
2405 || BINARY_CLASS_P (tem
)
2406 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
2407 || TREE_CODE (tem
) == SSA_NAME
2408 || is_gimple_min_invariant (tem
))
2412 /* Avoid folding if nothing changed, but remember the expression. */
2413 if (op0
== orig_op0
)
2416 result
= fold_unary_ignore_overflow (gimple_assign_rhs_code (stmt
),
2417 gimple_expr_type (stmt
), op0
);
2420 STRIP_USELESS_TYPE_CONVERSION (result
);
2421 if (valid_gimple_rhs_p (result
))
2428 /* Try to simplify RHS using equivalences and constant folding. */
2431 try_to_simplify (gimple stmt
)
2435 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2436 in this case, there is no point in doing extra work. */
2437 if (gimple_assign_copy_p (stmt
)
2438 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2441 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)))
2443 case tcc_declaration
:
2444 tem
= get_symbol_constant_value (gimple_assign_rhs1 (stmt
));
2450 /* Do not do full-blown reference lookup here, but simplify
2451 reads from constant aggregates. */
2452 tem
= fold_const_aggregate_ref (gimple_assign_rhs1 (stmt
));
2456 /* Fallthrough for some codes that can operate on registers. */
2457 if (!(TREE_CODE (gimple_assign_rhs1 (stmt
)) == REALPART_EXPR
2458 || TREE_CODE (gimple_assign_rhs1 (stmt
)) == IMAGPART_EXPR
2459 || TREE_CODE (gimple_assign_rhs1 (stmt
)) == VIEW_CONVERT_EXPR
))
2461 /* We could do a little more with unary ops, if they expand
2462 into binary ops, but it's debatable whether it is worth it. */
2464 return simplify_unary_expression (stmt
);
2466 case tcc_comparison
:
2468 return simplify_binary_expression (stmt
);
2477 /* Visit and value number USE, return true if the value number
2481 visit_use (tree use
)
2483 bool changed
= false;
2484 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2486 VN_INFO (use
)->use_processed
= true;
2488 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
2489 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
2490 && !SSA_NAME_IS_DEFAULT_DEF (use
))
2492 fprintf (dump_file
, "Value numbering ");
2493 print_generic_expr (dump_file
, use
, 0);
2494 fprintf (dump_file
, " stmt = ");
2495 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2498 /* Handle uninitialized uses. */
2499 if (SSA_NAME_IS_DEFAULT_DEF (use
))
2500 changed
= set_ssa_val_to (use
, use
);
2503 if (gimple_code (stmt
) == GIMPLE_PHI
)
2504 changed
= visit_phi (stmt
);
2505 else if (!gimple_has_lhs (stmt
)
2506 || gimple_has_volatile_ops (stmt
)
2507 || stmt_could_throw_p (stmt
))
2508 changed
= defs_to_varying (stmt
);
2509 else if (is_gimple_assign (stmt
))
2511 tree lhs
= gimple_assign_lhs (stmt
);
2514 /* Shortcut for copies. Simplifying copies is pointless,
2515 since we copy the expression and value they represent. */
2516 if (gimple_assign_copy_p (stmt
)
2517 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
2518 && TREE_CODE (lhs
) == SSA_NAME
)
2520 changed
= visit_copy (lhs
, gimple_assign_rhs1 (stmt
));
2523 simplified
= try_to_simplify (stmt
);
2526 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2528 fprintf (dump_file
, "RHS ");
2529 print_gimple_expr (dump_file
, stmt
, 0, 0);
2530 fprintf (dump_file
, " simplified to ");
2531 print_generic_expr (dump_file
, simplified
, 0);
2532 if (TREE_CODE (lhs
) == SSA_NAME
)
2533 fprintf (dump_file
, " has constants %d\n",
2534 expr_has_constants (simplified
));
2536 fprintf (dump_file
, "\n");
2539 /* Setting value numbers to constants will occasionally
2540 screw up phi congruence because constants are not
2541 uniquely associated with a single ssa name that can be
2544 && is_gimple_min_invariant (simplified
)
2545 && TREE_CODE (lhs
) == SSA_NAME
)
2547 VN_INFO (lhs
)->expr
= simplified
;
2548 VN_INFO (lhs
)->has_constants
= true;
2549 changed
= set_ssa_val_to (lhs
, simplified
);
2553 && TREE_CODE (simplified
) == SSA_NAME
2554 && TREE_CODE (lhs
) == SSA_NAME
)
2556 changed
= visit_copy (lhs
, simplified
);
2559 else if (simplified
)
2561 if (TREE_CODE (lhs
) == SSA_NAME
)
2563 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
2564 /* We have to unshare the expression or else
2565 valuizing may change the IL stream. */
2566 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
2569 else if (stmt_has_constants (stmt
)
2570 && TREE_CODE (lhs
) == SSA_NAME
)
2571 VN_INFO (lhs
)->has_constants
= true;
2572 else if (TREE_CODE (lhs
) == SSA_NAME
)
2574 /* We reset expr and constantness here because we may
2575 have been value numbering optimistically, and
2576 iterating. They may become non-constant in this case,
2577 even if they were optimistically constant. */
2579 VN_INFO (lhs
)->has_constants
= false;
2580 VN_INFO (lhs
)->expr
= NULL_TREE
;
2583 if ((TREE_CODE (lhs
) == SSA_NAME
2584 /* We can substitute SSA_NAMEs that are live over
2585 abnormal edges with their constant value. */
2586 && !(gimple_assign_copy_p (stmt
)
2587 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
2589 && is_gimple_min_invariant (simplified
))
2590 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2591 /* Stores or copies from SSA_NAMEs that are live over
2592 abnormal edges are a problem. */
2593 || (gimple_assign_single_p (stmt
)
2594 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
2595 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt
))))
2596 changed
= defs_to_varying (stmt
);
2597 else if (REFERENCE_CLASS_P (lhs
) || DECL_P (lhs
))
2599 changed
= visit_reference_op_store (lhs
, gimple_assign_rhs1 (stmt
), stmt
);
2601 else if (TREE_CODE (lhs
) == SSA_NAME
)
2603 if ((gimple_assign_copy_p (stmt
)
2604 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
2606 && is_gimple_min_invariant (simplified
)))
2608 VN_INFO (lhs
)->has_constants
= true;
2610 changed
= set_ssa_val_to (lhs
, simplified
);
2612 changed
= set_ssa_val_to (lhs
, gimple_assign_rhs1 (stmt
));
2616 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2618 case GIMPLE_UNARY_RHS
:
2619 changed
= visit_unary_op (lhs
, stmt
);
2621 case GIMPLE_BINARY_RHS
:
2622 changed
= visit_binary_op (lhs
, stmt
);
2624 case GIMPLE_SINGLE_RHS
:
2625 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)))
2628 /* VOP-less references can go through unary case. */
2629 if ((gimple_assign_rhs_code (stmt
) == REALPART_EXPR
2630 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
2631 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
)
2632 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0)) == SSA_NAME
)
2634 changed
= visit_unary_op (lhs
, stmt
);
2638 case tcc_declaration
:
2639 changed
= visit_reference_op_load
2640 (lhs
, gimple_assign_rhs1 (stmt
), stmt
);
2642 case tcc_expression
:
2643 if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
2645 changed
= visit_unary_op (lhs
, stmt
);
2650 changed
= defs_to_varying (stmt
);
2654 changed
= defs_to_varying (stmt
);
2660 changed
= defs_to_varying (stmt
);
2662 else if (is_gimple_call (stmt
))
2664 tree lhs
= gimple_call_lhs (stmt
);
2666 /* ??? We could try to simplify calls. */
2668 if (stmt_has_constants (stmt
)
2669 && TREE_CODE (lhs
) == SSA_NAME
)
2670 VN_INFO (lhs
)->has_constants
= true;
2671 else if (TREE_CODE (lhs
) == SSA_NAME
)
2673 /* We reset expr and constantness here because we may
2674 have been value numbering optimistically, and
2675 iterating. They may become non-constant in this case,
2676 even if they were optimistically constant. */
2677 VN_INFO (lhs
)->has_constants
= false;
2678 VN_INFO (lhs
)->expr
= NULL_TREE
;
2681 if (TREE_CODE (lhs
) == SSA_NAME
2682 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2683 changed
= defs_to_varying (stmt
);
2684 /* ??? We should handle stores from calls. */
2685 else if (TREE_CODE (lhs
) == SSA_NAME
)
2687 if (gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
))
2688 changed
= visit_reference_op_call (lhs
, stmt
);
2690 changed
= defs_to_varying (stmt
);
2693 changed
= defs_to_varying (stmt
);
2700 /* Compare two operands by reverse postorder index */
2703 compare_ops (const void *pa
, const void *pb
)
2705 const tree opa
= *((const tree
*)pa
);
2706 const tree opb
= *((const tree
*)pb
);
2707 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
2708 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
2712 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
2713 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
2714 else if (gimple_nop_p (opstmta
))
2716 else if (gimple_nop_p (opstmtb
))
2719 bba
= gimple_bb (opstmta
);
2720 bbb
= gimple_bb (opstmtb
);
2723 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
2731 if (gimple_code (opstmta
) == GIMPLE_PHI
2732 && gimple_code (opstmtb
) == GIMPLE_PHI
)
2733 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
2734 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
2736 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
2738 else if (gimple_uid (opstmta
) != gimple_uid (opstmtb
))
2739 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
2741 return SSA_NAME_VERSION (opa
) - SSA_NAME_VERSION (opb
);
2743 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
2746 /* Sort an array containing members of a strongly connected component
2747 SCC so that the members are ordered by RPO number.
2748 This means that when the sort is complete, iterating through the
2749 array will give you the members in RPO order. */
2752 sort_scc (VEC (tree
, heap
) *scc
)
2754 qsort (VEC_address (tree
, scc
),
2755 VEC_length (tree
, scc
),
2760 /* Insert the no longer used nary *ENTRY to the current hash. */
2763 copy_nary (void **entry
, void *data ATTRIBUTE_UNUSED
)
2765 vn_nary_op_t onary
= (vn_nary_op_t
) *entry
;
2766 size_t size
= (sizeof (struct vn_nary_op_s
)
2767 - sizeof (tree
) * (4 - onary
->length
));
2768 vn_nary_op_t nary
= (vn_nary_op_t
) obstack_alloc (¤t_info
->nary_obstack
,
2771 memcpy (nary
, onary
, size
);
2772 slot
= htab_find_slot_with_hash (current_info
->nary
, nary
, nary
->hashcode
,
2774 gcc_assert (!*slot
);
2779 /* Insert the no longer used phi *ENTRY to the current hash. */
2782 copy_phis (void **entry
, void *data ATTRIBUTE_UNUSED
)
2784 vn_phi_t ophi
= (vn_phi_t
) *entry
;
2785 vn_phi_t phi
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
2787 memcpy (phi
, ophi
, sizeof (*phi
));
2788 ophi
->phiargs
= NULL
;
2789 slot
= htab_find_slot_with_hash (current_info
->phis
, phi
, phi
->hashcode
,
2795 /* Insert the no longer used reference *ENTRY to the current hash. */
2798 copy_references (void **entry
, void *data ATTRIBUTE_UNUSED
)
2800 vn_reference_t oref
= (vn_reference_t
) *entry
;
2803 ref
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
2804 memcpy (ref
, oref
, sizeof (*ref
));
2805 oref
->operands
= NULL
;
2806 slot
= htab_find_slot_with_hash (current_info
->references
, ref
, ref
->hashcode
,
2809 free_reference (*slot
);
2814 /* Process a strongly connected component in the SSA graph. */
2817 process_scc (VEC (tree
, heap
) *scc
)
2819 /* If the SCC has a single member, just visit it. */
2821 if (VEC_length (tree
, scc
) == 1)
2823 tree use
= VEC_index (tree
, scc
, 0);
2824 if (!VN_INFO (use
)->use_processed
)
2831 unsigned int iterations
= 0;
2832 bool changed
= true;
2834 /* Iterate over the SCC with the optimistic table until it stops
2836 current_info
= optimistic_info
;
2841 /* As we are value-numbering optimistically we have to
2842 clear the expression tables and the simplified expressions
2843 in each iteration until we converge. */
2844 htab_empty (optimistic_info
->nary
);
2845 htab_empty (optimistic_info
->phis
);
2846 htab_empty (optimistic_info
->references
);
2847 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
2848 gcc_obstack_init (&optimistic_info
->nary_obstack
);
2849 empty_alloc_pool (optimistic_info
->phis_pool
);
2850 empty_alloc_pool (optimistic_info
->references_pool
);
2851 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
2852 VN_INFO (var
)->expr
= NULL_TREE
;
2853 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
2854 changed
|= visit_use (var
);
2857 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
2859 /* Finally, copy the contents of the no longer used optimistic
2860 table to the valid table. */
2861 current_info
= valid_info
;
2862 htab_traverse (optimistic_info
->nary
, copy_nary
, NULL
);
2863 htab_traverse (optimistic_info
->phis
, copy_phis
, NULL
);
2864 htab_traverse (optimistic_info
->references
, copy_references
, NULL
);
2868 DEF_VEC_O(ssa_op_iter
);
2869 DEF_VEC_ALLOC_O(ssa_op_iter
,heap
);
2871 /* Pop the components of the found SCC for NAME off the SCC stack
2872 and process them. Returns true if all went well, false if
2873 we run into resource limits. */
2876 extract_and_process_scc_for_name (tree name
)
2878 VEC (tree
, heap
) *scc
= NULL
;
2881 /* Found an SCC, pop the components off the SCC stack and
2885 x
= VEC_pop (tree
, sccstack
);
2887 VN_INFO (x
)->on_sccstack
= false;
2888 VEC_safe_push (tree
, heap
, scc
, x
);
2889 } while (x
!= name
);
2891 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2892 if (VEC_length (tree
, scc
)
2893 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
2896 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
2897 "SCC size %u exceeding %u\n", VEC_length (tree
, scc
),
2898 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
2902 if (VEC_length (tree
, scc
) > 1)
2905 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2906 print_scc (dump_file
, scc
);
2910 VEC_free (tree
, heap
, scc
);
2915 /* Depth first search on NAME to discover and process SCC's in the SSA
2917 Execution of this algorithm relies on the fact that the SCC's are
2918 popped off the stack in topological order.
2919 Returns true if successful, false if we stopped processing SCC's due
2920 to resource constraints. */
2925 VEC(ssa_op_iter
, heap
) *itervec
= NULL
;
2926 VEC(tree
, heap
) *namevec
= NULL
;
2927 use_operand_p usep
= NULL
;
2934 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
2935 VN_INFO (name
)->visited
= true;
2936 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
2938 VEC_safe_push (tree
, heap
, sccstack
, name
);
2939 VN_INFO (name
)->on_sccstack
= true;
2940 defstmt
= SSA_NAME_DEF_STMT (name
);
2942 /* Recursively DFS on our operands, looking for SCC's. */
2943 if (!gimple_nop_p (defstmt
))
2945 /* Push a new iterator. */
2946 if (gimple_code (defstmt
) == GIMPLE_PHI
)
2947 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
2949 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
2952 clear_and_done_ssa_iter (&iter
);
2956 /* If we are done processing uses of a name, go up the stack
2957 of iterators and process SCCs as we found them. */
2958 if (op_iter_done (&iter
))
2960 /* See if we found an SCC. */
2961 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
2962 if (!extract_and_process_scc_for_name (name
))
2964 VEC_free (tree
, heap
, namevec
);
2965 VEC_free (ssa_op_iter
, heap
, itervec
);
2969 /* Check if we are done. */
2970 if (VEC_empty (tree
, namevec
))
2972 VEC_free (tree
, heap
, namevec
);
2973 VEC_free (ssa_op_iter
, heap
, itervec
);
2977 /* Restore the last use walker and continue walking there. */
2979 name
= VEC_pop (tree
, namevec
);
2980 memcpy (&iter
, VEC_last (ssa_op_iter
, itervec
),
2981 sizeof (ssa_op_iter
));
2982 VEC_pop (ssa_op_iter
, itervec
);
2983 goto continue_walking
;
2986 use
= USE_FROM_PTR (usep
);
2988 /* Since we handle phi nodes, we will sometimes get
2989 invariants in the use expression. */
2990 if (TREE_CODE (use
) == SSA_NAME
)
2992 if (! (VN_INFO (use
)->visited
))
2994 /* Recurse by pushing the current use walking state on
2995 the stack and starting over. */
2996 VEC_safe_push(ssa_op_iter
, heap
, itervec
, &iter
);
2997 VEC_safe_push(tree
, heap
, namevec
, name
);
3002 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
3003 VN_INFO (use
)->low
);
3005 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
3006 && VN_INFO (use
)->on_sccstack
)
3008 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
3009 VN_INFO (name
)->low
);
3013 usep
= op_iter_next_use (&iter
);
3017 /* Allocate a value number table. */
3020 allocate_vn_table (vn_tables_t table
)
3022 table
->phis
= htab_create (23, vn_phi_hash
, vn_phi_eq
, free_phi
);
3023 table
->nary
= htab_create (23, vn_nary_op_hash
, vn_nary_op_eq
, NULL
);
3024 table
->references
= htab_create (23, vn_reference_hash
, vn_reference_eq
,
3027 gcc_obstack_init (&table
->nary_obstack
);
3028 table
->phis_pool
= create_alloc_pool ("VN phis",
3029 sizeof (struct vn_phi_s
),
3031 table
->references_pool
= create_alloc_pool ("VN references",
3032 sizeof (struct vn_reference_s
),
3036 /* Free a value number table. */
3039 free_vn_table (vn_tables_t table
)
3041 htab_delete (table
->phis
);
3042 htab_delete (table
->nary
);
3043 htab_delete (table
->references
);
3044 obstack_free (&table
->nary_obstack
, NULL
);
3045 free_alloc_pool (table
->phis_pool
);
3046 free_alloc_pool (table
->references_pool
);
3054 int *rpo_numbers_temp
;
3056 calculate_dominance_info (CDI_DOMINATORS
);
3058 constant_to_value_id
= htab_create (23, vn_constant_hash
, vn_constant_eq
,
3061 constant_value_ids
= BITMAP_ALLOC (NULL
);
3066 vn_ssa_aux_table
= VEC_alloc (vn_ssa_aux_t
, heap
, num_ssa_names
+ 1);
3067 /* VEC_alloc doesn't actually grow it to the right size, it just
3068 preallocates the space to do so. */
3069 VEC_safe_grow_cleared (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
, num_ssa_names
+ 1);
3070 gcc_obstack_init (&vn_ssa_aux_obstack
);
3072 shared_lookup_phiargs
= NULL
;
3073 shared_lookup_references
= NULL
;
3074 rpo_numbers
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
3075 rpo_numbers_temp
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
3076 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
3078 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3079 the i'th block in RPO order is bb. We want to map bb's to RPO
3080 numbers, so we need to rearrange this array. */
3081 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
3082 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
3084 XDELETE (rpo_numbers_temp
);
3086 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
3088 /* Create the VN_INFO structures, and initialize value numbers to
3090 for (i
= 0; i
< num_ssa_names
; i
++)
3092 tree name
= ssa_name (i
);
3095 VN_INFO_GET (name
)->valnum
= VN_TOP
;
3096 VN_INFO (name
)->expr
= NULL_TREE
;
3097 VN_INFO (name
)->value_id
= 0;
3101 renumber_gimple_stmt_uids ();
3103 /* Create the valid and optimistic value numbering tables. */
3104 valid_info
= XCNEW (struct vn_tables_s
);
3105 allocate_vn_table (valid_info
);
3106 optimistic_info
= XCNEW (struct vn_tables_s
);
3107 allocate_vn_table (optimistic_info
);
3115 htab_delete (constant_to_value_id
);
3116 BITMAP_FREE (constant_value_ids
);
3117 VEC_free (tree
, heap
, shared_lookup_phiargs
);
3118 VEC_free (vn_reference_op_s
, heap
, shared_lookup_references
);
3119 XDELETEVEC (rpo_numbers
);
3121 for (i
= 0; i
< num_ssa_names
; i
++)
3123 tree name
= ssa_name (i
);
3125 && VN_INFO (name
)->needs_insertion
)
3126 release_ssa_name (name
);
3128 obstack_free (&vn_ssa_aux_obstack
, NULL
);
3129 VEC_free (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
);
3131 VEC_free (tree
, heap
, sccstack
);
3132 free_vn_table (valid_info
);
3133 XDELETE (valid_info
);
3134 free_vn_table (optimistic_info
);
3135 XDELETE (optimistic_info
);
3138 /* Set the value ids in the valid hash tables. */
3141 set_hashtable_value_ids (void)
3148 /* Now set the value ids of the things we had put in the hash
3151 FOR_EACH_HTAB_ELEMENT (valid_info
->nary
,
3152 vno
, vn_nary_op_t
, hi
)
3156 if (TREE_CODE (vno
->result
) == SSA_NAME
)
3157 vno
->value_id
= VN_INFO (vno
->result
)->value_id
;
3158 else if (is_gimple_min_invariant (vno
->result
))
3159 vno
->value_id
= get_or_alloc_constant_value_id (vno
->result
);
3163 FOR_EACH_HTAB_ELEMENT (valid_info
->phis
,
3168 if (TREE_CODE (vp
->result
) == SSA_NAME
)
3169 vp
->value_id
= VN_INFO (vp
->result
)->value_id
;
3170 else if (is_gimple_min_invariant (vp
->result
))
3171 vp
->value_id
= get_or_alloc_constant_value_id (vp
->result
);
3175 FOR_EACH_HTAB_ELEMENT (valid_info
->references
,
3176 vr
, vn_reference_t
, hi
)
3180 if (TREE_CODE (vr
->result
) == SSA_NAME
)
3181 vr
->value_id
= VN_INFO (vr
->result
)->value_id
;
3182 else if (is_gimple_min_invariant (vr
->result
))
3183 vr
->value_id
= get_or_alloc_constant_value_id (vr
->result
);
3188 /* Do SCCVN. Returns true if it finished, false if we bailed out
3189 due to resource constraints. */
3192 run_scc_vn (bool may_insert_arg
)
3196 bool changed
= true;
3198 may_insert
= may_insert_arg
;
3201 current_info
= valid_info
;
3203 for (param
= DECL_ARGUMENTS (current_function_decl
);
3205 param
= TREE_CHAIN (param
))
3207 if (gimple_default_def (cfun
, param
) != NULL
)
3209 tree def
= gimple_default_def (cfun
, param
);
3210 VN_INFO (def
)->valnum
= def
;
3214 for (i
= 1; i
< num_ssa_names
; ++i
)
3216 tree name
= ssa_name (i
);
3218 && VN_INFO (name
)->visited
== false
3219 && !has_zero_uses (name
))
3228 /* Initialize the value ids. */
3230 for (i
= 1; i
< num_ssa_names
; ++i
)
3232 tree name
= ssa_name (i
);
3236 info
= VN_INFO (name
);
3237 if (info
->valnum
== name
3238 || info
->valnum
== VN_TOP
)
3239 info
->value_id
= get_next_value_id ();
3240 else if (is_gimple_min_invariant (info
->valnum
))
3241 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
3244 /* Propagate until they stop changing. */
3248 for (i
= 1; i
< num_ssa_names
; ++i
)
3250 tree name
= ssa_name (i
);
3254 info
= VN_INFO (name
);
3255 if (TREE_CODE (info
->valnum
) == SSA_NAME
3256 && info
->valnum
!= name
3257 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
3260 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
3265 set_hashtable_value_ids ();
3267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3269 fprintf (dump_file
, "Value numbers:\n");
3270 for (i
= 0; i
< num_ssa_names
; i
++)
3272 tree name
= ssa_name (i
);
3274 && VN_INFO (name
)->visited
3275 && SSA_VAL (name
) != name
)
3277 print_generic_expr (dump_file
, name
, 0);
3278 fprintf (dump_file
, " = ");
3279 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
3280 fprintf (dump_file
, "\n");
3289 /* Return the maximum value id we have ever seen. */
3292 get_max_value_id (void)
3294 return next_value_id
;
3297 /* Return the next unique value id. */
3300 get_next_value_id (void)
3302 return next_value_id
++;
3306 /* Compare two expressions E1 and E2 and return true if they are equal. */
3309 expressions_equal_p (tree e1
, tree e2
)
3311 /* The obvious case. */
3315 /* If only one of them is null, they cannot be equal. */
3319 /* Now perform the actual comparison. */
3320 if (TREE_CODE (e1
) == TREE_CODE (e2
)
3321 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
3328 /* Return true if the nary operation NARY may trap. This is a copy
3329 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
3332 vn_nary_may_trap (vn_nary_op_t nary
)
3336 bool honor_nans
= false;
3337 bool honor_snans
= false;
3338 bool fp_operation
= false;
3339 bool honor_trapv
= false;
3343 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
3344 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
3345 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
3348 fp_operation
= FLOAT_TYPE_P (type
);
3351 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
3352 honor_snans
= flag_signaling_nans
!= 0;
3354 else if (INTEGRAL_TYPE_P (type
)
3355 && TYPE_OVERFLOW_TRAPS (type
))
3359 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
3361 honor_nans
, honor_snans
, rhs2
,
3367 for (i
= 0; i
< nary
->length
; ++i
)
3368 if (tree_could_trap_p (nary
->op
[i
]))