1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007, 2008
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 expr
= fold_build1 (gimple_assign_rhs_code (def_stmt
),
264 gimple_expr_type (def_stmt
),
265 TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0));
269 expr
= fold_build1 (gimple_assign_rhs_code (def_stmt
),
270 gimple_expr_type (def_stmt
),
271 gimple_assign_rhs1 (def_stmt
));
275 expr
= fold_build2 (gimple_assign_rhs_code (def_stmt
),
276 gimple_expr_type (def_stmt
),
277 gimple_assign_rhs1 (def_stmt
),
278 gimple_assign_rhs2 (def_stmt
));
283 if (expr
== NULL_TREE
)
286 /* Cache the expression. */
293 /* Free a phi operation structure VP. */
298 vn_phi_t phi
= (vn_phi_t
) vp
;
299 VEC_free (tree
, heap
, phi
->phiargs
);
302 /* Free a reference operation structure VP. */
305 free_reference (void *vp
)
307 vn_reference_t vr
= (vn_reference_t
) vp
;
308 VEC_free (vn_reference_op_s
, heap
, vr
->operands
);
311 /* Hash table equality function for vn_constant_t. */
314 vn_constant_eq (const void *p1
, const void *p2
)
316 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
317 const struct vn_constant_s
*vc2
= (const struct vn_constant_s
*) p2
;
319 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
322 /* Hash table hash function for vn_constant_t. */
325 vn_constant_hash (const void *p1
)
327 const struct vn_constant_s
*vc1
= (const struct vn_constant_s
*) p1
;
328 return vc1
->hashcode
;
331 /* Lookup a value id for CONSTANT and return it. If it does not
335 get_constant_value_id (tree constant
)
338 struct vn_constant_s vc
;
340 vc
.hashcode
= vn_hash_constant_with_type (constant
);
341 vc
.constant
= constant
;
342 slot
= htab_find_slot_with_hash (constant_to_value_id
, &vc
,
343 vc
.hashcode
, NO_INSERT
);
345 return ((vn_constant_t
)*slot
)->value_id
;
349 /* Lookup a value id for CONSTANT, and if it does not exist, create a
350 new one and return it. If it does exist, return it. */
353 get_or_alloc_constant_value_id (tree constant
)
356 vn_constant_t vc
= XNEW (struct vn_constant_s
);
358 vc
->hashcode
= vn_hash_constant_with_type (constant
);
359 vc
->constant
= constant
;
360 slot
= htab_find_slot_with_hash (constant_to_value_id
, vc
,
361 vc
->hashcode
, INSERT
);
365 return ((vn_constant_t
)*slot
)->value_id
;
367 vc
->value_id
= get_next_value_id ();
369 bitmap_set_bit (constant_value_ids
, vc
->value_id
);
373 /* Return true if V is a value id for a constant. */
376 value_id_constant_p (unsigned int v
)
378 return bitmap_bit_p (constant_value_ids
, v
);
381 /* Compare two reference operands P1 and P2 for equality. Return true if
382 they are equal, and false otherwise. */
385 vn_reference_op_eq (const void *p1
, const void *p2
)
387 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
388 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
389 return vro1
->opcode
== vro2
->opcode
390 && vro1
->type
== vro2
->type
391 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
392 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
393 && expressions_equal_p (vro1
->op2
, vro2
->op2
);
396 /* Compute the hash for a reference operand VRO1. */
399 vn_reference_op_compute_hash (const vn_reference_op_t vro1
)
401 return iterative_hash_expr (vro1
->op0
, vro1
->opcode
)
402 + iterative_hash_expr (vro1
->op1
, vro1
->opcode
)
403 + iterative_hash_expr (vro1
->op2
, vro1
->opcode
);
406 /* Return the hashcode for a given reference operation P1. */
409 vn_reference_hash (const void *p1
)
411 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
412 return vr1
->hashcode
;
415 /* Compute a hash for the reference operation VR1 and return it. */
418 vn_reference_compute_hash (const vn_reference_t vr1
)
420 hashval_t result
= 0;
423 vn_reference_op_t vro
;
425 for (i
= 0; VEC_iterate (tree
, vr1
->vuses
, i
, v
); i
++)
426 result
+= iterative_hash_expr (v
, 0);
427 for (i
= 0; VEC_iterate (vn_reference_op_s
, vr1
->operands
, i
, vro
); i
++)
428 result
+= vn_reference_op_compute_hash (vro
);
433 /* Return true if reference operations P1 and P2 are equivalent. This
434 means they have the same set of operands and vuses. */
437 vn_reference_eq (const void *p1
, const void *p2
)
441 vn_reference_op_t vro
;
443 const_vn_reference_t
const vr1
= (const_vn_reference_t
) p1
;
444 const_vn_reference_t
const vr2
= (const_vn_reference_t
) p2
;
446 if (vr1
->vuses
== vr2
->vuses
447 && vr1
->operands
== vr2
->operands
)
450 /* Impossible for them to be equivalent if they have different
452 if (VEC_length (tree
, vr1
->vuses
) != VEC_length (tree
, vr2
->vuses
))
455 /* We require that address operands be canonicalized in a way that
456 two memory references will have the same operands if they are
458 if (VEC_length (vn_reference_op_s
, vr1
->operands
)
459 != VEC_length (vn_reference_op_s
, vr2
->operands
))
462 /* The memory state is more often different than the address of the
463 store/load, so check it first. */
464 for (i
= 0; VEC_iterate (tree
, vr1
->vuses
, i
, v
); i
++)
466 if (VEC_index (tree
, vr2
->vuses
, i
) != v
)
470 for (i
= 0; VEC_iterate (vn_reference_op_s
, vr1
->operands
, i
, vro
); i
++)
472 if (!vn_reference_op_eq (VEC_index (vn_reference_op_s
, vr2
->operands
, i
),
479 /* Place the vuses from STMT into *result. */
482 vuses_to_vec (gimple stmt
, VEC (tree
, gc
) **result
)
490 VEC_reserve_exact (tree
, gc
, *result
,
491 num_ssa_operands (stmt
, SSA_OP_VIRTUAL_USES
));
493 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
494 VEC_quick_push (tree
, *result
, vuse
);
498 /* Copy the VUSE names in STMT into a vector, and return
502 copy_vuses_from_stmt (gimple stmt
)
504 VEC (tree
, gc
) *vuses
= NULL
;
506 vuses_to_vec (stmt
, &vuses
);
511 /* Place the vdefs from STMT into *result. */
514 vdefs_to_vec (gimple stmt
, VEC (tree
, gc
) **result
)
522 *result
= VEC_alloc (tree
, gc
, num_ssa_operands (stmt
, SSA_OP_VIRTUAL_DEFS
));
524 FOR_EACH_SSA_TREE_OPERAND (vdef
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
525 VEC_quick_push (tree
, *result
, vdef
);
528 /* Copy the names of vdef results in STMT into a vector, and return
531 static VEC (tree
, gc
) *
532 copy_vdefs_from_stmt (gimple stmt
)
534 VEC (tree
, gc
) *vdefs
= NULL
;
536 vdefs_to_vec (stmt
, &vdefs
);
541 /* Place for shared_v{uses/defs}_from_stmt to shove vuses/vdefs. */
542 static VEC (tree
, gc
) *shared_lookup_vops
;
544 /* Copy the virtual uses from STMT into SHARED_LOOKUP_VOPS.
545 This function will overwrite the current SHARED_LOOKUP_VOPS
549 shared_vuses_from_stmt (gimple stmt
)
551 VEC_truncate (tree
, shared_lookup_vops
, 0);
552 vuses_to_vec (stmt
, &shared_lookup_vops
);
554 return shared_lookup_vops
;
557 /* Copy the operations present in load/store REF into RESULT, a vector of
558 vn_reference_op_s's. */
561 copy_reference_ops_from_ref (tree ref
, VEC(vn_reference_op_s
, heap
) **result
)
563 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
565 vn_reference_op_s temp
;
567 memset (&temp
, 0, sizeof (temp
));
568 /* We do not care for spurious type qualifications. */
569 temp
.type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
570 temp
.opcode
= TREE_CODE (ref
);
571 temp
.op0
= TMR_SYMBOL (ref
) ? TMR_SYMBOL (ref
) : TMR_BASE (ref
);
572 temp
.op1
= TMR_INDEX (ref
);
573 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
575 memset (&temp
, 0, sizeof (temp
));
576 temp
.type
= NULL_TREE
;
577 temp
.opcode
= TREE_CODE (ref
);
578 temp
.op0
= TMR_STEP (ref
);
579 temp
.op1
= TMR_OFFSET (ref
);
580 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
584 /* For non-calls, store the information that makes up the address. */
588 vn_reference_op_s temp
;
590 memset (&temp
, 0, sizeof (temp
));
591 /* We do not care for spurious type qualifications. */
592 temp
.type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
593 temp
.opcode
= TREE_CODE (ref
);
597 case ALIGN_INDIRECT_REF
:
598 case MISALIGNED_INDIRECT_REF
:
600 /* The only operand is the address, which gets its own
601 vn_reference_op_s structure. */
604 /* Record bits and position. */
605 temp
.op0
= TREE_OPERAND (ref
, 1);
606 temp
.op1
= TREE_OPERAND (ref
, 2);
609 /* The field decl is enough to unambiguously specify the field,
610 a matching type is not necessary and a mismatching type
611 is always a spurious difference. */
612 temp
.type
= NULL_TREE
;
614 /* If this is a reference to a union member, record the union
615 member size as operand. Do so only if we are doing
616 expression insertion (during FRE), as PRE currently gets
617 confused with this. */
619 && TREE_CODE (DECL_CONTEXT (TREE_OPERAND (ref
, 1))) == UNION_TYPE
620 && integer_zerop (DECL_FIELD_OFFSET (TREE_OPERAND (ref
, 1)))
621 && integer_zerop (DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1))))
622 temp
.op0
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref
, 1)));
625 /* Record field as operand. */
626 temp
.op0
= TREE_OPERAND (ref
, 1);
627 temp
.op1
= TREE_OPERAND (ref
, 2);
629 case ARRAY_RANGE_REF
:
631 /* Record index as operand. */
632 temp
.op0
= TREE_OPERAND (ref
, 1);
633 temp
.op1
= TREE_OPERAND (ref
, 2);
634 temp
.op2
= TREE_OPERAND (ref
, 3);
649 /* These are only interesting for their operands, their
650 existence, and their type. They will never be the last
651 ref in the chain of references (IE they require an
652 operand), so we don't have to put anything
653 for op* as it will be handled by the iteration */
656 case VIEW_CONVERT_EXPR
:
663 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
665 if (REFERENCE_CLASS_P (ref
) || TREE_CODE (ref
) == ADDR_EXPR
)
666 ref
= TREE_OPERAND (ref
, 0);
672 /* Copy the operations present in load/store/call REF into RESULT, a vector of
673 vn_reference_op_s's. */
676 copy_reference_ops_from_call (gimple call
,
677 VEC(vn_reference_op_s
, heap
) **result
)
679 vn_reference_op_s temp
;
683 /* Copy the call_expr opcode, type, function being called, and
685 memset (&temp
, 0, sizeof (temp
));
686 temp
.type
= gimple_call_return_type (call
);
687 temp
.opcode
= CALL_EXPR
;
688 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
691 We make no attempt to simplify the called function because
692 the typical &FUNCTION_DECL form is also used in function pointer
693 cases that become constant. If we simplify the original to
694 FUNCTION_DECL but not the function pointer case (which can
695 happen because we have no fold functions that operate on
696 vn_reference_t), we will claim they are not equivalent.
698 An example of this behavior can be see if CALL_EXPR_FN below is
699 replaced with get_callee_fndecl and gcc.dg/tree-ssa/ssa-pre-13.c
701 callfn
= gimple_call_fn (call
);
702 temp
.type
= TREE_TYPE (callfn
);
703 temp
.opcode
= TREE_CODE (callfn
);
705 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
707 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
709 tree callarg
= gimple_call_arg (call
, i
);
710 memset (&temp
, 0, sizeof (temp
));
711 temp
.type
= TREE_TYPE (callarg
);
712 temp
.opcode
= TREE_CODE (callarg
);
714 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
719 /* Create a vector of vn_reference_op_s structures from REF, a
720 REFERENCE_CLASS_P tree. The vector is not shared. */
722 static VEC(vn_reference_op_s
, heap
) *
723 create_reference_ops_from_ref (tree ref
)
725 VEC (vn_reference_op_s
, heap
) *result
= NULL
;
727 copy_reference_ops_from_ref (ref
, &result
);
731 /* Create a vector of vn_reference_op_s structures from CALL, a
732 call statement. The vector is not shared. */
734 static VEC(vn_reference_op_s
, heap
) *
735 create_reference_ops_from_call (gimple call
)
737 VEC (vn_reference_op_s
, heap
) *result
= NULL
;
739 copy_reference_ops_from_call (call
, &result
);
743 static VEC(vn_reference_op_s
, heap
) *shared_lookup_references
;
745 /* Create a vector of vn_reference_op_s structures from REF, a
746 REFERENCE_CLASS_P tree. The vector is shared among all callers of
749 static VEC(vn_reference_op_s
, heap
) *
750 shared_reference_ops_from_ref (tree ref
)
754 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
755 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
756 return shared_lookup_references
;
759 /* Create a vector of vn_reference_op_s structures from CALL, a
760 call statement. The vector is shared among all callers of
763 static VEC(vn_reference_op_s
, heap
) *
764 shared_reference_ops_from_call (gimple call
)
768 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
769 copy_reference_ops_from_call (call
, &shared_lookup_references
);
770 return shared_lookup_references
;
774 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
775 structures into their value numbers. This is done in-place, and
776 the vector passed in is returned. */
778 static VEC (vn_reference_op_s
, heap
) *
779 valueize_refs (VEC (vn_reference_op_s
, heap
) *orig
)
781 vn_reference_op_t vro
;
784 for (i
= 0; VEC_iterate (vn_reference_op_s
, orig
, i
, vro
); i
++)
786 if (vro
->opcode
== SSA_NAME
787 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
789 vro
->op0
= SSA_VAL (vro
->op0
);
790 /* If it transforms from an SSA_NAME to a constant, update
792 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
793 vro
->opcode
= TREE_CODE (vro
->op0
);
795 /* TODO: Do we want to valueize op2 and op1 of
796 ARRAY_REF/COMPONENT_REF for Ada */
803 /* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
804 their value numbers. This is done in-place, and the vector passed
807 static VEC (tree
, gc
) *
808 valueize_vuses (VEC (tree
, gc
) *orig
)
810 bool made_replacement
= false;
814 for (i
= 0; VEC_iterate (tree
, orig
, i
, vuse
); i
++)
816 if (vuse
!= SSA_VAL (vuse
))
818 made_replacement
= true;
819 VEC_replace (tree
, orig
, i
, SSA_VAL (vuse
));
823 if (made_replacement
&& VEC_length (tree
, orig
) > 1)
829 /* Return the single reference statement defining all virtual uses
830 in VUSES or NULL_TREE, if there are multiple defining statements.
831 Take into account only definitions that alias REF if following
835 get_def_ref_stmt_vuses (tree ref
, VEC (tree
, gc
) *vuses
)
841 gcc_assert (VEC_length (tree
, vuses
) >= 1);
843 def_stmt
= SSA_NAME_DEF_STMT (VEC_index (tree
, vuses
, 0));
844 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
846 /* We can only handle lookups over PHI nodes for a single
848 if (VEC_length (tree
, vuses
) == 1)
850 def_stmt
= get_single_def_stmt_from_phi (ref
, def_stmt
);
857 /* Verify each VUSE reaches the same defining stmt. */
858 for (i
= 1; VEC_iterate (tree
, vuses
, i
, vuse
); ++i
)
860 gimple tmp
= SSA_NAME_DEF_STMT (vuse
);
865 /* Now see if the definition aliases ref, and loop until it does. */
868 && is_gimple_assign (def_stmt
)
869 && !refs_may_alias_p (ref
, gimple_get_lhs (def_stmt
)))
870 def_stmt
= get_single_def_stmt_with_phi (ref
, def_stmt
);
875 /* Lookup a SCCVN reference operation VR in the current hash table.
876 Returns the resulting value number if it exists in the hash table,
877 NULL_TREE otherwise. VNRESULT will be filled in with the actual
878 vn_reference_t stored in the hashtable if something is found. */
881 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
887 slot
= htab_find_slot_with_hash (current_info
->references
, vr
,
889 if (!slot
&& current_info
== optimistic_info
)
890 slot
= htab_find_slot_with_hash (valid_info
->references
, vr
,
895 *vnresult
= (vn_reference_t
)*slot
;
896 return ((vn_reference_t
)*slot
)->result
;
903 /* Lookup a reference operation by it's parts, in the current hash table.
904 Returns the resulting value number if it exists in the hash table,
905 NULL_TREE otherwise. VNRESULT will be filled in with the actual
906 vn_reference_t stored in the hashtable if something is found. */
909 vn_reference_lookup_pieces (VEC (tree
, gc
) *vuses
,
910 VEC (vn_reference_op_s
, heap
) *operands
,
911 vn_reference_t
*vnresult
)
913 struct vn_reference_s vr1
;
918 vr1
.vuses
= valueize_vuses (vuses
);
919 vr1
.operands
= valueize_refs (operands
);
920 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
921 result
= vn_reference_lookup_1 (&vr1
, vnresult
);
926 /* Lookup OP in the current hash table, and return the resulting value
927 number if it exists in the hash table. Return NULL_TREE if it does
928 not exist in the hash table or if the result field of the structure
929 was NULL.. VNRESULT will be filled in with the vn_reference_t
930 stored in the hashtable if one exists. */
933 vn_reference_lookup (tree op
, VEC (tree
, gc
) *vuses
, bool maywalk
,
934 vn_reference_t
*vnresult
)
936 struct vn_reference_s vr1
;
942 vr1
.vuses
= valueize_vuses (vuses
);
943 vr1
.operands
= valueize_refs (shared_reference_ops_from_ref (op
));
944 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
945 result
= vn_reference_lookup_1 (&vr1
, vnresult
);
947 /* If there is a single defining statement for all virtual uses, we can
948 use that, following virtual use-def chains. */
952 && VEC_length (tree
, vr1
.vuses
) >= 1
953 && (def_stmt
= get_def_ref_stmt_vuses (op
, vr1
.vuses
))
954 && is_gimple_assign (def_stmt
))
956 /* We are now at an aliasing definition for the vuses we want to
957 look up. Re-do the lookup with the vdefs for this stmt. */
958 vdefs_to_vec (def_stmt
, &vuses
);
959 vr1
.vuses
= valueize_vuses (vuses
);
960 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
961 result
= vn_reference_lookup_1 (&vr1
, vnresult
);
968 /* Insert OP into the current hash table with a value number of
969 RESULT, and return the resulting reference structure we created. */
972 vn_reference_insert (tree op
, tree result
, VEC (tree
, gc
) *vuses
)
977 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
978 if (TREE_CODE (result
) == SSA_NAME
)
979 vr1
->value_id
= VN_INFO (result
)->value_id
;
981 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
982 vr1
->vuses
= valueize_vuses (vuses
);
983 vr1
->operands
= valueize_refs (create_reference_ops_from_ref (op
));
984 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
985 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
987 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
990 /* Because we lookup stores using vuses, and value number failures
991 using the vdefs (see visit_reference_op_store for how and why),
992 it's possible that on failure we may try to insert an already
993 inserted store. This is not wrong, there is no ssa name for a
994 store that we could use as a differentiator anyway. Thus, unlike
995 the other lookup functions, you cannot gcc_assert (!*slot)
998 /* But free the old slot in case of a collision. */
1000 free_reference (*slot
);
1006 /* Insert a reference by it's pieces into the current hash table with
1007 a value number of RESULT. Return the resulting reference
1008 structure we created. */
1011 vn_reference_insert_pieces (VEC (tree
, gc
) *vuses
,
1012 VEC (vn_reference_op_s
, heap
) *operands
,
1013 tree result
, unsigned int value_id
)
1019 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
1020 vr1
->value_id
= value_id
;
1021 vr1
->vuses
= valueize_vuses (vuses
);
1022 vr1
->operands
= valueize_refs (operands
);
1023 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
1024 if (result
&& TREE_CODE (result
) == SSA_NAME
)
1025 result
= SSA_VAL (result
);
1026 vr1
->result
= result
;
1028 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
1031 /* At this point we should have all the things inserted that we have
1032 seen before, and we should never try inserting something that
1034 gcc_assert (!*slot
);
1036 free_reference (*slot
);
1042 /* Compute and return the hash value for nary operation VBO1. */
1045 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
1050 for (i
= 0; i
< vno1
->length
; ++i
)
1051 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
1052 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
1054 if (vno1
->length
== 2
1055 && commutative_tree_code (vno1
->opcode
)
1056 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1], false))
1058 tree temp
= vno1
->op
[0];
1059 vno1
->op
[0] = vno1
->op
[1];
1063 for (i
= 0; i
< vno1
->length
; ++i
)
1064 hash
+= iterative_hash_expr (vno1
->op
[i
], vno1
->opcode
);
1069 /* Return the computed hashcode for nary operation P1. */
1072 vn_nary_op_hash (const void *p1
)
1074 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
1075 return vno1
->hashcode
;
1078 /* Compare nary operations P1 and P2 and return true if they are
1082 vn_nary_op_eq (const void *p1
, const void *p2
)
1084 const_vn_nary_op_t
const vno1
= (const_vn_nary_op_t
) p1
;
1085 const_vn_nary_op_t
const vno2
= (const_vn_nary_op_t
) p2
;
1088 if (vno1
->opcode
!= vno2
->opcode
1089 || vno1
->type
!= vno2
->type
)
1092 for (i
= 0; i
< vno1
->length
; ++i
)
1093 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
1099 /* Lookup a n-ary operation by its pieces and return the resulting value
1100 number if it exists in the hash table. Return NULL_TREE if it does
1101 not exist in the hash table or if the result field of the operation
1102 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1106 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
1107 tree type
, tree op0
, tree op1
, tree op2
,
1108 tree op3
, vn_nary_op_t
*vnresult
)
1111 struct vn_nary_op_s vno1
;
1115 vno1
.length
= length
;
1121 vno1
.hashcode
= vn_nary_op_compute_hash (&vno1
);
1122 slot
= htab_find_slot_with_hash (current_info
->nary
, &vno1
, vno1
.hashcode
,
1124 if (!slot
&& current_info
== optimistic_info
)
1125 slot
= htab_find_slot_with_hash (valid_info
->nary
, &vno1
, vno1
.hashcode
,
1130 *vnresult
= (vn_nary_op_t
)*slot
;
1131 return ((vn_nary_op_t
)*slot
)->result
;
1134 /* Lookup OP in the current hash table, and return the resulting value
1135 number if it exists in the hash table. Return NULL_TREE if it does
1136 not exist in the hash table or if the result field of the operation
1137 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1141 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
1144 struct vn_nary_op_s vno1
;
1149 vno1
.opcode
= TREE_CODE (op
);
1150 vno1
.length
= TREE_CODE_LENGTH (TREE_CODE (op
));
1151 vno1
.type
= TREE_TYPE (op
);
1152 for (i
= 0; i
< vno1
.length
; ++i
)
1153 vno1
.op
[i
] = TREE_OPERAND (op
, i
);
1154 vno1
.hashcode
= vn_nary_op_compute_hash (&vno1
);
1155 slot
= htab_find_slot_with_hash (current_info
->nary
, &vno1
, vno1
.hashcode
,
1157 if (!slot
&& current_info
== optimistic_info
)
1158 slot
= htab_find_slot_with_hash (valid_info
->nary
, &vno1
, vno1
.hashcode
,
1163 *vnresult
= (vn_nary_op_t
)*slot
;
1164 return ((vn_nary_op_t
)*slot
)->result
;
1167 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1168 value number if it exists in the hash table. Return NULL_TREE if
1169 it does not exist in the hash table. VNRESULT will contain the
1170 vn_nary_op_t from the hashtable if it exists. */
1173 vn_nary_op_lookup_stmt (gimple stmt
, vn_nary_op_t
*vnresult
)
1176 struct vn_nary_op_s vno1
;
1181 vno1
.opcode
= gimple_assign_rhs_code (stmt
);
1182 vno1
.length
= gimple_num_ops (stmt
) - 1;
1183 vno1
.type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1184 for (i
= 0; i
< vno1
.length
; ++i
)
1185 vno1
.op
[i
] = gimple_op (stmt
, i
+ 1);
1186 vno1
.hashcode
= vn_nary_op_compute_hash (&vno1
);
1187 slot
= htab_find_slot_with_hash (current_info
->nary
, &vno1
, vno1
.hashcode
,
1189 if (!slot
&& current_info
== optimistic_info
)
1190 slot
= htab_find_slot_with_hash (valid_info
->nary
, &vno1
, vno1
.hashcode
,
1195 *vnresult
= (vn_nary_op_t
)*slot
;
1196 return ((vn_nary_op_t
)*slot
)->result
;
1199 /* Insert a n-ary operation into the current hash table using it's
1200 pieces. Return the vn_nary_op_t structure we created and put in
1204 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
1205 tree type
, tree op0
,
1206 tree op1
, tree op2
, tree op3
,
1208 unsigned int value_id
)
1213 vno1
= (vn_nary_op_t
) obstack_alloc (¤t_info
->nary_obstack
,
1214 (sizeof (struct vn_nary_op_s
)
1215 - sizeof (tree
) * (4 - length
)));
1216 vno1
->value_id
= value_id
;
1217 vno1
->opcode
= code
;
1218 vno1
->length
= length
;
1228 vno1
->result
= result
;
1229 vno1
->hashcode
= vn_nary_op_compute_hash (vno1
);
1230 slot
= htab_find_slot_with_hash (current_info
->nary
, vno1
, vno1
->hashcode
,
1232 gcc_assert (!*slot
);
1239 /* Insert OP into the current hash table with a value number of
1240 RESULT. Return the vn_nary_op_t structure we created and put in
1244 vn_nary_op_insert (tree op
, tree result
)
1246 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
1251 vno1
= (vn_nary_op_t
) obstack_alloc (¤t_info
->nary_obstack
,
1252 (sizeof (struct vn_nary_op_s
)
1253 - sizeof (tree
) * (4 - length
)));
1254 vno1
->value_id
= VN_INFO (result
)->value_id
;
1255 vno1
->opcode
= TREE_CODE (op
);
1256 vno1
->length
= length
;
1257 vno1
->type
= TREE_TYPE (op
);
1258 for (i
= 0; i
< vno1
->length
; ++i
)
1259 vno1
->op
[i
] = TREE_OPERAND (op
, i
);
1260 vno1
->result
= result
;
1261 vno1
->hashcode
= vn_nary_op_compute_hash (vno1
);
1262 slot
= htab_find_slot_with_hash (current_info
->nary
, vno1
, vno1
->hashcode
,
1264 gcc_assert (!*slot
);
1270 /* Insert the rhs of STMT into the current hash table with a value number of
1274 vn_nary_op_insert_stmt (gimple stmt
, tree result
)
1276 unsigned length
= gimple_num_ops (stmt
) - 1;
1281 vno1
= (vn_nary_op_t
) obstack_alloc (¤t_info
->nary_obstack
,
1282 (sizeof (struct vn_nary_op_s
)
1283 - sizeof (tree
) * (4 - length
)));
1284 vno1
->value_id
= VN_INFO (result
)->value_id
;
1285 vno1
->opcode
= gimple_assign_rhs_code (stmt
);
1286 vno1
->length
= length
;
1287 vno1
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1288 for (i
= 0; i
< vno1
->length
; ++i
)
1289 vno1
->op
[i
] = gimple_op (stmt
, i
+ 1);
1290 vno1
->result
= result
;
1291 vno1
->hashcode
= vn_nary_op_compute_hash (vno1
);
1292 slot
= htab_find_slot_with_hash (current_info
->nary
, vno1
, vno1
->hashcode
,
1294 gcc_assert (!*slot
);
1300 /* Compute a hashcode for PHI operation VP1 and return it. */
1302 static inline hashval_t
1303 vn_phi_compute_hash (vn_phi_t vp1
)
1305 hashval_t result
= 0;
1309 result
= vp1
->block
->index
;
1311 for (i
= 0; VEC_iterate (tree
, vp1
->phiargs
, i
, phi1op
); i
++)
1313 if (phi1op
== VN_TOP
)
1315 result
+= iterative_hash_expr (phi1op
, result
);
1321 /* Return the computed hashcode for phi operation P1. */
1324 vn_phi_hash (const void *p1
)
1326 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
1327 return vp1
->hashcode
;
1330 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1333 vn_phi_eq (const void *p1
, const void *p2
)
1335 const_vn_phi_t
const vp1
= (const_vn_phi_t
) p1
;
1336 const_vn_phi_t
const vp2
= (const_vn_phi_t
) p2
;
1338 if (vp1
->block
== vp2
->block
)
1343 /* Any phi in the same block will have it's arguments in the
1344 same edge order, because of how we store phi nodes. */
1345 for (i
= 0; VEC_iterate (tree
, vp1
->phiargs
, i
, phi1op
); i
++)
1347 tree phi2op
= VEC_index (tree
, vp2
->phiargs
, i
);
1348 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
1350 if (!expressions_equal_p (phi1op
, phi2op
))
1358 static VEC(tree
, heap
) *shared_lookup_phiargs
;
1360 /* Lookup PHI in the current hash table, and return the resulting
1361 value number if it exists in the hash table. Return NULL_TREE if
1362 it does not exist in the hash table. */
1365 vn_phi_lookup (gimple phi
)
1368 struct vn_phi_s vp1
;
1371 VEC_truncate (tree
, shared_lookup_phiargs
, 0);
1373 /* Canonicalize the SSA_NAME's to their value number. */
1374 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1376 tree def
= PHI_ARG_DEF (phi
, i
);
1377 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
1378 VEC_safe_push (tree
, heap
, shared_lookup_phiargs
, def
);
1380 vp1
.phiargs
= shared_lookup_phiargs
;
1381 vp1
.block
= gimple_bb (phi
);
1382 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
1383 slot
= htab_find_slot_with_hash (current_info
->phis
, &vp1
, vp1
.hashcode
,
1385 if (!slot
&& current_info
== optimistic_info
)
1386 slot
= htab_find_slot_with_hash (valid_info
->phis
, &vp1
, vp1
.hashcode
,
1390 return ((vn_phi_t
)*slot
)->result
;
1393 /* Insert PHI into the current hash table with a value number of
1397 vn_phi_insert (gimple phi
, tree result
)
1400 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
1402 VEC (tree
, heap
) *args
= NULL
;
1404 /* Canonicalize the SSA_NAME's to their value number. */
1405 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1407 tree def
= PHI_ARG_DEF (phi
, i
);
1408 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
1409 VEC_safe_push (tree
, heap
, args
, def
);
1411 vp1
->value_id
= VN_INFO (result
)->value_id
;
1412 vp1
->phiargs
= args
;
1413 vp1
->block
= gimple_bb (phi
);
1414 vp1
->result
= result
;
1415 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
1417 slot
= htab_find_slot_with_hash (current_info
->phis
, vp1
, vp1
->hashcode
,
1420 /* Because we iterate over phi operations more than once, it's
1421 possible the slot might already exist here, hence no assert.*/
1427 /* Print set of components in strongly connected component SCC to OUT. */
1430 print_scc (FILE *out
, VEC (tree
, heap
) *scc
)
1435 fprintf (out
, "SCC consists of: ");
1436 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
1438 print_generic_expr (out
, var
, 0);
1441 fprintf (out
, "\n");
1444 /* Set the value number of FROM to TO, return true if it has changed
1448 set_ssa_val_to (tree from
, tree to
)
1453 && TREE_CODE (to
) == SSA_NAME
1454 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
1457 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1458 and invariants. So assert that here. */
1459 gcc_assert (to
!= NULL_TREE
1461 || TREE_CODE (to
) == SSA_NAME
1462 || is_gimple_min_invariant (to
)));
1464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1466 fprintf (dump_file
, "Setting value number of ");
1467 print_generic_expr (dump_file
, from
, 0);
1468 fprintf (dump_file
, " to ");
1469 print_generic_expr (dump_file
, to
, 0);
1470 fprintf (dump_file
, "\n");
1473 currval
= SSA_VAL (from
);
1475 if (currval
!= to
&& !operand_equal_p (currval
, to
, OEP_PURE_SAME
))
1477 SSA_VAL (from
) = to
;
1483 /* Set all definitions in STMT to value number to themselves.
1484 Return true if a value number changed. */
1487 defs_to_varying (gimple stmt
)
1489 bool changed
= false;
1493 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1495 tree def
= DEF_FROM_PTR (defp
);
1497 VN_INFO (def
)->use_processed
= true;
1498 changed
|= set_ssa_val_to (def
, def
);
1503 static bool expr_has_constants (tree expr
);
1504 static tree
try_to_simplify (gimple stmt
);
1506 /* Visit a copy between LHS and RHS, return true if the value number
1510 visit_copy (tree lhs
, tree rhs
)
1512 /* Follow chains of copies to their destination. */
1513 while (SSA_VAL (rhs
) != rhs
&& TREE_CODE (SSA_VAL (rhs
)) == SSA_NAME
)
1514 rhs
= SSA_VAL (rhs
);
1516 /* The copy may have a more interesting constant filled expression
1517 (we don't, since we know our RHS is just an SSA name). */
1518 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
1519 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
1521 return set_ssa_val_to (lhs
, rhs
);
1524 /* Visit a unary operator RHS, value number it, and return true if the
1525 value number of LHS has changed as a result. */
1528 visit_unary_op (tree lhs
, gimple stmt
)
1530 bool changed
= false;
1531 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
1535 changed
= set_ssa_val_to (lhs
, result
);
1539 changed
= set_ssa_val_to (lhs
, lhs
);
1540 vn_nary_op_insert_stmt (stmt
, lhs
);
1546 /* Visit a binary operator RHS, value number it, and return true if the
1547 value number of LHS has changed as a result. */
1550 visit_binary_op (tree lhs
, gimple stmt
)
1552 bool changed
= false;
1553 tree result
= vn_nary_op_lookup_stmt (stmt
, NULL
);
1557 changed
= set_ssa_val_to (lhs
, result
);
1561 changed
= set_ssa_val_to (lhs
, lhs
);
1562 vn_nary_op_insert_stmt (stmt
, lhs
);
1568 /* Visit a call STMT storing into LHS. Return true if the value number
1569 of the LHS has changed as a result. */
1572 visit_reference_op_call (tree lhs
, gimple stmt
)
1574 bool changed
= false;
1575 struct vn_reference_s vr1
;
1578 vr1
.vuses
= valueize_vuses (shared_vuses_from_stmt (stmt
));
1579 vr1
.operands
= valueize_refs (shared_reference_ops_from_call (stmt
));
1580 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1581 result
= vn_reference_lookup_1 (&vr1
, NULL
);
1584 changed
= set_ssa_val_to (lhs
, result
);
1585 if (TREE_CODE (result
) == SSA_NAME
1586 && VN_INFO (result
)->has_constants
)
1587 VN_INFO (lhs
)->has_constants
= true;
1593 changed
= set_ssa_val_to (lhs
, lhs
);
1594 vr2
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
1595 vr2
->vuses
= valueize_vuses (copy_vuses_from_stmt (stmt
));
1596 vr2
->operands
= valueize_refs (create_reference_ops_from_call (stmt
));
1597 vr2
->hashcode
= vr1
.hashcode
;
1599 slot
= htab_find_slot_with_hash (current_info
->references
,
1600 vr2
, vr2
->hashcode
, INSERT
);
1602 free_reference (*slot
);
1609 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1610 and return true if the value number of the LHS has changed as a result. */
1613 visit_reference_op_load (tree lhs
, tree op
, gimple stmt
)
1615 bool changed
= false;
1616 tree result
= vn_reference_lookup (op
, shared_vuses_from_stmt (stmt
), true,
1619 /* We handle type-punning through unions by value-numbering based
1620 on offset and size of the access. Be prepared to handle a
1621 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1623 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
1625 /* We will be setting the value number of lhs to the value number
1626 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1627 So first simplify and lookup this expression to see if it
1628 is already available. */
1629 tree val
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
1631 && !is_gimple_min_invariant (val
)
1632 && TREE_CODE (val
) != SSA_NAME
)
1634 tree tem
= try_to_simplify (stmt
);
1639 if (!is_gimple_min_invariant (val
)
1640 && TREE_CODE (val
) != SSA_NAME
)
1641 result
= vn_nary_op_lookup (val
, NULL
);
1642 /* If the expression is not yet available, value-number lhs to
1643 a new SSA_NAME we create. */
1644 if (!result
&& may_insert
)
1646 result
= make_ssa_name (SSA_NAME_VAR (lhs
), NULL
);
1647 /* Initialize value-number information properly. */
1648 VN_INFO_GET (result
)->valnum
= result
;
1649 VN_INFO (result
)->value_id
= get_next_value_id ();
1650 VN_INFO (result
)->expr
= val
;
1651 VN_INFO (result
)->has_constants
= expr_has_constants (val
);
1652 VN_INFO (result
)->needs_insertion
= true;
1653 /* As all "inserted" statements are singleton SCCs, insert
1654 to the valid table. This is strictly needed to
1655 avoid re-generating new value SSA_NAMEs for the same
1656 expression during SCC iteration over and over (the
1657 optimistic table gets cleared after each iteration).
1658 We do not need to insert into the optimistic table, as
1659 lookups there will fall back to the valid table. */
1660 if (current_info
== optimistic_info
)
1662 current_info
= valid_info
;
1663 vn_nary_op_insert (val
, result
);
1664 current_info
= optimistic_info
;
1667 vn_nary_op_insert (val
, result
);
1668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1670 fprintf (dump_file
, "Inserting name ");
1671 print_generic_expr (dump_file
, result
, 0);
1672 fprintf (dump_file
, " for expression ");
1673 print_generic_expr (dump_file
, val
, 0);
1674 fprintf (dump_file
, "\n");
1681 changed
= set_ssa_val_to (lhs
, result
);
1682 if (TREE_CODE (result
) == SSA_NAME
1683 && VN_INFO (result
)->has_constants
)
1685 VN_INFO (lhs
)->expr
= VN_INFO (result
)->expr
;
1686 VN_INFO (lhs
)->has_constants
= true;
1691 changed
= set_ssa_val_to (lhs
, lhs
);
1692 vn_reference_insert (op
, lhs
, copy_vuses_from_stmt (stmt
));
1699 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1700 and return true if the value number of the LHS has changed as a result. */
1703 visit_reference_op_store (tree lhs
, tree op
, gimple stmt
)
1705 bool changed
= false;
1707 bool resultsame
= false;
1709 /* First we want to lookup using the *vuses* from the store and see
1710 if there the last store to this location with the same address
1713 The vuses represent the memory state before the store. If the
1714 memory state, address, and value of the store is the same as the
1715 last store to this location, then this store will produce the
1716 same memory state as that store.
1718 In this case the vdef versions for this store are value numbered to those
1719 vuse versions, since they represent the same memory state after
1722 Otherwise, the vdefs for the store are used when inserting into
1723 the table, since the store generates a new memory state. */
1725 result
= vn_reference_lookup (lhs
, shared_vuses_from_stmt (stmt
), false,
1730 if (TREE_CODE (result
) == SSA_NAME
)
1731 result
= SSA_VAL (result
);
1732 if (TREE_CODE (op
) == SSA_NAME
)
1734 resultsame
= expressions_equal_p (result
, op
);
1737 if (!result
|| !resultsame
)
1739 VEC(tree
, gc
) *vdefs
= copy_vdefs_from_stmt (stmt
);
1743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1745 fprintf (dump_file
, "No store match\n");
1746 fprintf (dump_file
, "Value numbering store ");
1747 print_generic_expr (dump_file
, lhs
, 0);
1748 fprintf (dump_file
, " to ");
1749 print_generic_expr (dump_file
, op
, 0);
1750 fprintf (dump_file
, "\n");
1752 /* Have to set value numbers before insert, since insert is
1753 going to valueize the references in-place. */
1754 for (i
= 0; VEC_iterate (tree
, vdefs
, i
, vdef
); i
++)
1756 VN_INFO (vdef
)->use_processed
= true;
1757 changed
|= set_ssa_val_to (vdef
, vdef
);
1760 /* Do not insert structure copies into the tables. */
1761 if (is_gimple_min_invariant (op
)
1762 || is_gimple_reg (op
))
1763 vn_reference_insert (lhs
, op
, vdefs
);
1767 /* We had a match, so value number the vdefs to have the value
1768 number of the vuses they came from. */
1769 ssa_op_iter op_iter
;
1773 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1774 fprintf (dump_file
, "Store matched earlier value,"
1775 "value numbering store vdefs to matching vuses.\n");
1777 FOR_EACH_SSA_VDEF_OPERAND (var
, vv
, stmt
, op_iter
)
1779 tree def
= DEF_FROM_PTR (var
);
1782 /* Uh, if the vuse is a multiuse, we can't really do much
1783 here, sadly, since we don't know which value number of
1784 which vuse to use. */
1785 if (VUSE_VECT_NUM_ELEM (*vv
) != 1)
1788 use
= VUSE_ELEMENT_VAR (*vv
, 0);
1790 VN_INFO (def
)->use_processed
= true;
1791 changed
|= set_ssa_val_to (def
, SSA_VAL (use
));
1798 /* Visit and value number PHI, return true if the value number
1802 visit_phi (gimple phi
)
1804 bool changed
= false;
1806 tree sameval
= VN_TOP
;
1807 bool allsame
= true;
1810 /* TODO: We could check for this in init_sccvn, and replace this
1811 with a gcc_assert. */
1812 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1813 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
1815 /* See if all non-TOP arguments have the same value. TOP is
1816 equivalent to everything, so we can ignore it. */
1817 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1819 tree def
= PHI_ARG_DEF (phi
, i
);
1821 if (TREE_CODE (def
) == SSA_NAME
)
1822 def
= SSA_VAL (def
);
1825 if (sameval
== VN_TOP
)
1831 if (!expressions_equal_p (def
, sameval
))
1839 /* If all value numbered to the same value, the phi node has that
1843 if (is_gimple_min_invariant (sameval
))
1845 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
1846 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
1850 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
1851 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
1854 if (TREE_CODE (sameval
) == SSA_NAME
)
1855 return visit_copy (PHI_RESULT (phi
), sameval
);
1857 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
1860 /* Otherwise, see if it is equivalent to a phi node in this block. */
1861 result
= vn_phi_lookup (phi
);
1864 if (TREE_CODE (result
) == SSA_NAME
)
1865 changed
= visit_copy (PHI_RESULT (phi
), result
);
1867 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
1871 vn_phi_insert (phi
, PHI_RESULT (phi
));
1872 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
1873 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
1874 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
1880 /* Return true if EXPR contains constants. */
1883 expr_has_constants (tree expr
)
1885 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1888 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
1891 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
1892 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
1893 /* Constants inside reference ops are rarely interesting, but
1894 it can take a lot of looking to find them. */
1896 case tcc_declaration
:
1899 return is_gimple_min_invariant (expr
);
1904 /* Return true if STMT contains constants. */
1907 stmt_has_constants (gimple stmt
)
1909 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1912 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
1914 case GIMPLE_UNARY_RHS
:
1915 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
1917 case GIMPLE_BINARY_RHS
:
1918 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))
1919 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt
)));
1920 case GIMPLE_SINGLE_RHS
:
1921 /* Constants inside reference ops are rarely interesting, but
1922 it can take a lot of looking to find them. */
1923 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt
));
1930 /* Replace SSA_NAMES in expr with their value numbers, and return the
1932 This is performed in place. */
1935 valueize_expr (tree expr
)
1937 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1940 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
1941 && SSA_VAL (TREE_OPERAND (expr
, 0)) != VN_TOP
)
1942 TREE_OPERAND (expr
, 0) = SSA_VAL (TREE_OPERAND (expr
, 0));
1945 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
1946 && SSA_VAL (TREE_OPERAND (expr
, 0)) != VN_TOP
)
1947 TREE_OPERAND (expr
, 0) = SSA_VAL (TREE_OPERAND (expr
, 0));
1948 if (TREE_CODE (TREE_OPERAND (expr
, 1)) == SSA_NAME
1949 && SSA_VAL (TREE_OPERAND (expr
, 1)) != VN_TOP
)
1950 TREE_OPERAND (expr
, 1) = SSA_VAL (TREE_OPERAND (expr
, 1));
1958 /* Simplify the binary expression RHS, and return the result if
1962 simplify_binary_expression (gimple stmt
)
1964 tree result
= NULL_TREE
;
1965 tree op0
= gimple_assign_rhs1 (stmt
);
1966 tree op1
= gimple_assign_rhs2 (stmt
);
1968 /* This will not catch every single case we could combine, but will
1969 catch those with constants. The goal here is to simultaneously
1970 combine constants between expressions, but avoid infinite
1971 expansion of expressions during simplification. */
1972 if (TREE_CODE (op0
) == SSA_NAME
)
1974 if (VN_INFO (op0
)->has_constants
1975 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)) == tcc_comparison
)
1976 op0
= valueize_expr (vn_get_expr_for (op0
));
1977 else if (SSA_VAL (op0
) != VN_TOP
&& SSA_VAL (op0
) != op0
)
1978 op0
= SSA_VAL (op0
);
1981 if (TREE_CODE (op1
) == SSA_NAME
)
1983 if (VN_INFO (op1
)->has_constants
)
1984 op1
= valueize_expr (vn_get_expr_for (op1
));
1985 else if (SSA_VAL (op1
) != VN_TOP
&& SSA_VAL (op1
) != op1
)
1986 op1
= SSA_VAL (op1
);
1989 /* Avoid folding if nothing changed. */
1990 if (op0
== gimple_assign_rhs1 (stmt
)
1991 && op1
== gimple_assign_rhs2 (stmt
))
1994 fold_defer_overflow_warnings ();
1996 result
= fold_binary (gimple_assign_rhs_code (stmt
),
1997 TREE_TYPE (gimple_get_lhs (stmt
)), op0
, op1
);
1999 fold_undefer_overflow_warnings (result
&& valid_gimple_rhs_p (result
),
2002 /* Make sure result is not a complex expression consisting
2003 of operators of operators (IE (a + b) + (a + c))
2004 Otherwise, we will end up with unbounded expressions if
2005 fold does anything at all. */
2006 if (result
&& valid_gimple_rhs_p (result
))
2012 /* Simplify the unary expression RHS, and return the result if
2016 simplify_unary_expression (gimple stmt
)
2018 tree result
= NULL_TREE
;
2019 tree orig_op0
, op0
= gimple_assign_rhs1 (stmt
);
2021 /* We handle some tcc_reference codes here that are all
2022 GIMPLE_ASSIGN_SINGLE codes. */
2023 if (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
2024 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
2025 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
)
2026 op0
= TREE_OPERAND (op0
, 0);
2028 if (TREE_CODE (op0
) != SSA_NAME
)
2032 if (VN_INFO (op0
)->has_constants
)
2033 op0
= valueize_expr (vn_get_expr_for (op0
));
2034 else if (gimple_assign_cast_p (stmt
)
2035 || gimple_assign_rhs_code (stmt
) == REALPART_EXPR
2036 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
2037 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
)
2039 /* We want to do tree-combining on conversion-like expressions.
2040 Make sure we feed only SSA_NAMEs or constants to fold though. */
2041 tree tem
= valueize_expr (vn_get_expr_for (op0
));
2042 if (UNARY_CLASS_P (tem
)
2043 || BINARY_CLASS_P (tem
)
2044 || TREE_CODE (tem
) == VIEW_CONVERT_EXPR
2045 || TREE_CODE (tem
) == SSA_NAME
2046 || is_gimple_min_invariant (tem
))
2050 /* Avoid folding if nothing changed, but remember the expression. */
2051 if (op0
== orig_op0
)
2054 result
= fold_unary (gimple_assign_rhs_code (stmt
),
2055 gimple_expr_type (stmt
), op0
);
2058 STRIP_USELESS_TYPE_CONVERSION (result
);
2059 if (valid_gimple_rhs_p (result
))
2066 /* Try to simplify RHS using equivalences and constant folding. */
2069 try_to_simplify (gimple stmt
)
2073 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2074 in this case, there is no point in doing extra work. */
2075 if (gimple_assign_copy_p (stmt
)
2076 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2079 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)))
2081 case tcc_declaration
:
2082 tem
= get_symbol_constant_value (gimple_assign_rhs1 (stmt
));
2088 /* Do not do full-blown reference lookup here, but simplify
2089 reads from constant aggregates. */
2090 tem
= fold_const_aggregate_ref (gimple_assign_rhs1 (stmt
));
2094 /* Fallthrough for some codes that can operate on registers. */
2095 if (!(TREE_CODE (gimple_assign_rhs1 (stmt
)) == REALPART_EXPR
2096 || TREE_CODE (gimple_assign_rhs1 (stmt
)) == IMAGPART_EXPR
2097 || TREE_CODE (gimple_assign_rhs1 (stmt
)) == VIEW_CONVERT_EXPR
))
2099 /* We could do a little more with unary ops, if they expand
2100 into binary ops, but it's debatable whether it is worth it. */
2102 return simplify_unary_expression (stmt
);
2104 case tcc_comparison
:
2106 return simplify_binary_expression (stmt
);
2115 /* Visit and value number USE, return true if the value number
2119 visit_use (tree use
)
2121 bool changed
= false;
2122 gimple stmt
= SSA_NAME_DEF_STMT (use
);
2124 VN_INFO (use
)->use_processed
= true;
2126 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
2127 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
2128 && !SSA_NAME_IS_DEFAULT_DEF (use
))
2130 fprintf (dump_file
, "Value numbering ");
2131 print_generic_expr (dump_file
, use
, 0);
2132 fprintf (dump_file
, " stmt = ");
2133 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2136 /* Handle uninitialized uses. */
2137 if (SSA_NAME_IS_DEFAULT_DEF (use
))
2138 changed
= set_ssa_val_to (use
, use
);
2141 if (gimple_code (stmt
) == GIMPLE_PHI
)
2142 changed
= visit_phi (stmt
);
2143 else if (!gimple_has_lhs (stmt
)
2144 || gimple_has_volatile_ops (stmt
)
2145 || stmt_could_throw_p (stmt
))
2146 changed
= defs_to_varying (stmt
);
2147 else if (is_gimple_assign (stmt
))
2149 tree lhs
= gimple_assign_lhs (stmt
);
2152 /* Shortcut for copies. Simplifying copies is pointless,
2153 since we copy the expression and value they represent. */
2154 if (gimple_assign_copy_p (stmt
)
2155 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
2156 && TREE_CODE (lhs
) == SSA_NAME
)
2158 changed
= visit_copy (lhs
, gimple_assign_rhs1 (stmt
));
2161 simplified
= try_to_simplify (stmt
);
2164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2166 fprintf (dump_file
, "RHS ");
2167 print_gimple_expr (dump_file
, stmt
, 0, 0);
2168 fprintf (dump_file
, " simplified to ");
2169 print_generic_expr (dump_file
, simplified
, 0);
2170 if (TREE_CODE (lhs
) == SSA_NAME
)
2171 fprintf (dump_file
, " has constants %d\n",
2172 expr_has_constants (simplified
));
2174 fprintf (dump_file
, "\n");
2177 /* Setting value numbers to constants will occasionally
2178 screw up phi congruence because constants are not
2179 uniquely associated with a single ssa name that can be
2182 && is_gimple_min_invariant (simplified
)
2183 && TREE_CODE (lhs
) == SSA_NAME
)
2185 VN_INFO (lhs
)->expr
= simplified
;
2186 VN_INFO (lhs
)->has_constants
= true;
2187 changed
= set_ssa_val_to (lhs
, simplified
);
2191 && TREE_CODE (simplified
) == SSA_NAME
2192 && TREE_CODE (lhs
) == SSA_NAME
)
2194 changed
= visit_copy (lhs
, simplified
);
2197 else if (simplified
)
2199 if (TREE_CODE (lhs
) == SSA_NAME
)
2201 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
2202 /* We have to unshare the expression or else
2203 valuizing may change the IL stream. */
2204 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
2207 else if (stmt_has_constants (stmt
)
2208 && TREE_CODE (lhs
) == SSA_NAME
)
2209 VN_INFO (lhs
)->has_constants
= true;
2210 else if (TREE_CODE (lhs
) == SSA_NAME
)
2212 /* We reset expr and constantness here because we may
2213 have been value numbering optimistically, and
2214 iterating. They may become non-constant in this case,
2215 even if they were optimistically constant. */
2217 VN_INFO (lhs
)->has_constants
= false;
2218 VN_INFO (lhs
)->expr
= NULL_TREE
;
2221 if (TREE_CODE (lhs
) == SSA_NAME
2222 /* We can substitute SSA_NAMEs that are live over
2223 abnormal edges with their constant value. */
2224 && !(gimple_assign_copy_p (stmt
)
2225 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
2227 && is_gimple_min_invariant (simplified
))
2228 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2229 changed
= defs_to_varying (stmt
);
2230 else if (REFERENCE_CLASS_P (lhs
) || DECL_P (lhs
))
2232 changed
= visit_reference_op_store (lhs
, gimple_assign_rhs1 (stmt
), stmt
);
2234 else if (TREE_CODE (lhs
) == SSA_NAME
)
2236 if ((gimple_assign_copy_p (stmt
)
2237 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
2239 && is_gimple_min_invariant (simplified
)))
2241 VN_INFO (lhs
)->has_constants
= true;
2243 changed
= set_ssa_val_to (lhs
, simplified
);
2245 changed
= set_ssa_val_to (lhs
, gimple_assign_rhs1 (stmt
));
2249 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2251 case GIMPLE_UNARY_RHS
:
2252 changed
= visit_unary_op (lhs
, stmt
);
2254 case GIMPLE_BINARY_RHS
:
2255 changed
= visit_binary_op (lhs
, stmt
);
2257 case GIMPLE_SINGLE_RHS
:
2258 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)))
2260 case tcc_declaration
:
2262 changed
= visit_reference_op_load
2263 (lhs
, gimple_assign_rhs1 (stmt
), stmt
);
2265 case tcc_expression
:
2266 if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
2268 changed
= visit_unary_op (lhs
, stmt
);
2273 changed
= defs_to_varying (stmt
);
2277 changed
= defs_to_varying (stmt
);
2283 changed
= defs_to_varying (stmt
);
2285 else if (is_gimple_call (stmt
))
2287 tree lhs
= gimple_call_lhs (stmt
);
2289 /* ??? We could try to simplify calls. */
2291 if (stmt_has_constants (stmt
)
2292 && TREE_CODE (lhs
) == SSA_NAME
)
2293 VN_INFO (lhs
)->has_constants
= true;
2294 else if (TREE_CODE (lhs
) == SSA_NAME
)
2296 /* We reset expr and constantness here because we may
2297 have been value numbering optimistically, and
2298 iterating. They may become non-constant in this case,
2299 even if they were optimistically constant. */
2300 VN_INFO (lhs
)->has_constants
= false;
2301 VN_INFO (lhs
)->expr
= NULL_TREE
;
2304 if (TREE_CODE (lhs
) == SSA_NAME
2305 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2306 changed
= defs_to_varying (stmt
);
2307 /* ??? We should handle stores from calls. */
2308 else if (TREE_CODE (lhs
) == SSA_NAME
)
2310 if (gimple_call_flags (stmt
) & (ECF_PURE
| ECF_CONST
))
2311 changed
= visit_reference_op_call (lhs
, stmt
);
2313 changed
= defs_to_varying (stmt
);
2316 changed
= defs_to_varying (stmt
);
2323 /* Compare two operands by reverse postorder index */
2326 compare_ops (const void *pa
, const void *pb
)
2328 const tree opa
= *((const tree
*)pa
);
2329 const tree opb
= *((const tree
*)pb
);
2330 gimple opstmta
= SSA_NAME_DEF_STMT (opa
);
2331 gimple opstmtb
= SSA_NAME_DEF_STMT (opb
);
2335 if (gimple_nop_p (opstmta
) && gimple_nop_p (opstmtb
))
2337 else if (gimple_nop_p (opstmta
))
2339 else if (gimple_nop_p (opstmtb
))
2342 bba
= gimple_bb (opstmta
);
2343 bbb
= gimple_bb (opstmtb
);
2354 if (gimple_code (opstmta
) == GIMPLE_PHI
2355 && gimple_code (opstmtb
) == GIMPLE_PHI
)
2357 else if (gimple_code (opstmta
) == GIMPLE_PHI
)
2359 else if (gimple_code (opstmtb
) == GIMPLE_PHI
)
2361 return gimple_uid (opstmta
) - gimple_uid (opstmtb
);
2363 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
2366 /* Sort an array containing members of a strongly connected component
2367 SCC so that the members are ordered by RPO number.
2368 This means that when the sort is complete, iterating through the
2369 array will give you the members in RPO order. */
2372 sort_scc (VEC (tree
, heap
) *scc
)
2374 qsort (VEC_address (tree
, scc
),
2375 VEC_length (tree
, scc
),
2380 /* Process a strongly connected component in the SSA graph. */
2383 process_scc (VEC (tree
, heap
) *scc
)
2385 /* If the SCC has a single member, just visit it. */
2387 if (VEC_length (tree
, scc
) == 1)
2389 tree use
= VEC_index (tree
, scc
, 0);
2390 if (!VN_INFO (use
)->use_processed
)
2397 unsigned int iterations
= 0;
2398 bool changed
= true;
2400 /* Iterate over the SCC with the optimistic table until it stops
2402 current_info
= optimistic_info
;
2407 /* As we are value-numbering optimistically we have to
2408 clear the expression tables and the simplified expressions
2409 in each iteration until we converge. */
2410 htab_empty (optimistic_info
->nary
);
2411 htab_empty (optimistic_info
->phis
);
2412 htab_empty (optimistic_info
->references
);
2413 obstack_free (&optimistic_info
->nary_obstack
, NULL
);
2414 gcc_obstack_init (&optimistic_info
->nary_obstack
);
2415 empty_alloc_pool (optimistic_info
->phis_pool
);
2416 empty_alloc_pool (optimistic_info
->references_pool
);
2417 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
2418 VN_INFO (var
)->expr
= NULL_TREE
;
2419 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
2420 changed
|= visit_use (var
);
2423 statistics_histogram_event (cfun
, "SCC iterations", iterations
);
2425 /* Finally, visit the SCC once using the valid table. */
2426 current_info
= valid_info
;
2427 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
2432 DEF_VEC_O(ssa_op_iter
);
2433 DEF_VEC_ALLOC_O(ssa_op_iter
,heap
);
2435 /* Pop the components of the found SCC for NAME off the SCC stack
2436 and process them. Returns true if all went well, false if
2437 we run into resource limits. */
2440 extract_and_process_scc_for_name (tree name
)
2442 VEC (tree
, heap
) *scc
= NULL
;
2445 /* Found an SCC, pop the components off the SCC stack and
2449 x
= VEC_pop (tree
, sccstack
);
2451 VN_INFO (x
)->on_sccstack
= false;
2452 VEC_safe_push (tree
, heap
, scc
, x
);
2453 } while (x
!= name
);
2455 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2456 if (VEC_length (tree
, scc
)
2457 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
))
2460 fprintf (dump_file
, "WARNING: Giving up with SCCVN due to "
2461 "SCC size %u exceeding %u\n", VEC_length (tree
, scc
),
2462 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE
));
2466 if (VEC_length (tree
, scc
) > 1)
2469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2470 print_scc (dump_file
, scc
);
2474 VEC_free (tree
, heap
, scc
);
2479 /* Depth first search on NAME to discover and process SCC's in the SSA
2481 Execution of this algorithm relies on the fact that the SCC's are
2482 popped off the stack in topological order.
2483 Returns true if successful, false if we stopped processing SCC's due
2484 to resource constraints. */
2489 VEC(ssa_op_iter
, heap
) *itervec
= NULL
;
2490 VEC(tree
, heap
) *namevec
= NULL
;
2491 use_operand_p usep
= NULL
;
2498 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
2499 VN_INFO (name
)->visited
= true;
2500 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
2502 VEC_safe_push (tree
, heap
, sccstack
, name
);
2503 VN_INFO (name
)->on_sccstack
= true;
2504 defstmt
= SSA_NAME_DEF_STMT (name
);
2506 /* Recursively DFS on our operands, looking for SCC's. */
2507 if (!gimple_nop_p (defstmt
))
2509 /* Push a new iterator. */
2510 if (gimple_code (defstmt
) == GIMPLE_PHI
)
2511 usep
= op_iter_init_phiuse (&iter
, defstmt
, SSA_OP_ALL_USES
);
2513 usep
= op_iter_init_use (&iter
, defstmt
, SSA_OP_ALL_USES
);
2520 /* If we are done processing uses of a name, go up the stack
2521 of iterators and process SCCs as we found them. */
2522 if (op_iter_done (&iter
))
2524 /* See if we found an SCC. */
2525 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
2526 if (!extract_and_process_scc_for_name (name
))
2528 VEC_free (tree
, heap
, namevec
);
2529 VEC_free (ssa_op_iter
, heap
, itervec
);
2533 /* Check if we are done. */
2534 if (VEC_empty (tree
, namevec
))
2536 VEC_free (tree
, heap
, namevec
);
2537 VEC_free (ssa_op_iter
, heap
, itervec
);
2541 /* Restore the last use walker and continue walking there. */
2543 name
= VEC_pop (tree
, namevec
);
2544 memcpy (&iter
, VEC_last (ssa_op_iter
, itervec
),
2545 sizeof (ssa_op_iter
));
2546 VEC_pop (ssa_op_iter
, itervec
);
2547 goto continue_walking
;
2550 use
= USE_FROM_PTR (usep
);
2552 /* Since we handle phi nodes, we will sometimes get
2553 invariants in the use expression. */
2554 if (TREE_CODE (use
) == SSA_NAME
)
2556 if (! (VN_INFO (use
)->visited
))
2558 /* Recurse by pushing the current use walking state on
2559 the stack and starting over. */
2560 VEC_safe_push(ssa_op_iter
, heap
, itervec
, &iter
);
2561 VEC_safe_push(tree
, heap
, namevec
, name
);
2566 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
2567 VN_INFO (use
)->low
);
2569 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
2570 && VN_INFO (use
)->on_sccstack
)
2572 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
2573 VN_INFO (name
)->low
);
2577 usep
= op_iter_next_use (&iter
);
2581 /* Allocate a value number table. */
2584 allocate_vn_table (vn_tables_t table
)
2586 table
->phis
= htab_create (23, vn_phi_hash
, vn_phi_eq
, free_phi
);
2587 table
->nary
= htab_create (23, vn_nary_op_hash
, vn_nary_op_eq
, NULL
);
2588 table
->references
= htab_create (23, vn_reference_hash
, vn_reference_eq
,
2591 gcc_obstack_init (&table
->nary_obstack
);
2592 table
->phis_pool
= create_alloc_pool ("VN phis",
2593 sizeof (struct vn_phi_s
),
2595 table
->references_pool
= create_alloc_pool ("VN references",
2596 sizeof (struct vn_reference_s
),
2600 /* Free a value number table. */
2603 free_vn_table (vn_tables_t table
)
2605 htab_delete (table
->phis
);
2606 htab_delete (table
->nary
);
2607 htab_delete (table
->references
);
2608 obstack_free (&table
->nary_obstack
, NULL
);
2609 free_alloc_pool (table
->phis_pool
);
2610 free_alloc_pool (table
->references_pool
);
2618 int *rpo_numbers_temp
;
2620 calculate_dominance_info (CDI_DOMINATORS
);
2622 constant_to_value_id
= htab_create (23, vn_constant_hash
, vn_constant_eq
,
2625 constant_value_ids
= BITMAP_ALLOC (NULL
);
2630 vn_ssa_aux_table
= VEC_alloc (vn_ssa_aux_t
, heap
, num_ssa_names
+ 1);
2631 /* VEC_alloc doesn't actually grow it to the right size, it just
2632 preallocates the space to do so. */
2633 VEC_safe_grow_cleared (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
, num_ssa_names
+ 1);
2634 gcc_obstack_init (&vn_ssa_aux_obstack
);
2636 shared_lookup_phiargs
= NULL
;
2637 shared_lookup_vops
= NULL
;
2638 shared_lookup_references
= NULL
;
2639 rpo_numbers
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
2640 rpo_numbers_temp
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
2641 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
2643 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
2644 the i'th block in RPO order is bb. We want to map bb's to RPO
2645 numbers, so we need to rearrange this array. */
2646 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
2647 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
2649 XDELETE (rpo_numbers_temp
);
2651 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
2653 /* Create the VN_INFO structures, and initialize value numbers to
2655 for (i
= 0; i
< num_ssa_names
; i
++)
2657 tree name
= ssa_name (i
);
2660 VN_INFO_GET (name
)->valnum
= VN_TOP
;
2661 VN_INFO (name
)->expr
= NULL_TREE
;
2662 VN_INFO (name
)->value_id
= 0;
2666 renumber_gimple_stmt_uids ();
2668 /* Create the valid and optimistic value numbering tables. */
2669 valid_info
= XCNEW (struct vn_tables_s
);
2670 allocate_vn_table (valid_info
);
2671 optimistic_info
= XCNEW (struct vn_tables_s
);
2672 allocate_vn_table (optimistic_info
);
2680 htab_delete (constant_to_value_id
);
2681 BITMAP_FREE (constant_value_ids
);
2682 VEC_free (tree
, heap
, shared_lookup_phiargs
);
2683 VEC_free (tree
, gc
, shared_lookup_vops
);
2684 VEC_free (vn_reference_op_s
, heap
, shared_lookup_references
);
2685 XDELETEVEC (rpo_numbers
);
2687 for (i
= 0; i
< num_ssa_names
; i
++)
2689 tree name
= ssa_name (i
);
2691 && VN_INFO (name
)->needs_insertion
)
2692 release_ssa_name (name
);
2694 obstack_free (&vn_ssa_aux_obstack
, NULL
);
2695 VEC_free (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
);
2697 VEC_free (tree
, heap
, sccstack
);
2698 free_vn_table (valid_info
);
2699 XDELETE (valid_info
);
2700 free_vn_table (optimistic_info
);
2701 XDELETE (optimistic_info
);
2704 /* Set the value ids in the valid hash tables. */
2707 set_hashtable_value_ids (void)
2714 /* Now set the value ids of the things we had put in the hash
2717 FOR_EACH_HTAB_ELEMENT (valid_info
->nary
,
2718 vno
, vn_nary_op_t
, hi
)
2722 if (TREE_CODE (vno
->result
) == SSA_NAME
)
2723 vno
->value_id
= VN_INFO (vno
->result
)->value_id
;
2724 else if (is_gimple_min_invariant (vno
->result
))
2725 vno
->value_id
= get_or_alloc_constant_value_id (vno
->result
);
2729 FOR_EACH_HTAB_ELEMENT (valid_info
->phis
,
2734 if (TREE_CODE (vp
->result
) == SSA_NAME
)
2735 vp
->value_id
= VN_INFO (vp
->result
)->value_id
;
2736 else if (is_gimple_min_invariant (vp
->result
))
2737 vp
->value_id
= get_or_alloc_constant_value_id (vp
->result
);
2741 FOR_EACH_HTAB_ELEMENT (valid_info
->references
,
2742 vr
, vn_reference_t
, hi
)
2746 if (TREE_CODE (vr
->result
) == SSA_NAME
)
2747 vr
->value_id
= VN_INFO (vr
->result
)->value_id
;
2748 else if (is_gimple_min_invariant (vr
->result
))
2749 vr
->value_id
= get_or_alloc_constant_value_id (vr
->result
);
2754 /* Do SCCVN. Returns true if it finished, false if we bailed out
2755 due to resource constraints. */
2758 run_scc_vn (bool may_insert_arg
)
2762 bool changed
= true;
2764 may_insert
= may_insert_arg
;
2767 current_info
= valid_info
;
2769 for (param
= DECL_ARGUMENTS (current_function_decl
);
2771 param
= TREE_CHAIN (param
))
2773 if (gimple_default_def (cfun
, param
) != NULL
)
2775 tree def
= gimple_default_def (cfun
, param
);
2776 SSA_VAL (def
) = def
;
2780 for (i
= 1; i
< num_ssa_names
; ++i
)
2782 tree name
= ssa_name (i
);
2784 && VN_INFO (name
)->visited
== false
2785 && !has_zero_uses (name
))
2794 /* Initialize the value ids. */
2796 for (i
= 1; i
< num_ssa_names
; ++i
)
2798 tree name
= ssa_name (i
);
2802 info
= VN_INFO (name
);
2803 if (info
->valnum
== name
)
2804 info
->value_id
= get_next_value_id ();
2805 else if (is_gimple_min_invariant (info
->valnum
))
2806 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
2809 /* Propagate until they stop changing. */
2813 for (i
= 1; i
< num_ssa_names
; ++i
)
2815 tree name
= ssa_name (i
);
2819 info
= VN_INFO (name
);
2820 if (TREE_CODE (info
->valnum
) == SSA_NAME
2821 && info
->valnum
!= name
2822 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
2825 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
2830 set_hashtable_value_ids ();
2832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2834 fprintf (dump_file
, "Value numbers:\n");
2835 for (i
= 0; i
< num_ssa_names
; i
++)
2837 tree name
= ssa_name (i
);
2839 && VN_INFO (name
)->visited
2840 && SSA_VAL (name
) != name
)
2842 print_generic_expr (dump_file
, name
, 0);
2843 fprintf (dump_file
, " = ");
2844 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
2845 fprintf (dump_file
, "\n");
2854 /* Return the maximum value id we have ever seen. */
2857 get_max_value_id (void)
2859 return next_value_id
;
2862 /* Return the next unique value id. */
2865 get_next_value_id (void)
2867 return next_value_id
++;
2871 /* Compare two expressions E1 and E2 and return true if they are equal. */
2874 expressions_equal_p (tree e1
, tree e2
)
2876 /* The obvious case. */
2880 /* If only one of them is null, they cannot be equal. */
2884 /* Recurse on elements of lists. */
2885 if (TREE_CODE (e1
) == TREE_LIST
&& TREE_CODE (e2
) == TREE_LIST
)
2889 for (lop1
= e1
, lop2
= e2
;
2891 lop1
= TREE_CHAIN (lop1
), lop2
= TREE_CHAIN (lop2
))
2895 if (!expressions_equal_p (TREE_VALUE (lop1
), TREE_VALUE (lop2
)))
2901 /* Now perform the actual comparison. */
2902 if (TREE_CODE (e1
) == TREE_CODE (e2
)
2903 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
2909 /* Sort the VUSE array so that we can do equality comparisons
2910 quicker on two vuse vecs. */
2913 sort_vuses (VEC (tree
,gc
) *vuses
)
2915 if (VEC_length (tree
, vuses
) > 1)
2916 qsort (VEC_address (tree
, vuses
),
2917 VEC_length (tree
, vuses
),
2922 /* Sort the VUSE array so that we can do equality comparisons
2923 quicker on two vuse vecs. */
2926 sort_vuses_heap (VEC (tree
,heap
) *vuses
)
2928 if (VEC_length (tree
, vuses
) > 1)
2929 qsort (VEC_address (tree
, vuses
),
2930 VEC_length (tree
, vuses
),