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);
650 if (is_gimple_min_invariant (ref))
656 /* These are only interesting for their operands, their
657 existence, and their type. They will never be the last
658 ref in the chain of references (IE they require an
659 operand), so we don't have to put anything
660 for op* as it will be handled by the iteration */
663 case VIEW_CONVERT_EXPR:
668 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
670 if (REFERENCE_CLASS_P (ref)
671 || (TREE_CODE (ref) == ADDR_EXPR
672 && !is_gimple_min_invariant (ref)))
673 ref = TREE_OPERAND (ref, 0);
679 /* Copy the operations present in load/store/call REF into RESULT, a vector of
680 vn_reference_op_s's. */
683 copy_reference_ops_from_call (gimple call,
684 VEC(vn_reference_op_s, heap) **result)
686 vn_reference_op_s temp;
689 /* Copy the call_expr opcode, type, function being called, and
691 memset (&temp, 0, sizeof (temp));
692 temp.type = gimple_call_return_type (call);
693 temp.opcode = CALL_EXPR;
694 temp.op0 = gimple_call_fn (call);
695 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
697 /* Copy the call arguments. As they can be references as well,
698 just chain them together. */
699 for (i = 0; i < gimple_call_num_args (call); ++i)
701 tree callarg = gimple_call_arg (call, i);
702 copy_reference_ops_from_ref (callarg, result);
707 /* Create a vector of vn_reference_op_s structures from REF, a
708 REFERENCE_CLASS_P tree. The vector is not shared. */
710 static VEC(vn_reference_op_s, heap) *
711 create_reference_ops_from_ref (tree ref)
713 VEC (vn_reference_op_s, heap) *result = NULL;
715 copy_reference_ops_from_ref (ref, &result);
719 /* Create a vector of vn_reference_op_s structures from CALL, a
720 call statement. The vector is not shared. */
722 static VEC(vn_reference_op_s, heap) *
723 create_reference_ops_from_call (gimple call)
725 VEC (vn_reference_op_s, heap) *result = NULL;
727 copy_reference_ops_from_call (call, &result);
731 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
733 /* Create a vector of vn_reference_op_s structures from REF, a
734 REFERENCE_CLASS_P tree. The vector is shared among all callers of
737 static VEC(vn_reference_op_s, heap) *
738 shared_reference_ops_from_ref (tree ref)
742 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
743 copy_reference_ops_from_ref (ref, &shared_lookup_references);
744 return shared_lookup_references;
747 /* Create a vector of vn_reference_op_s structures from CALL, a
748 call statement. The vector is shared among all callers of
751 static VEC(vn_reference_op_s, heap) *
752 shared_reference_ops_from_call (gimple call)
756 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
757 copy_reference_ops_from_call (call, &shared_lookup_references);
758 return shared_lookup_references;
762 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
763 structures into their value numbers. This is done in-place, and
764 the vector passed in is returned. */
766 static VEC (vn_reference_op_s, heap) *
767 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
769 vn_reference_op_t vro;
772 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
774 if (vro->opcode == SSA_NAME
775 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
777 vro->op0 = SSA_VAL (vro->op0);
778 /* If it transforms from an SSA_NAME to a constant, update
780 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
781 vro->opcode = TREE_CODE (vro->op0);
783 /* TODO: Do we want to valueize op2 and op1 of
784 ARRAY_REF/COMPONENT_REF for Ada */
791 /* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
792 their value numbers. This is done in-place, and the vector passed
795 static VEC (tree, gc) *
796 valueize_vuses (VEC (tree, gc) *orig)
798 bool made_replacement = false;
802 for (i = 0; VEC_iterate (tree, orig, i, vuse); i++)
804 if (vuse != SSA_VAL (vuse))
806 made_replacement = true;
807 VEC_replace (tree, orig, i, SSA_VAL (vuse));
811 if (made_replacement && VEC_length (tree, orig) > 1)
817 /* Return the single reference statement defining all virtual uses
818 in VUSES or NULL_TREE, if there are multiple defining statements.
819 Take into account only definitions that alias REF if following
823 get_def_ref_stmt_vuses (tree ref, VEC (tree, gc) *vuses)
829 gcc_assert (VEC_length (tree, vuses) >= 1);
831 def_stmt = SSA_NAME_DEF_STMT (VEC_index (tree, vuses, 0));
832 if (gimple_code (def_stmt) == GIMPLE_PHI)
834 /* We can only handle lookups over PHI nodes for a single
836 if (VEC_length (tree, vuses) == 1)
838 def_stmt = get_single_def_stmt_from_phi (ref, def_stmt);
845 /* Verify each VUSE reaches the same defining stmt. */
846 for (i = 1; VEC_iterate (tree, vuses, i, vuse); ++i)
848 gimple tmp = SSA_NAME_DEF_STMT (vuse);
853 /* Now see if the definition aliases ref, and loop until it does. */
856 && is_gimple_assign (def_stmt)
857 && !refs_may_alias_p (ref, gimple_get_lhs (def_stmt)))
858 def_stmt = get_single_def_stmt_with_phi (ref, def_stmt);
863 /* Lookup a SCCVN reference operation VR in the current hash table.
864 Returns the resulting value number if it exists in the hash table,
865 NULL_TREE otherwise. VNRESULT will be filled in with the actual
866 vn_reference_t stored in the hashtable if something is found. */
869 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
875 slot = htab_find_slot_with_hash (current_info->references, vr,
877 if (!slot && current_info == optimistic_info)
878 slot = htab_find_slot_with_hash (valid_info->references, vr,
883 *vnresult = (vn_reference_t)*slot;
884 return ((vn_reference_t)*slot)->result;
891 /* Lookup a reference operation by it's parts, in the current hash table.
892 Returns the resulting value number if it exists in the hash table,
893 NULL_TREE otherwise. VNRESULT will be filled in with the actual
894 vn_reference_t stored in the hashtable if something is found. */
897 vn_reference_lookup_pieces (VEC (tree, gc) *vuses,
898 VEC (vn_reference_op_s, heap) *operands,
899 vn_reference_t *vnresult)
901 struct vn_reference_s vr1;
906 vr1.vuses = valueize_vuses (vuses);
907 vr1.operands = valueize_refs (operands);
908 vr1.hashcode = vn_reference_compute_hash (&vr1);
909 result = vn_reference_lookup_1 (&vr1, vnresult);
914 /* Lookup OP in the current hash table, and return the resulting value
915 number if it exists in the hash table. Return NULL_TREE if it does
916 not exist in the hash table or if the result field of the structure
917 was NULL.. VNRESULT will be filled in with the vn_reference_t
918 stored in the hashtable if one exists. */
921 vn_reference_lookup (tree op, VEC (tree, gc) *vuses, bool maywalk,
922 vn_reference_t *vnresult)
924 struct vn_reference_s vr1;
930 vr1.vuses = valueize_vuses (vuses);
931 vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
932 vr1.hashcode = vn_reference_compute_hash (&vr1);
933 result = vn_reference_lookup_1 (&vr1, vnresult);
935 /* If there is a single defining statement for all virtual uses, we can
936 use that, following virtual use-def chains. */
940 && VEC_length (tree, vr1.vuses) >= 1
941 && (def_stmt = get_def_ref_stmt_vuses (op, vr1.vuses))
942 && is_gimple_assign (def_stmt))
944 /* We are now at an aliasing definition for the vuses we want to
945 look up. Re-do the lookup with the vdefs for this stmt. */
946 vdefs_to_vec (def_stmt, &vuses);
947 vr1.vuses = valueize_vuses (vuses);
948 vr1.hashcode = vn_reference_compute_hash (&vr1);
949 result = vn_reference_lookup_1 (&vr1, vnresult);
956 /* Insert OP into the current hash table with a value number of
957 RESULT, and return the resulting reference structure we created. */
960 vn_reference_insert (tree op, tree result, VEC (tree, gc) *vuses)
965 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
966 if (TREE_CODE (result) == SSA_NAME)
967 vr1->value_id = VN_INFO (result)->value_id;
969 vr1->value_id = get_or_alloc_constant_value_id (result);
970 vr1->vuses = valueize_vuses (vuses);
971 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
972 vr1->hashcode = vn_reference_compute_hash (vr1);
973 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
975 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
978 /* Because we lookup stores using vuses, and value number failures
979 using the vdefs (see visit_reference_op_store for how and why),
980 it's possible that on failure we may try to insert an already
981 inserted store. This is not wrong, there is no ssa name for a
982 store that we could use as a differentiator anyway. Thus, unlike
983 the other lookup functions, you cannot gcc_assert (!*slot)
986 /* But free the old slot in case of a collision. */
988 free_reference (*slot);
994 /* Insert a reference by it's pieces into the current hash table with
995 a value number of RESULT. Return the resulting reference
996 structure we created. */
999 vn_reference_insert_pieces (VEC (tree, gc) *vuses,
1000 VEC (vn_reference_op_s, heap) *operands,
1001 tree result, unsigned int value_id)
1007 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1008 vr1->value_id = value_id;
1009 vr1->vuses = valueize_vuses (vuses);
1010 vr1->operands = valueize_refs (operands);
1011 vr1->hashcode = vn_reference_compute_hash (vr1);
1012 if (result && TREE_CODE (result) == SSA_NAME)
1013 result = SSA_VAL (result);
1014 vr1->result = result;
1016 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1019 /* At this point we should have all the things inserted that we have
1020 seen before, and we should never try inserting something that
1022 gcc_assert (!*slot);
1024 free_reference (*slot);
1030 /* Compute and return the hash value for nary operation VBO1. */
1033 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1038 for (i = 0; i < vno1->length; ++i)
1039 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1040 vno1->op[i] = SSA_VAL (vno1->op[i]);
1042 if (vno1->length == 2
1043 && commutative_tree_code (vno1->opcode)
1044 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1046 tree temp = vno1->op[0];
1047 vno1->op[0] = vno1->op[1];
1051 for (i = 0; i < vno1->length; ++i)
1052 hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
1057 /* Return the computed hashcode for nary operation P1. */
1060 vn_nary_op_hash (const void *p1)
1062 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1063 return vno1->hashcode;
1066 /* Compare nary operations P1 and P2 and return true if they are
1070 vn_nary_op_eq (const void *p1, const void *p2)
1072 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1073 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1076 if (vno1->opcode != vno2->opcode
1077 || vno1->type != vno2->type)
1080 for (i = 0; i < vno1->length; ++i)
1081 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1087 /* Lookup a n-ary operation by its pieces and return the resulting value
1088 number if it exists in the hash table. Return NULL_TREE if it does
1089 not exist in the hash table or if the result field of the operation
1090 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1094 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
1095 tree type, tree op0, tree op1, tree op2,
1096 tree op3, vn_nary_op_t *vnresult)
1099 struct vn_nary_op_s vno1;
1103 vno1.length = length;
1109 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1110 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1112 if (!slot && current_info == optimistic_info)
1113 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1118 *vnresult = (vn_nary_op_t)*slot;
1119 return ((vn_nary_op_t)*slot)->result;
1122 /* Lookup OP in the current hash table, and return the resulting value
1123 number if it exists in the hash table. Return NULL_TREE if it does
1124 not exist in the hash table or if the result field of the operation
1125 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1129 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
1132 struct vn_nary_op_s vno1;
1137 vno1.opcode = TREE_CODE (op);
1138 vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
1139 vno1.type = TREE_TYPE (op);
1140 for (i = 0; i < vno1.length; ++i)
1141 vno1.op[i] = TREE_OPERAND (op, i);
1142 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1143 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1145 if (!slot && current_info == optimistic_info)
1146 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1151 *vnresult = (vn_nary_op_t)*slot;
1152 return ((vn_nary_op_t)*slot)->result;
1155 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1156 value number if it exists in the hash table. Return NULL_TREE if
1157 it does not exist in the hash table. VNRESULT will contain the
1158 vn_nary_op_t from the hashtable if it exists. */
1161 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
1164 struct vn_nary_op_s vno1;
1169 vno1.opcode = gimple_assign_rhs_code (stmt);
1170 vno1.length = gimple_num_ops (stmt) - 1;
1171 vno1.type = TREE_TYPE (gimple_assign_lhs (stmt));
1172 for (i = 0; i < vno1.length; ++i)
1173 vno1.op[i] = gimple_op (stmt, i + 1);
1174 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1175 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1177 if (!slot && current_info == optimistic_info)
1178 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1183 *vnresult = (vn_nary_op_t)*slot;
1184 return ((vn_nary_op_t)*slot)->result;
1187 /* Insert a n-ary operation into the current hash table using it's
1188 pieces. Return the vn_nary_op_t structure we created and put in
1192 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
1193 tree type, tree op0,
1194 tree op1, tree op2, tree op3,
1196 unsigned int value_id)
1201 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1202 (sizeof (struct vn_nary_op_s)
1203 - sizeof (tree) * (4 - length)));
1204 vno1->value_id = value_id;
1205 vno1->opcode = code;
1206 vno1->length = length;
1216 vno1->result = result;
1217 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1218 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1220 gcc_assert (!*slot);
1227 /* Insert OP into the current hash table with a value number of
1228 RESULT. Return the vn_nary_op_t structure we created and put in
1232 vn_nary_op_insert (tree op, tree result)
1234 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
1239 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1240 (sizeof (struct vn_nary_op_s)
1241 - sizeof (tree) * (4 - length)));
1242 vno1->value_id = VN_INFO (result)->value_id;
1243 vno1->opcode = TREE_CODE (op);
1244 vno1->length = length;
1245 vno1->type = TREE_TYPE (op);
1246 for (i = 0; i < vno1->length; ++i)
1247 vno1->op[i] = TREE_OPERAND (op, i);
1248 vno1->result = result;
1249 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1250 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1252 gcc_assert (!*slot);
1258 /* Insert the rhs of STMT into the current hash table with a value number of
1262 vn_nary_op_insert_stmt (gimple stmt, tree result)
1264 unsigned length = gimple_num_ops (stmt) - 1;
1269 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1270 (sizeof (struct vn_nary_op_s)
1271 - sizeof (tree) * (4 - length)));
1272 vno1->value_id = VN_INFO (result)->value_id;
1273 vno1->opcode = gimple_assign_rhs_code (stmt);
1274 vno1->length = length;
1275 vno1->type = TREE_TYPE (gimple_assign_lhs (stmt));
1276 for (i = 0; i < vno1->length; ++i)
1277 vno1->op[i] = gimple_op (stmt, i + 1);
1278 vno1->result = result;
1279 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1280 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1282 gcc_assert (!*slot);
1288 /* Compute a hashcode for PHI operation VP1 and return it. */
1290 static inline hashval_t
1291 vn_phi_compute_hash (vn_phi_t vp1)
1293 hashval_t result = 0;
1297 result = vp1->block->index;
1299 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1301 if (phi1op == VN_TOP)
1303 result += iterative_hash_expr (phi1op, result);
1309 /* Return the computed hashcode for phi operation P1. */
1312 vn_phi_hash (const void *p1)
1314 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1315 return vp1->hashcode;
1318 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1321 vn_phi_eq (const void *p1, const void *p2)
1323 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1324 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
1326 if (vp1->block == vp2->block)
1331 /* Any phi in the same block will have it's arguments in the
1332 same edge order, because of how we store phi nodes. */
1333 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1335 tree phi2op = VEC_index (tree, vp2->phiargs, i);
1336 if (phi1op == VN_TOP || phi2op == VN_TOP)
1338 if (!expressions_equal_p (phi1op, phi2op))
1346 static VEC(tree, heap) *shared_lookup_phiargs;
1348 /* Lookup PHI in the current hash table, and return the resulting
1349 value number if it exists in the hash table. Return NULL_TREE if
1350 it does not exist in the hash table. */
1353 vn_phi_lookup (gimple phi)
1356 struct vn_phi_s vp1;
1359 VEC_truncate (tree, shared_lookup_phiargs, 0);
1361 /* Canonicalize the SSA_NAME's to their value number. */
1362 for (i = 0; i < gimple_phi_num_args (phi); i++)
1364 tree def = PHI_ARG_DEF (phi, i);
1365 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1366 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
1368 vp1.phiargs = shared_lookup_phiargs;
1369 vp1.block = gimple_bb (phi);
1370 vp1.hashcode = vn_phi_compute_hash (&vp1);
1371 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
1373 if (!slot && current_info == optimistic_info)
1374 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
1378 return ((vn_phi_t)*slot)->result;
1381 /* Insert PHI into the current hash table with a value number of
1385 vn_phi_insert (gimple phi, tree result)
1388 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
1390 VEC (tree, heap) *args = NULL;
1392 /* Canonicalize the SSA_NAME's to their value number. */
1393 for (i = 0; i < gimple_phi_num_args (phi); i++)
1395 tree def = PHI_ARG_DEF (phi, i);
1396 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1397 VEC_safe_push (tree, heap, args, def);
1399 vp1->value_id = VN_INFO (result)->value_id;
1400 vp1->phiargs = args;
1401 vp1->block = gimple_bb (phi);
1402 vp1->result = result;
1403 vp1->hashcode = vn_phi_compute_hash (vp1);
1405 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
1408 /* Because we iterate over phi operations more than once, it's
1409 possible the slot might already exist here, hence no assert.*/
1415 /* Print set of components in strongly connected component SCC to OUT. */
1418 print_scc (FILE *out, VEC (tree, heap) *scc)
1423 fprintf (out, "SCC consists of: ");
1424 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1426 print_generic_expr (out, var, 0);
1429 fprintf (out, "\n");
1432 /* Set the value number of FROM to TO, return true if it has changed
1436 set_ssa_val_to (tree from, tree to)
1441 && TREE_CODE (to) == SSA_NAME
1442 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
1445 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1446 and invariants. So assert that here. */
1447 gcc_assert (to != NULL_TREE
1449 || TREE_CODE (to) == SSA_NAME
1450 || is_gimple_min_invariant (to)));
1452 if (dump_file && (dump_flags & TDF_DETAILS))
1454 fprintf (dump_file, "Setting value number of ");
1455 print_generic_expr (dump_file, from, 0);
1456 fprintf (dump_file, " to ");
1457 print_generic_expr (dump_file, to, 0);
1458 fprintf (dump_file, "\n");
1461 currval = SSA_VAL (from);
1463 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
1465 SSA_VAL (from) = to;
1471 /* Set all definitions in STMT to value number to themselves.
1472 Return true if a value number changed. */
1475 defs_to_varying (gimple stmt)
1477 bool changed = false;
1481 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1483 tree def = DEF_FROM_PTR (defp);
1485 VN_INFO (def)->use_processed = true;
1486 changed |= set_ssa_val_to (def, def);
1491 static bool expr_has_constants (tree expr);
1492 static tree try_to_simplify (gimple stmt);
1494 /* Visit a copy between LHS and RHS, return true if the value number
1498 visit_copy (tree lhs, tree rhs)
1500 /* Follow chains of copies to their destination. */
1501 while (SSA_VAL (rhs) != rhs && TREE_CODE (SSA_VAL (rhs)) == SSA_NAME)
1502 rhs = SSA_VAL (rhs);
1504 /* The copy may have a more interesting constant filled expression
1505 (we don't, since we know our RHS is just an SSA name). */
1506 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1507 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1509 return set_ssa_val_to (lhs, rhs);
1512 /* Visit a unary operator RHS, value number it, and return true if the
1513 value number of LHS has changed as a result. */
1516 visit_unary_op (tree lhs, gimple stmt)
1518 bool changed = false;
1519 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1523 changed = set_ssa_val_to (lhs, result);
1527 changed = set_ssa_val_to (lhs, lhs);
1528 vn_nary_op_insert_stmt (stmt, lhs);
1534 /* Visit a binary operator RHS, value number it, and return true if the
1535 value number of LHS has changed as a result. */
1538 visit_binary_op (tree lhs, gimple stmt)
1540 bool changed = false;
1541 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1545 changed = set_ssa_val_to (lhs, result);
1549 changed = set_ssa_val_to (lhs, lhs);
1550 vn_nary_op_insert_stmt (stmt, lhs);
1556 /* Visit a call STMT storing into LHS. Return true if the value number
1557 of the LHS has changed as a result. */
1560 visit_reference_op_call (tree lhs, gimple stmt)
1562 bool changed = false;
1563 struct vn_reference_s vr1;
1566 vr1.vuses = valueize_vuses (shared_vuses_from_stmt (stmt));
1567 vr1.operands = valueize_refs (shared_reference_ops_from_call (stmt));
1568 vr1.hashcode = vn_reference_compute_hash (&vr1);
1569 result = vn_reference_lookup_1 (&vr1, NULL);
1572 changed = set_ssa_val_to (lhs, result);
1573 if (TREE_CODE (result) == SSA_NAME
1574 && VN_INFO (result)->has_constants)
1575 VN_INFO (lhs)->has_constants = true;
1581 changed = set_ssa_val_to (lhs, lhs);
1582 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
1583 vr2->vuses = valueize_vuses (copy_vuses_from_stmt (stmt));
1584 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
1585 vr2->hashcode = vr1.hashcode;
1587 slot = htab_find_slot_with_hash (current_info->references,
1588 vr2, vr2->hashcode, INSERT);
1590 free_reference (*slot);
1597 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1598 and return true if the value number of the LHS has changed as a result. */
1601 visit_reference_op_load (tree lhs, tree op, gimple stmt)
1603 bool changed = false;
1604 tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt), true,
1607 /* We handle type-punning through unions by value-numbering based
1608 on offset and size of the access. Be prepared to handle a
1609 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1611 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
1613 /* We will be setting the value number of lhs to the value number
1614 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1615 So first simplify and lookup this expression to see if it
1616 is already available. */
1617 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
1619 && !is_gimple_min_invariant (val)
1620 && TREE_CODE (val) != SSA_NAME)
1622 tree tem = try_to_simplify (stmt);
1627 if (!is_gimple_min_invariant (val)
1628 && TREE_CODE (val) != SSA_NAME)
1629 result = vn_nary_op_lookup (val, NULL);
1630 /* If the expression is not yet available, value-number lhs to
1631 a new SSA_NAME we create. */
1632 if (!result && may_insert)
1634 result = make_ssa_name (SSA_NAME_VAR (lhs), NULL);
1635 /* Initialize value-number information properly. */
1636 VN_INFO_GET (result)->valnum = result;
1637 VN_INFO (result)->value_id = get_next_value_id ();
1638 VN_INFO (result)->expr = val;
1639 VN_INFO (result)->has_constants = expr_has_constants (val);
1640 VN_INFO (result)->needs_insertion = true;
1641 /* As all "inserted" statements are singleton SCCs, insert
1642 to the valid table. This is strictly needed to
1643 avoid re-generating new value SSA_NAMEs for the same
1644 expression during SCC iteration over and over (the
1645 optimistic table gets cleared after each iteration).
1646 We do not need to insert into the optimistic table, as
1647 lookups there will fall back to the valid table. */
1648 if (current_info == optimistic_info)
1650 current_info = valid_info;
1651 vn_nary_op_insert (val, result);
1652 current_info = optimistic_info;
1655 vn_nary_op_insert (val, result);
1656 if (dump_file && (dump_flags & TDF_DETAILS))
1658 fprintf (dump_file, "Inserting name ");
1659 print_generic_expr (dump_file, result, 0);
1660 fprintf (dump_file, " for expression ");
1661 print_generic_expr (dump_file, val, 0);
1662 fprintf (dump_file, "\n");
1669 changed = set_ssa_val_to (lhs, result);
1670 if (TREE_CODE (result) == SSA_NAME
1671 && VN_INFO (result)->has_constants)
1673 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
1674 VN_INFO (lhs)->has_constants = true;
1679 changed = set_ssa_val_to (lhs, lhs);
1680 vn_reference_insert (op, lhs, copy_vuses_from_stmt (stmt));
1687 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1688 and return true if the value number of the LHS has changed as a result. */
1691 visit_reference_op_store (tree lhs, tree op, gimple stmt)
1693 bool changed = false;
1695 bool resultsame = false;
1697 /* First we want to lookup using the *vuses* from the store and see
1698 if there the last store to this location with the same address
1701 The vuses represent the memory state before the store. If the
1702 memory state, address, and value of the store is the same as the
1703 last store to this location, then this store will produce the
1704 same memory state as that store.
1706 In this case the vdef versions for this store are value numbered to those
1707 vuse versions, since they represent the same memory state after
1710 Otherwise, the vdefs for the store are used when inserting into
1711 the table, since the store generates a new memory state. */
1713 result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt), false,
1718 if (TREE_CODE (result) == SSA_NAME)
1719 result = SSA_VAL (result);
1720 if (TREE_CODE (op) == SSA_NAME)
1722 resultsame = expressions_equal_p (result, op);
1725 if (!result || !resultsame)
1727 VEC(tree, gc) *vdefs = copy_vdefs_from_stmt (stmt);
1731 if (dump_file && (dump_flags & TDF_DETAILS))
1733 fprintf (dump_file, "No store match\n");
1734 fprintf (dump_file, "Value numbering store ");
1735 print_generic_expr (dump_file, lhs, 0);
1736 fprintf (dump_file, " to ");
1737 print_generic_expr (dump_file, op, 0);
1738 fprintf (dump_file, "\n");
1740 /* Have to set value numbers before insert, since insert is
1741 going to valueize the references in-place. */
1742 for (i = 0; VEC_iterate (tree, vdefs, i, vdef); i++)
1744 VN_INFO (vdef)->use_processed = true;
1745 changed |= set_ssa_val_to (vdef, vdef);
1748 /* Do not insert structure copies into the tables. */
1749 if (is_gimple_min_invariant (op)
1750 || is_gimple_reg (op))
1751 vn_reference_insert (lhs, op, vdefs);
1755 /* We had a match, so value number the vdefs to have the value
1756 number of the vuses they came from. */
1757 ssa_op_iter op_iter;
1761 if (dump_file && (dump_flags & TDF_DETAILS))
1762 fprintf (dump_file, "Store matched earlier value,"
1763 "value numbering store vdefs to matching vuses.\n");
1765 FOR_EACH_SSA_VDEF_OPERAND (var, vv, stmt, op_iter)
1767 tree def = DEF_FROM_PTR (var);
1770 /* Uh, if the vuse is a multiuse, we can't really do much
1771 here, sadly, since we don't know which value number of
1772 which vuse to use. */
1773 if (VUSE_VECT_NUM_ELEM (*vv) != 1)
1776 use = VUSE_ELEMENT_VAR (*vv, 0);
1778 VN_INFO (def)->use_processed = true;
1779 changed |= set_ssa_val_to (def, SSA_VAL (use));
1786 /* Visit and value number PHI, return true if the value number
1790 visit_phi (gimple phi)
1792 bool changed = false;
1794 tree sameval = VN_TOP;
1795 bool allsame = true;
1798 /* TODO: We could check for this in init_sccvn, and replace this
1799 with a gcc_assert. */
1800 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
1801 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1803 /* See if all non-TOP arguments have the same value. TOP is
1804 equivalent to everything, so we can ignore it. */
1805 for (i = 0; i < gimple_phi_num_args (phi); i++)
1807 tree def = PHI_ARG_DEF (phi, i);
1809 if (TREE_CODE (def) == SSA_NAME)
1810 def = SSA_VAL (def);
1813 if (sameval == VN_TOP)
1819 if (!expressions_equal_p (def, sameval))
1827 /* If all value numbered to the same value, the phi node has that
1831 if (is_gimple_min_invariant (sameval))
1833 VN_INFO (PHI_RESULT (phi))->has_constants = true;
1834 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1838 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1839 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1842 if (TREE_CODE (sameval) == SSA_NAME)
1843 return visit_copy (PHI_RESULT (phi), sameval);
1845 return set_ssa_val_to (PHI_RESULT (phi), sameval);
1848 /* Otherwise, see if it is equivalent to a phi node in this block. */
1849 result = vn_phi_lookup (phi);
1852 if (TREE_CODE (result) == SSA_NAME)
1853 changed = visit_copy (PHI_RESULT (phi), result);
1855 changed = set_ssa_val_to (PHI_RESULT (phi), result);
1859 vn_phi_insert (phi, PHI_RESULT (phi));
1860 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1861 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1862 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1868 /* Return true if EXPR contains constants. */
1871 expr_has_constants (tree expr)
1873 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1876 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1879 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1880 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1881 /* Constants inside reference ops are rarely interesting, but
1882 it can take a lot of looking to find them. */
1884 case tcc_declaration:
1887 return is_gimple_min_invariant (expr);
1892 /* Return true if STMT contains constants. */
1895 stmt_has_constants (gimple stmt)
1897 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1900 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
1902 case GIMPLE_UNARY_RHS:
1903 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
1905 case GIMPLE_BINARY_RHS:
1906 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
1907 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
1908 case GIMPLE_SINGLE_RHS:
1909 /* Constants inside reference ops are rarely interesting, but
1910 it can take a lot of looking to find them. */
1911 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
1918 /* Replace SSA_NAMES in expr with their value numbers, and return the
1920 This is performed in place. */
1923 valueize_expr (tree expr)
1925 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1928 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1929 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1930 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1933 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1934 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1935 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1936 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
1937 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
1938 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
1946 /* Simplify the binary expression RHS, and return the result if
1950 simplify_binary_expression (gimple stmt)
1952 tree result = NULL_TREE;
1953 tree op0 = gimple_assign_rhs1 (stmt);
1954 tree op1 = gimple_assign_rhs2 (stmt);
1956 /* This will not catch every single case we could combine, but will
1957 catch those with constants. The goal here is to simultaneously
1958 combine constants between expressions, but avoid infinite
1959 expansion of expressions during simplification. */
1960 if (TREE_CODE (op0) == SSA_NAME)
1962 if (VN_INFO (op0)->has_constants
1963 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
1964 op0 = valueize_expr (vn_get_expr_for (op0));
1965 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
1966 op0 = SSA_VAL (op0);
1969 if (TREE_CODE (op1) == SSA_NAME)
1971 if (VN_INFO (op1)->has_constants)
1972 op1 = valueize_expr (vn_get_expr_for (op1));
1973 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
1974 op1 = SSA_VAL (op1);
1977 /* Avoid folding if nothing changed. */
1978 if (op0 == gimple_assign_rhs1 (stmt)
1979 && op1 == gimple_assign_rhs2 (stmt))
1982 fold_defer_overflow_warnings ();
1984 result = fold_binary (gimple_assign_rhs_code (stmt),
1985 TREE_TYPE (gimple_get_lhs (stmt)), op0, op1);
1987 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
1990 /* Make sure result is not a complex expression consisting
1991 of operators of operators (IE (a + b) + (a + c))
1992 Otherwise, we will end up with unbounded expressions if
1993 fold does anything at all. */
1994 if (result && valid_gimple_rhs_p (result))
2000 /* Simplify the unary expression RHS, and return the result if
2004 simplify_unary_expression (gimple stmt)
2006 tree result = NULL_TREE;
2007 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2009 /* We handle some tcc_reference codes here that are all
2010 GIMPLE_ASSIGN_SINGLE codes. */
2011 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2012 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2013 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2014 op0 = TREE_OPERAND (op0, 0);
2016 if (TREE_CODE (op0) != SSA_NAME)
2020 if (VN_INFO (op0)->has_constants)
2021 op0 = valueize_expr (vn_get_expr_for (op0));
2022 else if (gimple_assign_cast_p (stmt)
2023 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2024 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2025 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2027 /* We want to do tree-combining on conversion-like expressions.
2028 Make sure we feed only SSA_NAMEs or constants to fold though. */
2029 tree tem = valueize_expr (vn_get_expr_for (op0));
2030 if (UNARY_CLASS_P (tem)
2031 || BINARY_CLASS_P (tem)
2032 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2033 || TREE_CODE (tem) == SSA_NAME
2034 || is_gimple_min_invariant (tem))
2038 /* Avoid folding if nothing changed, but remember the expression. */
2039 if (op0 == orig_op0)
2042 result = fold_unary (gimple_assign_rhs_code (stmt),
2043 gimple_expr_type (stmt), op0);
2046 STRIP_USELESS_TYPE_CONVERSION (result);
2047 if (valid_gimple_rhs_p (result))
2054 /* Try to simplify RHS using equivalences and constant folding. */
2057 try_to_simplify (gimple stmt)
2061 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2062 in this case, there is no point in doing extra work. */
2063 if (gimple_assign_copy_p (stmt)
2064 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2067 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2069 case tcc_declaration:
2070 tem = get_symbol_constant_value (gimple_assign_rhs1 (stmt));
2076 /* Do not do full-blown reference lookup here, but simplify
2077 reads from constant aggregates. */
2078 tem = fold_const_aggregate_ref (gimple_assign_rhs1 (stmt));
2082 /* Fallthrough for some codes that can operate on registers. */
2083 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2084 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2085 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2087 /* We could do a little more with unary ops, if they expand
2088 into binary ops, but it's debatable whether it is worth it. */
2090 return simplify_unary_expression (stmt);
2092 case tcc_comparison:
2094 return simplify_binary_expression (stmt);
2103 /* Visit and value number USE, return true if the value number
2107 visit_use (tree use)
2109 bool changed = false;
2110 gimple stmt = SSA_NAME_DEF_STMT (use);
2112 VN_INFO (use)->use_processed = true;
2114 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
2115 if (dump_file && (dump_flags & TDF_DETAILS)
2116 && !SSA_NAME_IS_DEFAULT_DEF (use))
2118 fprintf (dump_file, "Value numbering ");
2119 print_generic_expr (dump_file, use, 0);
2120 fprintf (dump_file, " stmt = ");
2121 print_gimple_stmt (dump_file, stmt, 0, 0);
2124 /* Handle uninitialized uses. */
2125 if (SSA_NAME_IS_DEFAULT_DEF (use))
2126 changed = set_ssa_val_to (use, use);
2129 if (gimple_code (stmt) == GIMPLE_PHI)
2130 changed = visit_phi (stmt);
2131 else if (!gimple_has_lhs (stmt)
2132 || gimple_has_volatile_ops (stmt)
2133 || stmt_could_throw_p (stmt))
2134 changed = defs_to_varying (stmt);
2135 else if (is_gimple_assign (stmt))
2137 tree lhs = gimple_assign_lhs (stmt);
2140 /* Shortcut for copies. Simplifying copies is pointless,
2141 since we copy the expression and value they represent. */
2142 if (gimple_assign_copy_p (stmt)
2143 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2144 && TREE_CODE (lhs) == SSA_NAME)
2146 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
2149 simplified = try_to_simplify (stmt);
2152 if (dump_file && (dump_flags & TDF_DETAILS))
2154 fprintf (dump_file, "RHS ");
2155 print_gimple_expr (dump_file, stmt, 0, 0);
2156 fprintf (dump_file, " simplified to ");
2157 print_generic_expr (dump_file, simplified, 0);
2158 if (TREE_CODE (lhs) == SSA_NAME)
2159 fprintf (dump_file, " has constants %d\n",
2160 expr_has_constants (simplified));
2162 fprintf (dump_file, "\n");
2165 /* Setting value numbers to constants will occasionally
2166 screw up phi congruence because constants are not
2167 uniquely associated with a single ssa name that can be
2170 && is_gimple_min_invariant (simplified)
2171 && TREE_CODE (lhs) == SSA_NAME)
2173 VN_INFO (lhs)->expr = simplified;
2174 VN_INFO (lhs)->has_constants = true;
2175 changed = set_ssa_val_to (lhs, simplified);
2179 && TREE_CODE (simplified) == SSA_NAME
2180 && TREE_CODE (lhs) == SSA_NAME)
2182 changed = visit_copy (lhs, simplified);
2185 else if (simplified)
2187 if (TREE_CODE (lhs) == SSA_NAME)
2189 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
2190 /* We have to unshare the expression or else
2191 valuizing may change the IL stream. */
2192 VN_INFO (lhs)->expr = unshare_expr (simplified);
2195 else if (stmt_has_constants (stmt)
2196 && TREE_CODE (lhs) == SSA_NAME)
2197 VN_INFO (lhs)->has_constants = true;
2198 else if (TREE_CODE (lhs) == SSA_NAME)
2200 /* We reset expr and constantness here because we may
2201 have been value numbering optimistically, and
2202 iterating. They may become non-constant in this case,
2203 even if they were optimistically constant. */
2205 VN_INFO (lhs)->has_constants = false;
2206 VN_INFO (lhs)->expr = NULL_TREE;
2209 if (TREE_CODE (lhs) == SSA_NAME
2210 /* We can substitute SSA_NAMEs that are live over
2211 abnormal edges with their constant value. */
2212 && !(gimple_assign_copy_p (stmt)
2213 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2215 && is_gimple_min_invariant (simplified))
2216 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2217 changed = defs_to_varying (stmt);
2218 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
2220 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
2222 else if (TREE_CODE (lhs) == SSA_NAME)
2224 if ((gimple_assign_copy_p (stmt)
2225 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2227 && is_gimple_min_invariant (simplified)))
2229 VN_INFO (lhs)->has_constants = true;
2231 changed = set_ssa_val_to (lhs, simplified);
2233 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
2237 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2239 case GIMPLE_UNARY_RHS:
2240 changed = visit_unary_op (lhs, stmt);
2242 case GIMPLE_BINARY_RHS:
2243 changed = visit_binary_op (lhs, stmt);
2245 case GIMPLE_SINGLE_RHS:
2246 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2248 case tcc_declaration:
2250 changed = visit_reference_op_load
2251 (lhs, gimple_assign_rhs1 (stmt), stmt);
2253 case tcc_expression:
2254 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
2256 changed = visit_unary_op (lhs, stmt);
2261 changed = defs_to_varying (stmt);
2265 changed = defs_to_varying (stmt);
2271 changed = defs_to_varying (stmt);
2273 else if (is_gimple_call (stmt))
2275 tree lhs = gimple_call_lhs (stmt);
2277 /* ??? We could try to simplify calls. */
2279 if (stmt_has_constants (stmt)
2280 && TREE_CODE (lhs) == SSA_NAME)
2281 VN_INFO (lhs)->has_constants = true;
2282 else if (TREE_CODE (lhs) == SSA_NAME)
2284 /* We reset expr and constantness here because we may
2285 have been value numbering optimistically, and
2286 iterating. They may become non-constant in this case,
2287 even if they were optimistically constant. */
2288 VN_INFO (lhs)->has_constants = false;
2289 VN_INFO (lhs)->expr = NULL_TREE;
2292 if (TREE_CODE (lhs) == SSA_NAME
2293 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2294 changed = defs_to_varying (stmt);
2295 /* ??? We should handle stores from calls. */
2296 else if (TREE_CODE (lhs) == SSA_NAME)
2298 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2299 changed = visit_reference_op_call (lhs, stmt);
2301 changed = defs_to_varying (stmt);
2304 changed = defs_to_varying (stmt);
2311 /* Compare two operands by reverse postorder index */
2314 compare_ops (const void *pa, const void *pb)
2316 const tree opa = *((const tree *)pa);
2317 const tree opb = *((const tree *)pb);
2318 gimple opstmta = SSA_NAME_DEF_STMT (opa);
2319 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
2323 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
2325 else if (gimple_nop_p (opstmta))
2327 else if (gimple_nop_p (opstmtb))
2330 bba = gimple_bb (opstmta);
2331 bbb = gimple_bb (opstmtb);
2342 if (gimple_code (opstmta) == GIMPLE_PHI
2343 && gimple_code (opstmtb) == GIMPLE_PHI)
2345 else if (gimple_code (opstmta) == GIMPLE_PHI)
2347 else if (gimple_code (opstmtb) == GIMPLE_PHI)
2349 return gimple_uid (opstmta) - gimple_uid (opstmtb);
2351 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
2354 /* Sort an array containing members of a strongly connected component
2355 SCC so that the members are ordered by RPO number.
2356 This means that when the sort is complete, iterating through the
2357 array will give you the members in RPO order. */
2360 sort_scc (VEC (tree, heap) *scc)
2362 qsort (VEC_address (tree, scc),
2363 VEC_length (tree, scc),
2368 /* Process a strongly connected component in the SSA graph. */
2371 process_scc (VEC (tree, heap) *scc)
2373 /* If the SCC has a single member, just visit it. */
2375 if (VEC_length (tree, scc) == 1)
2377 tree use = VEC_index (tree, scc, 0);
2378 if (!VN_INFO (use)->use_processed)
2385 unsigned int iterations = 0;
2386 bool changed = true;
2388 /* Iterate over the SCC with the optimistic table until it stops
2390 current_info = optimistic_info;
2395 /* As we are value-numbering optimistically we have to
2396 clear the expression tables and the simplified expressions
2397 in each iteration until we converge. */
2398 htab_empty (optimistic_info->nary);
2399 htab_empty (optimistic_info->phis);
2400 htab_empty (optimistic_info->references);
2401 obstack_free (&optimistic_info->nary_obstack, NULL);
2402 gcc_obstack_init (&optimistic_info->nary_obstack);
2403 empty_alloc_pool (optimistic_info->phis_pool);
2404 empty_alloc_pool (optimistic_info->references_pool);
2405 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2406 VN_INFO (var)->expr = NULL_TREE;
2407 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2408 changed |= visit_use (var);
2411 statistics_histogram_event (cfun, "SCC iterations", iterations);
2413 /* Finally, visit the SCC once using the valid table. */
2414 current_info = valid_info;
2415 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2420 DEF_VEC_O(ssa_op_iter);
2421 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
2423 /* Pop the components of the found SCC for NAME off the SCC stack
2424 and process them. Returns true if all went well, false if
2425 we run into resource limits. */
2428 extract_and_process_scc_for_name (tree name)
2430 VEC (tree, heap) *scc = NULL;
2433 /* Found an SCC, pop the components off the SCC stack and
2437 x = VEC_pop (tree, sccstack);
2439 VN_INFO (x)->on_sccstack = false;
2440 VEC_safe_push (tree, heap, scc, x);
2441 } while (x != name);
2443 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2444 if (VEC_length (tree, scc)
2445 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
2448 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
2449 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
2450 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
2454 if (VEC_length (tree, scc) > 1)
2457 if (dump_file && (dump_flags & TDF_DETAILS))
2458 print_scc (dump_file, scc);
2462 VEC_free (tree, heap, scc);
2467 /* Depth first search on NAME to discover and process SCC's in the SSA
2469 Execution of this algorithm relies on the fact that the SCC's are
2470 popped off the stack in topological order.
2471 Returns true if successful, false if we stopped processing SCC's due
2472 to resource constraints. */
2477 VEC(ssa_op_iter, heap) *itervec = NULL;
2478 VEC(tree, heap) *namevec = NULL;
2479 use_operand_p usep = NULL;
2486 VN_INFO (name)->dfsnum = next_dfs_num++;
2487 VN_INFO (name)->visited = true;
2488 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
2490 VEC_safe_push (tree, heap, sccstack, name);
2491 VN_INFO (name)->on_sccstack = true;
2492 defstmt = SSA_NAME_DEF_STMT (name);
2494 /* Recursively DFS on our operands, looking for SCC's. */
2495 if (!gimple_nop_p (defstmt))
2497 /* Push a new iterator. */
2498 if (gimple_code (defstmt) == GIMPLE_PHI)
2499 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
2501 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
2508 /* If we are done processing uses of a name, go up the stack
2509 of iterators and process SCCs as we found them. */
2510 if (op_iter_done (&iter))
2512 /* See if we found an SCC. */
2513 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
2514 if (!extract_and_process_scc_for_name (name))
2516 VEC_free (tree, heap, namevec);
2517 VEC_free (ssa_op_iter, heap, itervec);
2521 /* Check if we are done. */
2522 if (VEC_empty (tree, namevec))
2524 VEC_free (tree, heap, namevec);
2525 VEC_free (ssa_op_iter, heap, itervec);
2529 /* Restore the last use walker and continue walking there. */
2531 name = VEC_pop (tree, namevec);
2532 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
2533 sizeof (ssa_op_iter));
2534 VEC_pop (ssa_op_iter, itervec);
2535 goto continue_walking;
2538 use = USE_FROM_PTR (usep);
2540 /* Since we handle phi nodes, we will sometimes get
2541 invariants in the use expression. */
2542 if (TREE_CODE (use) == SSA_NAME)
2544 if (! (VN_INFO (use)->visited))
2546 /* Recurse by pushing the current use walking state on
2547 the stack and starting over. */
2548 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
2549 VEC_safe_push(tree, heap, namevec, name);
2554 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
2555 VN_INFO (use)->low);
2557 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
2558 && VN_INFO (use)->on_sccstack)
2560 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
2561 VN_INFO (name)->low);
2565 usep = op_iter_next_use (&iter);
2569 /* Allocate a value number table. */
2572 allocate_vn_table (vn_tables_t table)
2574 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
2575 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
2576 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
2579 gcc_obstack_init (&table->nary_obstack);
2580 table->phis_pool = create_alloc_pool ("VN phis",
2581 sizeof (struct vn_phi_s),
2583 table->references_pool = create_alloc_pool ("VN references",
2584 sizeof (struct vn_reference_s),
2588 /* Free a value number table. */
2591 free_vn_table (vn_tables_t table)
2593 htab_delete (table->phis);
2594 htab_delete (table->nary);
2595 htab_delete (table->references);
2596 obstack_free (&table->nary_obstack, NULL);
2597 free_alloc_pool (table->phis_pool);
2598 free_alloc_pool (table->references_pool);
2606 int *rpo_numbers_temp;
2608 calculate_dominance_info (CDI_DOMINATORS);
2610 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
2613 constant_value_ids = BITMAP_ALLOC (NULL);
2618 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
2619 /* VEC_alloc doesn't actually grow it to the right size, it just
2620 preallocates the space to do so. */
2621 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
2622 gcc_obstack_init (&vn_ssa_aux_obstack);
2624 shared_lookup_phiargs = NULL;
2625 shared_lookup_vops = NULL;
2626 shared_lookup_references = NULL;
2627 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2628 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2629 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
2631 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
2632 the i'th block in RPO order is bb. We want to map bb's to RPO
2633 numbers, so we need to rearrange this array. */
2634 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
2635 rpo_numbers[rpo_numbers_temp[j]] = j;
2637 XDELETE (rpo_numbers_temp);
2639 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
2641 /* Create the VN_INFO structures, and initialize value numbers to
2643 for (i = 0; i < num_ssa_names; i++)
2645 tree name = ssa_name (i);
2648 VN_INFO_GET (name)->valnum = VN_TOP;
2649 VN_INFO (name)->expr = NULL_TREE;
2650 VN_INFO (name)->value_id = 0;
2654 renumber_gimple_stmt_uids ();
2656 /* Create the valid and optimistic value numbering tables. */
2657 valid_info = XCNEW (struct vn_tables_s);
2658 allocate_vn_table (valid_info);
2659 optimistic_info = XCNEW (struct vn_tables_s);
2660 allocate_vn_table (optimistic_info);
2668 htab_delete (constant_to_value_id);
2669 BITMAP_FREE (constant_value_ids);
2670 VEC_free (tree, heap, shared_lookup_phiargs);
2671 VEC_free (tree, gc, shared_lookup_vops);
2672 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
2673 XDELETEVEC (rpo_numbers);
2675 for (i = 0; i < num_ssa_names; i++)
2677 tree name = ssa_name (i);
2679 && VN_INFO (name)->needs_insertion)
2680 release_ssa_name (name);
2682 obstack_free (&vn_ssa_aux_obstack, NULL);
2683 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
2685 VEC_free (tree, heap, sccstack);
2686 free_vn_table (valid_info);
2687 XDELETE (valid_info);
2688 free_vn_table (optimistic_info);
2689 XDELETE (optimistic_info);
2692 /* Set the value ids in the valid hash tables. */
2695 set_hashtable_value_ids (void)
2702 /* Now set the value ids of the things we had put in the hash
2705 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
2706 vno, vn_nary_op_t, hi)
2710 if (TREE_CODE (vno->result) == SSA_NAME)
2711 vno->value_id = VN_INFO (vno->result)->value_id;
2712 else if (is_gimple_min_invariant (vno->result))
2713 vno->value_id = get_or_alloc_constant_value_id (vno->result);
2717 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
2722 if (TREE_CODE (vp->result) == SSA_NAME)
2723 vp->value_id = VN_INFO (vp->result)->value_id;
2724 else if (is_gimple_min_invariant (vp->result))
2725 vp->value_id = get_or_alloc_constant_value_id (vp->result);
2729 FOR_EACH_HTAB_ELEMENT (valid_info->references,
2730 vr, vn_reference_t, hi)
2734 if (TREE_CODE (vr->result) == SSA_NAME)
2735 vr->value_id = VN_INFO (vr->result)->value_id;
2736 else if (is_gimple_min_invariant (vr->result))
2737 vr->value_id = get_or_alloc_constant_value_id (vr->result);
2742 /* Do SCCVN. Returns true if it finished, false if we bailed out
2743 due to resource constraints. */
2746 run_scc_vn (bool may_insert_arg)
2750 bool changed = true;
2752 may_insert = may_insert_arg;
2755 current_info = valid_info;
2757 for (param = DECL_ARGUMENTS (current_function_decl);
2759 param = TREE_CHAIN (param))
2761 if (gimple_default_def (cfun, param) != NULL)
2763 tree def = gimple_default_def (cfun, param);
2764 SSA_VAL (def) = def;
2768 for (i = 1; i < num_ssa_names; ++i)
2770 tree name = ssa_name (i);
2772 && VN_INFO (name)->visited == false
2773 && !has_zero_uses (name))
2782 /* Initialize the value ids. */
2784 for (i = 1; i < num_ssa_names; ++i)
2786 tree name = ssa_name (i);
2790 info = VN_INFO (name);
2791 if (info->valnum == name)
2792 info->value_id = get_next_value_id ();
2793 else if (is_gimple_min_invariant (info->valnum))
2794 info->value_id = get_or_alloc_constant_value_id (info->valnum);
2797 /* Propagate until they stop changing. */
2801 for (i = 1; i < num_ssa_names; ++i)
2803 tree name = ssa_name (i);
2807 info = VN_INFO (name);
2808 if (TREE_CODE (info->valnum) == SSA_NAME
2809 && info->valnum != name
2810 && info->value_id != VN_INFO (info->valnum)->value_id)
2813 info->value_id = VN_INFO (info->valnum)->value_id;
2818 set_hashtable_value_ids ();
2820 if (dump_file && (dump_flags & TDF_DETAILS))
2822 fprintf (dump_file, "Value numbers:\n");
2823 for (i = 0; i < num_ssa_names; i++)
2825 tree name = ssa_name (i);
2827 && VN_INFO (name)->visited
2828 && SSA_VAL (name) != name)
2830 print_generic_expr (dump_file, name, 0);
2831 fprintf (dump_file, " = ");
2832 print_generic_expr (dump_file, SSA_VAL (name), 0);
2833 fprintf (dump_file, "\n");
2842 /* Return the maximum value id we have ever seen. */
2845 get_max_value_id (void)
2847 return next_value_id;
2850 /* Return the next unique value id. */
2853 get_next_value_id (void)
2855 return next_value_id++;
2859 /* Compare two expressions E1 and E2 and return true if they are equal. */
2862 expressions_equal_p (tree e1, tree e2)
2864 /* The obvious case. */
2868 /* If only one of them is null, they cannot be equal. */
2872 /* Recurse on elements of lists. */
2873 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
2877 for (lop1 = e1, lop2 = e2;
2879 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
2883 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
2889 /* Now perform the actual comparison. */
2890 if (TREE_CODE (e1) == TREE_CODE (e2)
2891 && operand_equal_p (e1, e2, OEP_PURE_SAME))
2897 /* Sort the VUSE array so that we can do equality comparisons
2898 quicker on two vuse vecs. */
2901 sort_vuses (VEC (tree,gc) *vuses)
2903 if (VEC_length (tree, vuses) > 1)
2904 qsort (VEC_address (tree, vuses),
2905 VEC_length (tree, vuses),
2910 /* Sort the VUSE array so that we can do equality comparisons
2911 quicker on two vuse vecs. */
2914 sort_vuses_heap (VEC (tree,heap) *vuses)
2916 if (VEC_length (tree, vuses) > 1)
2917 qsort (VEC_address (tree, vuses),
2918 VEC_length (tree, vuses),