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:
599 /* The only operand is the address, which gets its own
600 vn_reference_op_s structure. */
602 case MISALIGNED_INDIRECT_REF:
603 temp.op0 = TREE_OPERAND (ref, 1);
606 /* Record bits and position. */
607 temp.op0 = TREE_OPERAND (ref, 1);
608 temp.op1 = TREE_OPERAND (ref, 2);
611 /* The field decl is enough to unambiguously specify the field,
612 a matching type is not necessary and a mismatching type
613 is always a spurious difference. */
614 temp.type = NULL_TREE;
616 /* If this is a reference to a union member, record the union
617 member size as operand. Do so only if we are doing
618 expression insertion (during FRE), as PRE currently gets
619 confused with this. */
621 && TREE_CODE (DECL_CONTEXT (TREE_OPERAND (ref, 1))) == UNION_TYPE
622 && integer_zerop (DECL_FIELD_OFFSET (TREE_OPERAND (ref, 1)))
623 && integer_zerop (DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1))))
624 temp.op0 = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)));
627 /* Record field as operand. */
628 temp.op0 = TREE_OPERAND (ref, 1);
629 temp.op1 = TREE_OPERAND (ref, 2);
631 case ARRAY_RANGE_REF:
633 /* Record index as operand. */
634 temp.op0 = TREE_OPERAND (ref, 1);
635 temp.op1 = TREE_OPERAND (ref, 2);
636 temp.op2 = TREE_OPERAND (ref, 3);
652 if (is_gimple_min_invariant (ref))
658 /* These are only interesting for their operands, their
659 existence, and their type. They will never be the last
660 ref in the chain of references (IE they require an
661 operand), so we don't have to put anything
662 for op* as it will be handled by the iteration */
665 case VIEW_CONVERT_EXPR:
670 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
672 if (REFERENCE_CLASS_P (ref)
673 || (TREE_CODE (ref) == ADDR_EXPR
674 && !is_gimple_min_invariant (ref)))
675 ref = TREE_OPERAND (ref, 0);
681 /* Re-create a reference tree from the reference ops OPS.
682 Returns NULL_TREE if the ops were not handled.
683 This routine needs to be kept in sync with copy_reference_ops_from_ref. */
686 get_ref_from_reference_ops (VEC(vn_reference_op_s, heap) *ops)
688 vn_reference_op_t op;
690 tree ref, *op0_p = &ref;
692 for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
699 case ALIGN_INDIRECT_REF:
701 *op0_p = build1 (op->opcode, op->type, NULL_TREE);
702 op0_p = &TREE_OPERAND (*op0_p, 0);
705 case MISALIGNED_INDIRECT_REF:
706 *op0_p = build2 (MISALIGNED_INDIRECT_REF, op->type,
708 op0_p = &TREE_OPERAND (*op0_p, 0);
712 *op0_p = build3 (BIT_FIELD_REF, op->type, NULL_TREE,
714 op0_p = &TREE_OPERAND (*op0_p, 0);
718 *op0_p = build3 (COMPONENT_REF, TREE_TYPE (op->op0), NULL_TREE,
720 op0_p = &TREE_OPERAND (*op0_p, 0);
723 case ARRAY_RANGE_REF:
725 *op0_p = build4 (op->opcode, op->type, NULL_TREE,
726 op->op0, op->op1, op->op2);
727 op0_p = &TREE_OPERAND (*op0_p, 0);
745 if (op->op0 != NULL_TREE)
747 gcc_assert (is_gimple_min_invariant (op->op0));
754 case VIEW_CONVERT_EXPR:
755 *op0_p = build1 (op->opcode, op->type, NULL_TREE);
756 op0_p = &TREE_OPERAND (*op0_p, 0);
767 /* Copy the operations present in load/store/call REF into RESULT, a vector of
768 vn_reference_op_s's. */
771 copy_reference_ops_from_call (gimple call,
772 VEC(vn_reference_op_s, heap) **result)
774 vn_reference_op_s temp;
777 /* Copy the type, opcode, function being called and static chain. */
778 memset (&temp, 0, sizeof (temp));
779 temp.type = gimple_call_return_type (call);
780 temp.opcode = CALL_EXPR;
781 temp.op0 = gimple_call_fn (call);
782 temp.op1 = gimple_call_chain (call);
783 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
785 /* Copy the call arguments. As they can be references as well,
786 just chain them together. */
787 for (i = 0; i < gimple_call_num_args (call); ++i)
789 tree callarg = gimple_call_arg (call, i);
790 copy_reference_ops_from_ref (callarg, result);
794 /* Create a vector of vn_reference_op_s structures from REF, a
795 REFERENCE_CLASS_P tree. The vector is not shared. */
797 static VEC(vn_reference_op_s, heap) *
798 create_reference_ops_from_ref (tree ref)
800 VEC (vn_reference_op_s, heap) *result = NULL;
802 copy_reference_ops_from_ref (ref, &result);
806 /* Create a vector of vn_reference_op_s structures from CALL, a
807 call statement. The vector is not shared. */
809 static VEC(vn_reference_op_s, heap) *
810 create_reference_ops_from_call (gimple call)
812 VEC (vn_reference_op_s, heap) *result = NULL;
814 copy_reference_ops_from_call (call, &result);
818 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
820 /* Create a vector of vn_reference_op_s structures from REF, a
821 REFERENCE_CLASS_P tree. The vector is shared among all callers of
824 static VEC(vn_reference_op_s, heap) *
825 shared_reference_ops_from_ref (tree ref)
829 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
830 copy_reference_ops_from_ref (ref, &shared_lookup_references);
831 return shared_lookup_references;
834 /* Create a vector of vn_reference_op_s structures from CALL, a
835 call statement. The vector is shared among all callers of
838 static VEC(vn_reference_op_s, heap) *
839 shared_reference_ops_from_call (gimple call)
843 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
844 copy_reference_ops_from_call (call, &shared_lookup_references);
845 return shared_lookup_references;
849 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
850 structures into their value numbers. This is done in-place, and
851 the vector passed in is returned. */
853 static VEC (vn_reference_op_s, heap) *
854 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
856 vn_reference_op_t vro;
859 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
861 if (vro->opcode == SSA_NAME
862 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
864 vro->op0 = SSA_VAL (vro->op0);
865 /* If it transforms from an SSA_NAME to a constant, update
867 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
868 vro->opcode = TREE_CODE (vro->op0);
870 /* TODO: Do we want to valueize op2 and op1 of
871 ARRAY_REF/COMPONENT_REF for Ada */
878 /* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
879 their value numbers. This is done in-place, and the vector passed
882 static VEC (tree, gc) *
883 valueize_vuses (VEC (tree, gc) *orig)
885 bool made_replacement = false;
889 for (i = 0; VEC_iterate (tree, orig, i, vuse); i++)
891 if (vuse != SSA_VAL (vuse))
893 made_replacement = true;
894 VEC_replace (tree, orig, i, SSA_VAL (vuse));
898 if (made_replacement && VEC_length (tree, orig) > 1)
904 /* Return the single reference statement defining all virtual uses
905 in VUSES or NULL_TREE, if there are multiple defining statements.
906 Take into account only definitions that alias REF if following
910 get_def_ref_stmt_vuses (tree ref, VEC (tree, gc) *vuses)
916 gcc_assert (VEC_length (tree, vuses) >= 1);
918 def_stmt = SSA_NAME_DEF_STMT (VEC_index (tree, vuses, 0));
919 if (gimple_code (def_stmt) == GIMPLE_PHI)
921 /* We can only handle lookups over PHI nodes for a single
923 if (VEC_length (tree, vuses) == 1)
925 def_stmt = get_single_def_stmt_from_phi (ref, def_stmt);
932 /* Verify each VUSE reaches the same defining stmt. */
933 for (i = 1; VEC_iterate (tree, vuses, i, vuse); ++i)
935 gimple tmp = SSA_NAME_DEF_STMT (vuse);
940 /* Now see if the definition aliases ref, and loop until it does. */
943 && is_gimple_assign (def_stmt)
944 && !refs_may_alias_p (ref, gimple_get_lhs (def_stmt)))
945 def_stmt = get_single_def_stmt_with_phi (ref, def_stmt);
950 /* Lookup a SCCVN reference operation VR in the current hash table.
951 Returns the resulting value number if it exists in the hash table,
952 NULL_TREE otherwise. VNRESULT will be filled in with the actual
953 vn_reference_t stored in the hashtable if something is found. */
956 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
962 slot = htab_find_slot_with_hash (current_info->references, vr,
964 if (!slot && current_info == optimistic_info)
965 slot = htab_find_slot_with_hash (valid_info->references, vr,
970 *vnresult = (vn_reference_t)*slot;
971 return ((vn_reference_t)*slot)->result;
978 /* Lookup a reference operation by it's parts, in the current hash table.
979 Returns the resulting value number if it exists in the hash table,
980 NULL_TREE otherwise. VNRESULT will be filled in with the actual
981 vn_reference_t stored in the hashtable if something is found. */
984 vn_reference_lookup_pieces (VEC (tree, gc) *vuses,
985 VEC (vn_reference_op_s, heap) *operands,
986 vn_reference_t *vnresult, bool maywalk)
988 struct vn_reference_s vr1;
993 vr1.vuses = valueize_vuses (vuses);
994 vr1.operands = valueize_refs (operands);
995 vr1.hashcode = vn_reference_compute_hash (&vr1);
996 result = vn_reference_lookup_1 (&vr1, vnresult);
998 /* If there is a single defining statement for all virtual uses, we can
999 use that, following virtual use-def chains. */
1003 && VEC_length (tree, vr1.vuses) >= 1)
1005 tree ref = get_ref_from_reference_ops (operands);
1008 && (def_stmt = get_def_ref_stmt_vuses (ref, vr1.vuses))
1009 && is_gimple_assign (def_stmt))
1011 /* We are now at an aliasing definition for the vuses we want to
1012 look up. Re-do the lookup with the vdefs for this stmt. */
1013 vdefs_to_vec (def_stmt, &vuses);
1014 vr1.vuses = valueize_vuses (vuses);
1015 vr1.hashcode = vn_reference_compute_hash (&vr1);
1016 result = vn_reference_lookup_1 (&vr1, vnresult);
1023 /* Lookup OP in the current hash table, and return the resulting value
1024 number if it exists in the hash table. Return NULL_TREE if it does
1025 not exist in the hash table or if the result field of the structure
1026 was NULL.. VNRESULT will be filled in with the vn_reference_t
1027 stored in the hashtable if one exists. */
1030 vn_reference_lookup (tree op, VEC (tree, gc) *vuses, bool maywalk,
1031 vn_reference_t *vnresult)
1033 struct vn_reference_s vr1;
1039 vr1.vuses = valueize_vuses (vuses);
1040 vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
1041 vr1.hashcode = vn_reference_compute_hash (&vr1);
1042 result = vn_reference_lookup_1 (&vr1, vnresult);
1044 /* If there is a single defining statement for all virtual uses, we can
1045 use that, following virtual use-def chains. */
1049 && VEC_length (tree, vr1.vuses) >= 1
1050 && (def_stmt = get_def_ref_stmt_vuses (op, vr1.vuses))
1051 && is_gimple_assign (def_stmt))
1053 /* We are now at an aliasing definition for the vuses we want to
1054 look up. Re-do the lookup with the vdefs for this stmt. */
1055 vdefs_to_vec (def_stmt, &vuses);
1056 vr1.vuses = valueize_vuses (vuses);
1057 vr1.hashcode = vn_reference_compute_hash (&vr1);
1058 result = vn_reference_lookup_1 (&vr1, vnresult);
1065 /* Insert OP into the current hash table with a value number of
1066 RESULT, and return the resulting reference structure we created. */
1069 vn_reference_insert (tree op, tree result, VEC (tree, gc) *vuses)
1074 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1075 if (TREE_CODE (result) == SSA_NAME)
1076 vr1->value_id = VN_INFO (result)->value_id;
1078 vr1->value_id = get_or_alloc_constant_value_id (result);
1079 vr1->vuses = valueize_vuses (vuses);
1080 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1081 vr1->hashcode = vn_reference_compute_hash (vr1);
1082 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1084 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1087 /* Because we lookup stores using vuses, and value number failures
1088 using the vdefs (see visit_reference_op_store for how and why),
1089 it's possible that on failure we may try to insert an already
1090 inserted store. This is not wrong, there is no ssa name for a
1091 store that we could use as a differentiator anyway. Thus, unlike
1092 the other lookup functions, you cannot gcc_assert (!*slot)
1095 /* But free the old slot in case of a collision. */
1097 free_reference (*slot);
1103 /* Insert a reference by it's pieces into the current hash table with
1104 a value number of RESULT. Return the resulting reference
1105 structure we created. */
1108 vn_reference_insert_pieces (VEC (tree, gc) *vuses,
1109 VEC (vn_reference_op_s, heap) *operands,
1110 tree result, unsigned int value_id)
1116 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1117 vr1->value_id = value_id;
1118 vr1->vuses = valueize_vuses (vuses);
1119 vr1->operands = valueize_refs (operands);
1120 vr1->hashcode = vn_reference_compute_hash (vr1);
1121 if (result && TREE_CODE (result) == SSA_NAME)
1122 result = SSA_VAL (result);
1123 vr1->result = result;
1125 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1128 /* At this point we should have all the things inserted that we have
1129 seen before, and we should never try inserting something that
1131 gcc_assert (!*slot);
1133 free_reference (*slot);
1139 /* Compute and return the hash value for nary operation VBO1. */
1142 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1147 for (i = 0; i < vno1->length; ++i)
1148 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1149 vno1->op[i] = SSA_VAL (vno1->op[i]);
1151 if (vno1->length == 2
1152 && commutative_tree_code (vno1->opcode)
1153 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1155 tree temp = vno1->op[0];
1156 vno1->op[0] = vno1->op[1];
1160 for (i = 0; i < vno1->length; ++i)
1161 hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
1166 /* Return the computed hashcode for nary operation P1. */
1169 vn_nary_op_hash (const void *p1)
1171 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1172 return vno1->hashcode;
1175 /* Compare nary operations P1 and P2 and return true if they are
1179 vn_nary_op_eq (const void *p1, const void *p2)
1181 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1182 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1185 if (vno1->opcode != vno2->opcode
1186 || vno1->type != vno2->type)
1189 for (i = 0; i < vno1->length; ++i)
1190 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1196 /* Lookup a n-ary operation by its pieces and return the resulting value
1197 number if it exists in the hash table. Return NULL_TREE if it does
1198 not exist in the hash table or if the result field of the operation
1199 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1203 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
1204 tree type, tree op0, tree op1, tree op2,
1205 tree op3, vn_nary_op_t *vnresult)
1208 struct vn_nary_op_s vno1;
1212 vno1.length = length;
1218 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1219 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1221 if (!slot && current_info == optimistic_info)
1222 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1227 *vnresult = (vn_nary_op_t)*slot;
1228 return ((vn_nary_op_t)*slot)->result;
1231 /* Lookup OP in the current hash table, and return the resulting value
1232 number if it exists in the hash table. Return NULL_TREE if it does
1233 not exist in the hash table or if the result field of the operation
1234 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1238 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
1241 struct vn_nary_op_s vno1;
1246 vno1.opcode = TREE_CODE (op);
1247 vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
1248 vno1.type = TREE_TYPE (op);
1249 for (i = 0; i < vno1.length; ++i)
1250 vno1.op[i] = TREE_OPERAND (op, i);
1251 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1252 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1254 if (!slot && current_info == optimistic_info)
1255 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1260 *vnresult = (vn_nary_op_t)*slot;
1261 return ((vn_nary_op_t)*slot)->result;
1264 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1265 value number if it exists in the hash table. Return NULL_TREE if
1266 it does not exist in the hash table. VNRESULT will contain the
1267 vn_nary_op_t from the hashtable if it exists. */
1270 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
1273 struct vn_nary_op_s vno1;
1278 vno1.opcode = gimple_assign_rhs_code (stmt);
1279 vno1.length = gimple_num_ops (stmt) - 1;
1280 vno1.type = TREE_TYPE (gimple_assign_lhs (stmt));
1281 for (i = 0; i < vno1.length; ++i)
1282 vno1.op[i] = gimple_op (stmt, i + 1);
1283 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1284 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1286 if (!slot && current_info == optimistic_info)
1287 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1292 *vnresult = (vn_nary_op_t)*slot;
1293 return ((vn_nary_op_t)*slot)->result;
1296 /* Insert a n-ary operation into the current hash table using it's
1297 pieces. Return the vn_nary_op_t structure we created and put in
1301 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
1302 tree type, tree op0,
1303 tree op1, tree op2, tree op3,
1305 unsigned int value_id)
1310 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1311 (sizeof (struct vn_nary_op_s)
1312 - sizeof (tree) * (4 - length)));
1313 vno1->value_id = value_id;
1314 vno1->opcode = code;
1315 vno1->length = length;
1325 vno1->result = result;
1326 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1327 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1329 gcc_assert (!*slot);
1336 /* Insert OP into the current hash table with a value number of
1337 RESULT. Return the vn_nary_op_t structure we created and put in
1341 vn_nary_op_insert (tree op, tree result)
1343 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
1348 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1349 (sizeof (struct vn_nary_op_s)
1350 - sizeof (tree) * (4 - length)));
1351 vno1->value_id = VN_INFO (result)->value_id;
1352 vno1->opcode = TREE_CODE (op);
1353 vno1->length = length;
1354 vno1->type = TREE_TYPE (op);
1355 for (i = 0; i < vno1->length; ++i)
1356 vno1->op[i] = TREE_OPERAND (op, i);
1357 vno1->result = result;
1358 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1359 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1361 gcc_assert (!*slot);
1367 /* Insert the rhs of STMT into the current hash table with a value number of
1371 vn_nary_op_insert_stmt (gimple stmt, tree result)
1373 unsigned length = gimple_num_ops (stmt) - 1;
1378 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1379 (sizeof (struct vn_nary_op_s)
1380 - sizeof (tree) * (4 - length)));
1381 vno1->value_id = VN_INFO (result)->value_id;
1382 vno1->opcode = gimple_assign_rhs_code (stmt);
1383 vno1->length = length;
1384 vno1->type = TREE_TYPE (gimple_assign_lhs (stmt));
1385 for (i = 0; i < vno1->length; ++i)
1386 vno1->op[i] = gimple_op (stmt, i + 1);
1387 vno1->result = result;
1388 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1389 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1391 gcc_assert (!*slot);
1397 /* Compute a hashcode for PHI operation VP1 and return it. */
1399 static inline hashval_t
1400 vn_phi_compute_hash (vn_phi_t vp1)
1402 hashval_t result = 0;
1406 result = vp1->block->index;
1408 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1410 if (phi1op == VN_TOP)
1412 result += iterative_hash_expr (phi1op, result);
1418 /* Return the computed hashcode for phi operation P1. */
1421 vn_phi_hash (const void *p1)
1423 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1424 return vp1->hashcode;
1427 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1430 vn_phi_eq (const void *p1, const void *p2)
1432 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1433 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
1435 if (vp1->block == vp2->block)
1440 /* Any phi in the same block will have it's arguments in the
1441 same edge order, because of how we store phi nodes. */
1442 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1444 tree phi2op = VEC_index (tree, vp2->phiargs, i);
1445 if (phi1op == VN_TOP || phi2op == VN_TOP)
1447 if (!expressions_equal_p (phi1op, phi2op))
1455 static VEC(tree, heap) *shared_lookup_phiargs;
1457 /* Lookup PHI in the current hash table, and return the resulting
1458 value number if it exists in the hash table. Return NULL_TREE if
1459 it does not exist in the hash table. */
1462 vn_phi_lookup (gimple phi)
1465 struct vn_phi_s vp1;
1468 VEC_truncate (tree, shared_lookup_phiargs, 0);
1470 /* Canonicalize the SSA_NAME's to their value number. */
1471 for (i = 0; i < gimple_phi_num_args (phi); i++)
1473 tree def = PHI_ARG_DEF (phi, i);
1474 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1475 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
1477 vp1.phiargs = shared_lookup_phiargs;
1478 vp1.block = gimple_bb (phi);
1479 vp1.hashcode = vn_phi_compute_hash (&vp1);
1480 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
1482 if (!slot && current_info == optimistic_info)
1483 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
1487 return ((vn_phi_t)*slot)->result;
1490 /* Insert PHI into the current hash table with a value number of
1494 vn_phi_insert (gimple phi, tree result)
1497 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
1499 VEC (tree, heap) *args = NULL;
1501 /* Canonicalize the SSA_NAME's to their value number. */
1502 for (i = 0; i < gimple_phi_num_args (phi); i++)
1504 tree def = PHI_ARG_DEF (phi, i);
1505 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1506 VEC_safe_push (tree, heap, args, def);
1508 vp1->value_id = VN_INFO (result)->value_id;
1509 vp1->phiargs = args;
1510 vp1->block = gimple_bb (phi);
1511 vp1->result = result;
1512 vp1->hashcode = vn_phi_compute_hash (vp1);
1514 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
1517 /* Because we iterate over phi operations more than once, it's
1518 possible the slot might already exist here, hence no assert.*/
1524 /* Print set of components in strongly connected component SCC to OUT. */
1527 print_scc (FILE *out, VEC (tree, heap) *scc)
1532 fprintf (out, "SCC consists of: ");
1533 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1535 print_generic_expr (out, var, 0);
1538 fprintf (out, "\n");
1541 /* Set the value number of FROM to TO, return true if it has changed
1545 set_ssa_val_to (tree from, tree to)
1550 && TREE_CODE (to) == SSA_NAME
1551 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
1554 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1555 and invariants. So assert that here. */
1556 gcc_assert (to != NULL_TREE
1558 || TREE_CODE (to) == SSA_NAME
1559 || is_gimple_min_invariant (to)));
1561 if (dump_file && (dump_flags & TDF_DETAILS))
1563 fprintf (dump_file, "Setting value number of ");
1564 print_generic_expr (dump_file, from, 0);
1565 fprintf (dump_file, " to ");
1566 print_generic_expr (dump_file, to, 0);
1567 fprintf (dump_file, "\n");
1570 currval = SSA_VAL (from);
1572 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
1574 SSA_VAL (from) = to;
1580 /* Set all definitions in STMT to value number to themselves.
1581 Return true if a value number changed. */
1584 defs_to_varying (gimple stmt)
1586 bool changed = false;
1590 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1592 tree def = DEF_FROM_PTR (defp);
1594 VN_INFO (def)->use_processed = true;
1595 changed |= set_ssa_val_to (def, def);
1600 static bool expr_has_constants (tree expr);
1601 static tree try_to_simplify (gimple stmt);
1603 /* Visit a copy between LHS and RHS, return true if the value number
1607 visit_copy (tree lhs, tree rhs)
1609 /* Follow chains of copies to their destination. */
1610 while (TREE_CODE (rhs) == SSA_NAME
1611 && SSA_VAL (rhs) != rhs)
1612 rhs = SSA_VAL (rhs);
1614 /* The copy may have a more interesting constant filled expression
1615 (we don't, since we know our RHS is just an SSA name). */
1616 if (TREE_CODE (rhs) == SSA_NAME)
1618 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1619 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1622 return set_ssa_val_to (lhs, rhs);
1625 /* Visit a unary operator RHS, value number it, and return true if the
1626 value number of LHS has changed as a result. */
1629 visit_unary_op (tree lhs, gimple stmt)
1631 bool changed = false;
1632 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1636 changed = set_ssa_val_to (lhs, result);
1640 changed = set_ssa_val_to (lhs, lhs);
1641 vn_nary_op_insert_stmt (stmt, lhs);
1647 /* Visit a binary operator RHS, value number it, and return true if the
1648 value number of LHS has changed as a result. */
1651 visit_binary_op (tree lhs, gimple stmt)
1653 bool changed = false;
1654 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1658 changed = set_ssa_val_to (lhs, result);
1662 changed = set_ssa_val_to (lhs, lhs);
1663 vn_nary_op_insert_stmt (stmt, lhs);
1669 /* Visit a call STMT storing into LHS. Return true if the value number
1670 of the LHS has changed as a result. */
1673 visit_reference_op_call (tree lhs, gimple stmt)
1675 bool changed = false;
1676 struct vn_reference_s vr1;
1679 vr1.vuses = valueize_vuses (shared_vuses_from_stmt (stmt));
1680 vr1.operands = valueize_refs (shared_reference_ops_from_call (stmt));
1681 vr1.hashcode = vn_reference_compute_hash (&vr1);
1682 result = vn_reference_lookup_1 (&vr1, NULL);
1685 changed = set_ssa_val_to (lhs, result);
1686 if (TREE_CODE (result) == SSA_NAME
1687 && VN_INFO (result)->has_constants)
1688 VN_INFO (lhs)->has_constants = true;
1694 changed = set_ssa_val_to (lhs, lhs);
1695 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
1696 vr2->vuses = valueize_vuses (copy_vuses_from_stmt (stmt));
1697 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
1698 vr2->hashcode = vr1.hashcode;
1700 slot = htab_find_slot_with_hash (current_info->references,
1701 vr2, vr2->hashcode, INSERT);
1703 free_reference (*slot);
1710 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1711 and return true if the value number of the LHS has changed as a result. */
1714 visit_reference_op_load (tree lhs, tree op, gimple stmt)
1716 bool changed = false;
1717 tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt), true,
1720 /* We handle type-punning through unions by value-numbering based
1721 on offset and size of the access. Be prepared to handle a
1722 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1724 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
1726 /* We will be setting the value number of lhs to the value number
1727 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1728 So first simplify and lookup this expression to see if it
1729 is already available. */
1730 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
1732 && !is_gimple_min_invariant (val)
1733 && TREE_CODE (val) != SSA_NAME)
1735 tree tem = try_to_simplify (stmt);
1740 if (!is_gimple_min_invariant (val)
1741 && TREE_CODE (val) != SSA_NAME)
1742 result = vn_nary_op_lookup (val, NULL);
1743 /* If the expression is not yet available, value-number lhs to
1744 a new SSA_NAME we create. */
1745 if (!result && may_insert)
1747 result = make_ssa_name (SSA_NAME_VAR (lhs), NULL);
1748 /* Initialize value-number information properly. */
1749 VN_INFO_GET (result)->valnum = result;
1750 VN_INFO (result)->value_id = get_next_value_id ();
1751 VN_INFO (result)->expr = val;
1752 VN_INFO (result)->has_constants = expr_has_constants (val);
1753 VN_INFO (result)->needs_insertion = true;
1754 /* As all "inserted" statements are singleton SCCs, insert
1755 to the valid table. This is strictly needed to
1756 avoid re-generating new value SSA_NAMEs for the same
1757 expression during SCC iteration over and over (the
1758 optimistic table gets cleared after each iteration).
1759 We do not need to insert into the optimistic table, as
1760 lookups there will fall back to the valid table. */
1761 if (current_info == optimistic_info)
1763 current_info = valid_info;
1764 vn_nary_op_insert (val, result);
1765 current_info = optimistic_info;
1768 vn_nary_op_insert (val, result);
1769 if (dump_file && (dump_flags & TDF_DETAILS))
1771 fprintf (dump_file, "Inserting name ");
1772 print_generic_expr (dump_file, result, 0);
1773 fprintf (dump_file, " for expression ");
1774 print_generic_expr (dump_file, val, 0);
1775 fprintf (dump_file, "\n");
1782 changed = set_ssa_val_to (lhs, result);
1783 if (TREE_CODE (result) == SSA_NAME
1784 && VN_INFO (result)->has_constants)
1786 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
1787 VN_INFO (lhs)->has_constants = true;
1792 changed = set_ssa_val_to (lhs, lhs);
1793 vn_reference_insert (op, lhs, copy_vuses_from_stmt (stmt));
1800 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1801 and return true if the value number of the LHS has changed as a result. */
1804 visit_reference_op_store (tree lhs, tree op, gimple stmt)
1806 bool changed = false;
1808 bool resultsame = false;
1810 /* First we want to lookup using the *vuses* from the store and see
1811 if there the last store to this location with the same address
1814 The vuses represent the memory state before the store. If the
1815 memory state, address, and value of the store is the same as the
1816 last store to this location, then this store will produce the
1817 same memory state as that store.
1819 In this case the vdef versions for this store are value numbered to those
1820 vuse versions, since they represent the same memory state after
1823 Otherwise, the vdefs for the store are used when inserting into
1824 the table, since the store generates a new memory state. */
1826 result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt), false,
1831 if (TREE_CODE (result) == SSA_NAME)
1832 result = SSA_VAL (result);
1833 if (TREE_CODE (op) == SSA_NAME)
1835 resultsame = expressions_equal_p (result, op);
1838 if (!result || !resultsame)
1840 VEC(tree, gc) *vdefs = copy_vdefs_from_stmt (stmt);
1844 if (dump_file && (dump_flags & TDF_DETAILS))
1846 fprintf (dump_file, "No store match\n");
1847 fprintf (dump_file, "Value numbering store ");
1848 print_generic_expr (dump_file, lhs, 0);
1849 fprintf (dump_file, " to ");
1850 print_generic_expr (dump_file, op, 0);
1851 fprintf (dump_file, "\n");
1853 /* Have to set value numbers before insert, since insert is
1854 going to valueize the references in-place. */
1855 for (i = 0; VEC_iterate (tree, vdefs, i, vdef); i++)
1857 VN_INFO (vdef)->use_processed = true;
1858 changed |= set_ssa_val_to (vdef, vdef);
1861 /* Do not insert structure copies into the tables. */
1862 if (is_gimple_min_invariant (op)
1863 || is_gimple_reg (op))
1864 vn_reference_insert (lhs, op, vdefs);
1868 /* We had a match, so value number the vdefs to have the value
1869 number of the vuses they came from. */
1870 ssa_op_iter op_iter;
1874 if (dump_file && (dump_flags & TDF_DETAILS))
1875 fprintf (dump_file, "Store matched earlier value,"
1876 "value numbering store vdefs to matching vuses.\n");
1878 FOR_EACH_SSA_VDEF_OPERAND (var, vv, stmt, op_iter)
1880 tree def = DEF_FROM_PTR (var);
1883 /* Uh, if the vuse is a multiuse, we can't really do much
1884 here, sadly, since we don't know which value number of
1885 which vuse to use. */
1886 if (VUSE_VECT_NUM_ELEM (*vv) != 1)
1889 use = VUSE_ELEMENT_VAR (*vv, 0);
1891 VN_INFO (def)->use_processed = true;
1892 changed |= set_ssa_val_to (def, SSA_VAL (use));
1899 /* Visit and value number PHI, return true if the value number
1903 visit_phi (gimple phi)
1905 bool changed = false;
1907 tree sameval = VN_TOP;
1908 bool allsame = true;
1911 /* TODO: We could check for this in init_sccvn, and replace this
1912 with a gcc_assert. */
1913 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
1914 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1916 /* See if all non-TOP arguments have the same value. TOP is
1917 equivalent to everything, so we can ignore it. */
1918 for (i = 0; i < gimple_phi_num_args (phi); i++)
1920 tree def = PHI_ARG_DEF (phi, i);
1922 if (TREE_CODE (def) == SSA_NAME)
1923 def = SSA_VAL (def);
1926 if (sameval == VN_TOP)
1932 if (!expressions_equal_p (def, sameval))
1940 /* If all value numbered to the same value, the phi node has that
1944 if (is_gimple_min_invariant (sameval))
1946 VN_INFO (PHI_RESULT (phi))->has_constants = true;
1947 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1951 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1952 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1955 if (TREE_CODE (sameval) == SSA_NAME)
1956 return visit_copy (PHI_RESULT (phi), sameval);
1958 return set_ssa_val_to (PHI_RESULT (phi), sameval);
1961 /* Otherwise, see if it is equivalent to a phi node in this block. */
1962 result = vn_phi_lookup (phi);
1965 if (TREE_CODE (result) == SSA_NAME)
1966 changed = visit_copy (PHI_RESULT (phi), result);
1968 changed = set_ssa_val_to (PHI_RESULT (phi), result);
1972 vn_phi_insert (phi, PHI_RESULT (phi));
1973 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1974 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1975 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1981 /* Return true if EXPR contains constants. */
1984 expr_has_constants (tree expr)
1986 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1989 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1992 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1993 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1994 /* Constants inside reference ops are rarely interesting, but
1995 it can take a lot of looking to find them. */
1997 case tcc_declaration:
2000 return is_gimple_min_invariant (expr);
2005 /* Return true if STMT contains constants. */
2008 stmt_has_constants (gimple stmt)
2010 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2013 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2015 case GIMPLE_UNARY_RHS:
2016 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2018 case GIMPLE_BINARY_RHS:
2019 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2020 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
2021 case GIMPLE_SINGLE_RHS:
2022 /* Constants inside reference ops are rarely interesting, but
2023 it can take a lot of looking to find them. */
2024 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2031 /* Replace SSA_NAMES in expr with their value numbers, and return the
2033 This is performed in place. */
2036 valueize_expr (tree expr)
2038 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2041 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2042 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2043 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2046 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2047 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2048 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2049 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
2050 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
2051 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
2059 /* Simplify the binary expression RHS, and return the result if
2063 simplify_binary_expression (gimple stmt)
2065 tree result = NULL_TREE;
2066 tree op0 = gimple_assign_rhs1 (stmt);
2067 tree op1 = gimple_assign_rhs2 (stmt);
2069 /* This will not catch every single case we could combine, but will
2070 catch those with constants. The goal here is to simultaneously
2071 combine constants between expressions, but avoid infinite
2072 expansion of expressions during simplification. */
2073 if (TREE_CODE (op0) == SSA_NAME)
2075 if (VN_INFO (op0)->has_constants
2076 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
2077 op0 = valueize_expr (vn_get_expr_for (op0));
2078 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
2079 op0 = SSA_VAL (op0);
2082 if (TREE_CODE (op1) == SSA_NAME)
2084 if (VN_INFO (op1)->has_constants)
2085 op1 = valueize_expr (vn_get_expr_for (op1));
2086 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
2087 op1 = SSA_VAL (op1);
2090 /* Avoid folding if nothing changed. */
2091 if (op0 == gimple_assign_rhs1 (stmt)
2092 && op1 == gimple_assign_rhs2 (stmt))
2095 fold_defer_overflow_warnings ();
2097 result = fold_binary (gimple_assign_rhs_code (stmt),
2098 TREE_TYPE (gimple_get_lhs (stmt)), op0, op1);
2100 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2103 /* Make sure result is not a complex expression consisting
2104 of operators of operators (IE (a + b) + (a + c))
2105 Otherwise, we will end up with unbounded expressions if
2106 fold does anything at all. */
2107 if (result && valid_gimple_rhs_p (result))
2113 /* Simplify the unary expression RHS, and return the result if
2117 simplify_unary_expression (gimple stmt)
2119 tree result = NULL_TREE;
2120 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2122 /* We handle some tcc_reference codes here that are all
2123 GIMPLE_ASSIGN_SINGLE codes. */
2124 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2125 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2126 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2127 op0 = TREE_OPERAND (op0, 0);
2129 if (TREE_CODE (op0) != SSA_NAME)
2133 if (VN_INFO (op0)->has_constants)
2134 op0 = valueize_expr (vn_get_expr_for (op0));
2135 else if (gimple_assign_cast_p (stmt)
2136 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2137 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2138 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2140 /* We want to do tree-combining on conversion-like expressions.
2141 Make sure we feed only SSA_NAMEs or constants to fold though. */
2142 tree tem = valueize_expr (vn_get_expr_for (op0));
2143 if (UNARY_CLASS_P (tem)
2144 || BINARY_CLASS_P (tem)
2145 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2146 || TREE_CODE (tem) == SSA_NAME
2147 || is_gimple_min_invariant (tem))
2151 /* Avoid folding if nothing changed, but remember the expression. */
2152 if (op0 == orig_op0)
2155 result = fold_unary (gimple_assign_rhs_code (stmt),
2156 gimple_expr_type (stmt), op0);
2159 STRIP_USELESS_TYPE_CONVERSION (result);
2160 if (valid_gimple_rhs_p (result))
2167 /* Try to simplify RHS using equivalences and constant folding. */
2170 try_to_simplify (gimple stmt)
2174 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2175 in this case, there is no point in doing extra work. */
2176 if (gimple_assign_copy_p (stmt)
2177 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2180 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2182 case tcc_declaration:
2183 tem = get_symbol_constant_value (gimple_assign_rhs1 (stmt));
2189 /* Do not do full-blown reference lookup here, but simplify
2190 reads from constant aggregates. */
2191 tem = fold_const_aggregate_ref (gimple_assign_rhs1 (stmt));
2195 /* Fallthrough for some codes that can operate on registers. */
2196 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2197 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2198 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2200 /* We could do a little more with unary ops, if they expand
2201 into binary ops, but it's debatable whether it is worth it. */
2203 return simplify_unary_expression (stmt);
2205 case tcc_comparison:
2207 return simplify_binary_expression (stmt);
2216 /* Visit and value number USE, return true if the value number
2220 visit_use (tree use)
2222 bool changed = false;
2223 gimple stmt = SSA_NAME_DEF_STMT (use);
2225 VN_INFO (use)->use_processed = true;
2227 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
2228 if (dump_file && (dump_flags & TDF_DETAILS)
2229 && !SSA_NAME_IS_DEFAULT_DEF (use))
2231 fprintf (dump_file, "Value numbering ");
2232 print_generic_expr (dump_file, use, 0);
2233 fprintf (dump_file, " stmt = ");
2234 print_gimple_stmt (dump_file, stmt, 0, 0);
2237 /* Handle uninitialized uses. */
2238 if (SSA_NAME_IS_DEFAULT_DEF (use))
2239 changed = set_ssa_val_to (use, use);
2242 if (gimple_code (stmt) == GIMPLE_PHI)
2243 changed = visit_phi (stmt);
2244 else if (!gimple_has_lhs (stmt)
2245 || gimple_has_volatile_ops (stmt)
2246 || stmt_could_throw_p (stmt))
2247 changed = defs_to_varying (stmt);
2248 else if (is_gimple_assign (stmt))
2250 tree lhs = gimple_assign_lhs (stmt);
2253 /* Shortcut for copies. Simplifying copies is pointless,
2254 since we copy the expression and value they represent. */
2255 if (gimple_assign_copy_p (stmt)
2256 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2257 && TREE_CODE (lhs) == SSA_NAME)
2259 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
2262 simplified = try_to_simplify (stmt);
2265 if (dump_file && (dump_flags & TDF_DETAILS))
2267 fprintf (dump_file, "RHS ");
2268 print_gimple_expr (dump_file, stmt, 0, 0);
2269 fprintf (dump_file, " simplified to ");
2270 print_generic_expr (dump_file, simplified, 0);
2271 if (TREE_CODE (lhs) == SSA_NAME)
2272 fprintf (dump_file, " has constants %d\n",
2273 expr_has_constants (simplified));
2275 fprintf (dump_file, "\n");
2278 /* Setting value numbers to constants will occasionally
2279 screw up phi congruence because constants are not
2280 uniquely associated with a single ssa name that can be
2283 && is_gimple_min_invariant (simplified)
2284 && TREE_CODE (lhs) == SSA_NAME)
2286 VN_INFO (lhs)->expr = simplified;
2287 VN_INFO (lhs)->has_constants = true;
2288 changed = set_ssa_val_to (lhs, simplified);
2292 && TREE_CODE (simplified) == SSA_NAME
2293 && TREE_CODE (lhs) == SSA_NAME)
2295 changed = visit_copy (lhs, simplified);
2298 else if (simplified)
2300 if (TREE_CODE (lhs) == SSA_NAME)
2302 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
2303 /* We have to unshare the expression or else
2304 valuizing may change the IL stream. */
2305 VN_INFO (lhs)->expr = unshare_expr (simplified);
2308 else if (stmt_has_constants (stmt)
2309 && TREE_CODE (lhs) == SSA_NAME)
2310 VN_INFO (lhs)->has_constants = true;
2311 else if (TREE_CODE (lhs) == SSA_NAME)
2313 /* We reset expr and constantness here because we may
2314 have been value numbering optimistically, and
2315 iterating. They may become non-constant in this case,
2316 even if they were optimistically constant. */
2318 VN_INFO (lhs)->has_constants = false;
2319 VN_INFO (lhs)->expr = NULL_TREE;
2322 if (TREE_CODE (lhs) == SSA_NAME
2323 /* We can substitute SSA_NAMEs that are live over
2324 abnormal edges with their constant value. */
2325 && !(gimple_assign_copy_p (stmt)
2326 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2328 && is_gimple_min_invariant (simplified))
2329 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2330 changed = defs_to_varying (stmt);
2331 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
2333 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
2335 else if (TREE_CODE (lhs) == SSA_NAME)
2337 if ((gimple_assign_copy_p (stmt)
2338 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2340 && is_gimple_min_invariant (simplified)))
2342 VN_INFO (lhs)->has_constants = true;
2344 changed = set_ssa_val_to (lhs, simplified);
2346 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
2350 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2352 case GIMPLE_UNARY_RHS:
2353 changed = visit_unary_op (lhs, stmt);
2355 case GIMPLE_BINARY_RHS:
2356 changed = visit_binary_op (lhs, stmt);
2358 case GIMPLE_SINGLE_RHS:
2359 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2361 case tcc_declaration:
2363 changed = visit_reference_op_load
2364 (lhs, gimple_assign_rhs1 (stmt), stmt);
2366 case tcc_expression:
2367 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
2369 changed = visit_unary_op (lhs, stmt);
2374 changed = defs_to_varying (stmt);
2378 changed = defs_to_varying (stmt);
2384 changed = defs_to_varying (stmt);
2386 else if (is_gimple_call (stmt))
2388 tree lhs = gimple_call_lhs (stmt);
2390 /* ??? We could try to simplify calls. */
2392 if (stmt_has_constants (stmt)
2393 && TREE_CODE (lhs) == SSA_NAME)
2394 VN_INFO (lhs)->has_constants = true;
2395 else if (TREE_CODE (lhs) == SSA_NAME)
2397 /* We reset expr and constantness here because we may
2398 have been value numbering optimistically, and
2399 iterating. They may become non-constant in this case,
2400 even if they were optimistically constant. */
2401 VN_INFO (lhs)->has_constants = false;
2402 VN_INFO (lhs)->expr = NULL_TREE;
2405 if (TREE_CODE (lhs) == SSA_NAME
2406 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2407 changed = defs_to_varying (stmt);
2408 /* ??? We should handle stores from calls. */
2409 else if (TREE_CODE (lhs) == SSA_NAME)
2411 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2412 changed = visit_reference_op_call (lhs, stmt);
2414 changed = defs_to_varying (stmt);
2417 changed = defs_to_varying (stmt);
2424 /* Compare two operands by reverse postorder index */
2427 compare_ops (const void *pa, const void *pb)
2429 const tree opa = *((const tree *)pa);
2430 const tree opb = *((const tree *)pb);
2431 gimple opstmta = SSA_NAME_DEF_STMT (opa);
2432 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
2436 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
2438 else if (gimple_nop_p (opstmta))
2440 else if (gimple_nop_p (opstmtb))
2443 bba = gimple_bb (opstmta);
2444 bbb = gimple_bb (opstmtb);
2455 if (gimple_code (opstmta) == GIMPLE_PHI
2456 && gimple_code (opstmtb) == GIMPLE_PHI)
2458 else if (gimple_code (opstmta) == GIMPLE_PHI)
2460 else if (gimple_code (opstmtb) == GIMPLE_PHI)
2462 return gimple_uid (opstmta) - gimple_uid (opstmtb);
2464 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
2467 /* Sort an array containing members of a strongly connected component
2468 SCC so that the members are ordered by RPO number.
2469 This means that when the sort is complete, iterating through the
2470 array will give you the members in RPO order. */
2473 sort_scc (VEC (tree, heap) *scc)
2475 qsort (VEC_address (tree, scc),
2476 VEC_length (tree, scc),
2481 /* Process a strongly connected component in the SSA graph. */
2484 process_scc (VEC (tree, heap) *scc)
2486 /* If the SCC has a single member, just visit it. */
2488 if (VEC_length (tree, scc) == 1)
2490 tree use = VEC_index (tree, scc, 0);
2491 if (!VN_INFO (use)->use_processed)
2498 unsigned int iterations = 0;
2499 bool changed = true;
2501 /* Iterate over the SCC with the optimistic table until it stops
2503 current_info = optimistic_info;
2508 /* As we are value-numbering optimistically we have to
2509 clear the expression tables and the simplified expressions
2510 in each iteration until we converge. */
2511 htab_empty (optimistic_info->nary);
2512 htab_empty (optimistic_info->phis);
2513 htab_empty (optimistic_info->references);
2514 obstack_free (&optimistic_info->nary_obstack, NULL);
2515 gcc_obstack_init (&optimistic_info->nary_obstack);
2516 empty_alloc_pool (optimistic_info->phis_pool);
2517 empty_alloc_pool (optimistic_info->references_pool);
2518 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2519 VN_INFO (var)->expr = NULL_TREE;
2520 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2521 changed |= visit_use (var);
2524 statistics_histogram_event (cfun, "SCC iterations", iterations);
2526 /* Finally, visit the SCC once using the valid table. */
2527 current_info = valid_info;
2528 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2533 DEF_VEC_O(ssa_op_iter);
2534 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
2536 /* Pop the components of the found SCC for NAME off the SCC stack
2537 and process them. Returns true if all went well, false if
2538 we run into resource limits. */
2541 extract_and_process_scc_for_name (tree name)
2543 VEC (tree, heap) *scc = NULL;
2546 /* Found an SCC, pop the components off the SCC stack and
2550 x = VEC_pop (tree, sccstack);
2552 VN_INFO (x)->on_sccstack = false;
2553 VEC_safe_push (tree, heap, scc, x);
2554 } while (x != name);
2556 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2557 if (VEC_length (tree, scc)
2558 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
2561 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
2562 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
2563 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
2567 if (VEC_length (tree, scc) > 1)
2570 if (dump_file && (dump_flags & TDF_DETAILS))
2571 print_scc (dump_file, scc);
2575 VEC_free (tree, heap, scc);
2580 /* Depth first search on NAME to discover and process SCC's in the SSA
2582 Execution of this algorithm relies on the fact that the SCC's are
2583 popped off the stack in topological order.
2584 Returns true if successful, false if we stopped processing SCC's due
2585 to resource constraints. */
2590 VEC(ssa_op_iter, heap) *itervec = NULL;
2591 VEC(tree, heap) *namevec = NULL;
2592 use_operand_p usep = NULL;
2599 VN_INFO (name)->dfsnum = next_dfs_num++;
2600 VN_INFO (name)->visited = true;
2601 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
2603 VEC_safe_push (tree, heap, sccstack, name);
2604 VN_INFO (name)->on_sccstack = true;
2605 defstmt = SSA_NAME_DEF_STMT (name);
2607 /* Recursively DFS on our operands, looking for SCC's. */
2608 if (!gimple_nop_p (defstmt))
2610 /* Push a new iterator. */
2611 if (gimple_code (defstmt) == GIMPLE_PHI)
2612 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
2614 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
2621 /* If we are done processing uses of a name, go up the stack
2622 of iterators and process SCCs as we found them. */
2623 if (op_iter_done (&iter))
2625 /* See if we found an SCC. */
2626 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
2627 if (!extract_and_process_scc_for_name (name))
2629 VEC_free (tree, heap, namevec);
2630 VEC_free (ssa_op_iter, heap, itervec);
2634 /* Check if we are done. */
2635 if (VEC_empty (tree, namevec))
2637 VEC_free (tree, heap, namevec);
2638 VEC_free (ssa_op_iter, heap, itervec);
2642 /* Restore the last use walker and continue walking there. */
2644 name = VEC_pop (tree, namevec);
2645 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
2646 sizeof (ssa_op_iter));
2647 VEC_pop (ssa_op_iter, itervec);
2648 goto continue_walking;
2651 use = USE_FROM_PTR (usep);
2653 /* Since we handle phi nodes, we will sometimes get
2654 invariants in the use expression. */
2655 if (TREE_CODE (use) == SSA_NAME)
2657 if (! (VN_INFO (use)->visited))
2659 /* Recurse by pushing the current use walking state on
2660 the stack and starting over. */
2661 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
2662 VEC_safe_push(tree, heap, namevec, name);
2667 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
2668 VN_INFO (use)->low);
2670 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
2671 && VN_INFO (use)->on_sccstack)
2673 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
2674 VN_INFO (name)->low);
2678 usep = op_iter_next_use (&iter);
2682 /* Allocate a value number table. */
2685 allocate_vn_table (vn_tables_t table)
2687 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
2688 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
2689 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
2692 gcc_obstack_init (&table->nary_obstack);
2693 table->phis_pool = create_alloc_pool ("VN phis",
2694 sizeof (struct vn_phi_s),
2696 table->references_pool = create_alloc_pool ("VN references",
2697 sizeof (struct vn_reference_s),
2701 /* Free a value number table. */
2704 free_vn_table (vn_tables_t table)
2706 htab_delete (table->phis);
2707 htab_delete (table->nary);
2708 htab_delete (table->references);
2709 obstack_free (&table->nary_obstack, NULL);
2710 free_alloc_pool (table->phis_pool);
2711 free_alloc_pool (table->references_pool);
2719 int *rpo_numbers_temp;
2721 calculate_dominance_info (CDI_DOMINATORS);
2723 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
2726 constant_value_ids = BITMAP_ALLOC (NULL);
2731 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
2732 /* VEC_alloc doesn't actually grow it to the right size, it just
2733 preallocates the space to do so. */
2734 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
2735 gcc_obstack_init (&vn_ssa_aux_obstack);
2737 shared_lookup_phiargs = NULL;
2738 shared_lookup_vops = NULL;
2739 shared_lookup_references = NULL;
2740 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2741 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2742 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
2744 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
2745 the i'th block in RPO order is bb. We want to map bb's to RPO
2746 numbers, so we need to rearrange this array. */
2747 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
2748 rpo_numbers[rpo_numbers_temp[j]] = j;
2750 XDELETE (rpo_numbers_temp);
2752 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
2754 /* Create the VN_INFO structures, and initialize value numbers to
2756 for (i = 0; i < num_ssa_names; i++)
2758 tree name = ssa_name (i);
2761 VN_INFO_GET (name)->valnum = VN_TOP;
2762 VN_INFO (name)->expr = NULL_TREE;
2763 VN_INFO (name)->value_id = 0;
2767 renumber_gimple_stmt_uids ();
2769 /* Create the valid and optimistic value numbering tables. */
2770 valid_info = XCNEW (struct vn_tables_s);
2771 allocate_vn_table (valid_info);
2772 optimistic_info = XCNEW (struct vn_tables_s);
2773 allocate_vn_table (optimistic_info);
2781 htab_delete (constant_to_value_id);
2782 BITMAP_FREE (constant_value_ids);
2783 VEC_free (tree, heap, shared_lookup_phiargs);
2784 VEC_free (tree, gc, shared_lookup_vops);
2785 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
2786 XDELETEVEC (rpo_numbers);
2788 for (i = 0; i < num_ssa_names; i++)
2790 tree name = ssa_name (i);
2792 && VN_INFO (name)->needs_insertion)
2793 release_ssa_name (name);
2795 obstack_free (&vn_ssa_aux_obstack, NULL);
2796 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
2798 VEC_free (tree, heap, sccstack);
2799 free_vn_table (valid_info);
2800 XDELETE (valid_info);
2801 free_vn_table (optimistic_info);
2802 XDELETE (optimistic_info);
2805 /* Set the value ids in the valid hash tables. */
2808 set_hashtable_value_ids (void)
2815 /* Now set the value ids of the things we had put in the hash
2818 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
2819 vno, vn_nary_op_t, hi)
2823 if (TREE_CODE (vno->result) == SSA_NAME)
2824 vno->value_id = VN_INFO (vno->result)->value_id;
2825 else if (is_gimple_min_invariant (vno->result))
2826 vno->value_id = get_or_alloc_constant_value_id (vno->result);
2830 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
2835 if (TREE_CODE (vp->result) == SSA_NAME)
2836 vp->value_id = VN_INFO (vp->result)->value_id;
2837 else if (is_gimple_min_invariant (vp->result))
2838 vp->value_id = get_or_alloc_constant_value_id (vp->result);
2842 FOR_EACH_HTAB_ELEMENT (valid_info->references,
2843 vr, vn_reference_t, hi)
2847 if (TREE_CODE (vr->result) == SSA_NAME)
2848 vr->value_id = VN_INFO (vr->result)->value_id;
2849 else if (is_gimple_min_invariant (vr->result))
2850 vr->value_id = get_or_alloc_constant_value_id (vr->result);
2855 /* Do SCCVN. Returns true if it finished, false if we bailed out
2856 due to resource constraints. */
2859 run_scc_vn (bool may_insert_arg)
2863 bool changed = true;
2865 may_insert = may_insert_arg;
2868 current_info = valid_info;
2870 for (param = DECL_ARGUMENTS (current_function_decl);
2872 param = TREE_CHAIN (param))
2874 if (gimple_default_def (cfun, param) != NULL)
2876 tree def = gimple_default_def (cfun, param);
2877 SSA_VAL (def) = def;
2881 for (i = 1; i < num_ssa_names; ++i)
2883 tree name = ssa_name (i);
2885 && VN_INFO (name)->visited == false
2886 && !has_zero_uses (name))
2895 /* Initialize the value ids. */
2897 for (i = 1; i < num_ssa_names; ++i)
2899 tree name = ssa_name (i);
2903 info = VN_INFO (name);
2904 if (info->valnum == name)
2905 info->value_id = get_next_value_id ();
2906 else if (is_gimple_min_invariant (info->valnum))
2907 info->value_id = get_or_alloc_constant_value_id (info->valnum);
2910 /* Propagate until they stop changing. */
2914 for (i = 1; i < num_ssa_names; ++i)
2916 tree name = ssa_name (i);
2920 info = VN_INFO (name);
2921 if (TREE_CODE (info->valnum) == SSA_NAME
2922 && info->valnum != name
2923 && info->value_id != VN_INFO (info->valnum)->value_id)
2926 info->value_id = VN_INFO (info->valnum)->value_id;
2931 set_hashtable_value_ids ();
2933 if (dump_file && (dump_flags & TDF_DETAILS))
2935 fprintf (dump_file, "Value numbers:\n");
2936 for (i = 0; i < num_ssa_names; i++)
2938 tree name = ssa_name (i);
2940 && VN_INFO (name)->visited
2941 && SSA_VAL (name) != name)
2943 print_generic_expr (dump_file, name, 0);
2944 fprintf (dump_file, " = ");
2945 print_generic_expr (dump_file, SSA_VAL (name), 0);
2946 fprintf (dump_file, "\n");
2955 /* Return the maximum value id we have ever seen. */
2958 get_max_value_id (void)
2960 return next_value_id;
2963 /* Return the next unique value id. */
2966 get_next_value_id (void)
2968 return next_value_id++;
2972 /* Compare two expressions E1 and E2 and return true if they are equal. */
2975 expressions_equal_p (tree e1, tree e2)
2977 /* The obvious case. */
2981 /* If only one of them is null, they cannot be equal. */
2985 /* Recurse on elements of lists. */
2986 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
2990 for (lop1 = e1, lop2 = e2;
2992 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
2996 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
3002 /* Now perform the actual comparison. */
3003 if (TREE_CODE (e1) == TREE_CODE (e2)
3004 && operand_equal_p (e1, e2, OEP_PURE_SAME))
3010 /* Sort the VUSE array so that we can do equality comparisons
3011 quicker on two vuse vecs. */
3014 sort_vuses (VEC (tree,gc) *vuses)
3016 if (VEC_length (tree, vuses) > 1)
3017 qsort (VEC_address (tree, vuses),
3018 VEC_length (tree, vuses),
3023 /* Sort the VUSE array so that we can do equality comparisons
3024 quicker on two vuse vecs. */
3027 sort_vuses_heap (VEC (tree,heap) *vuses)
3029 if (VEC_length (tree, vuses) > 1)
3030 qsort (VEC_address (tree, vuses),
3031 VEC_length (tree, vuses),