1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
37 #include "tree-iterator.h"
39 #include "alloc-pool.h"
40 #include "tree-pass.h"
43 #include "langhooks.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-sccvn.h"
49 /* This algorithm is based on the SCC algorithm presented by Keith
50 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
51 (http://citeseer.ist.psu.edu/41805.html). In
52 straight line code, it is equivalent to a regular hash based value
53 numbering that is performed in reverse postorder.
55 For code with cycles, there are two alternatives, both of which
56 require keeping the hashtables separate from the actual list of
57 value numbers for SSA names.
59 1. Iterate value numbering in an RPO walk of the blocks, removing
60 all the entries from the hashtable after each iteration (but
61 keeping the SSA name->value number mapping between iterations).
62 Iterate until it does not change.
64 2. Perform value numbering as part of an SCC walk on the SSA graph,
65 iterating only the cycles in the SSA graph until they do not change
66 (using a separate, optimistic hashtable for value numbering the SCC
69 The second is not just faster in practice (because most SSA graph
70 cycles do not involve all the variables in the graph), it also has
73 One of these nice properties is that when we pop an SCC off the
74 stack, we are guaranteed to have processed all the operands coming from
75 *outside of that SCC*, so we do not need to do anything special to
76 ensure they have value numbers.
78 Another nice property is that the SCC walk is done as part of a DFS
79 of the SSA graph, which makes it easy to perform combining and
80 simplifying operations at the same time.
82 The code below is deliberately written in a way that makes it easy
83 to separate the SCC walk from the other work it does.
85 In order to propagate constants through the code, we track which
86 expressions contain constants, and use those while folding. In
87 theory, we could also track expressions whose value numbers are
88 replaced, in case we end up folding based on expression
91 In order to value number memory, we assign value numbers to vuses.
92 This enables us to note that, for example, stores to the same
93 address of the same value from the same starting memory states are
97 1. We can iterate only the changing portions of the SCC's, but
98 I have not seen an SCC big enough for this to be a win.
99 2. If you differentiate between phi nodes for loops and phi nodes
100 for if-then-else, you can properly consider phi nodes in different
101 blocks for equivalence.
102 3. We could value number vuses in more cases, particularly, whole
106 /* The set of hashtables and alloc_pool's for their items. */
108 typedef struct vn_tables_s
113 struct obstack nary_obstack;
114 alloc_pool phis_pool;
115 alloc_pool references_pool;
118 static htab_t constant_to_value_id;
119 static bitmap constant_value_ids;
122 /* Valid hashtables storing information we have proven to be
125 static vn_tables_t valid_info;
127 /* Optimistic hashtables storing information we are making assumptions about
128 during iterations. */
130 static vn_tables_t optimistic_info;
132 /* Pointer to the set of hashtables that is currently being used.
133 Should always point to either the optimistic_info, or the
136 static vn_tables_t current_info;
139 /* Reverse post order index for each basic block. */
141 static int *rpo_numbers;
143 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
145 /* This represents the top of the VN lattice, which is the universal
150 /* Unique counter for our value ids. */
152 static unsigned int next_value_id;
154 /* Next DFS number and the stack for strongly connected component
157 static unsigned int next_dfs_num;
158 static VEC (tree, heap) *sccstack;
160 static bool may_insert;
163 DEF_VEC_P(vn_ssa_aux_t);
164 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
166 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
167 are allocated on an obstack for locality reasons, and to free them
168 without looping over the VEC. */
170 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
171 static struct obstack vn_ssa_aux_obstack;
173 /* Return the value numbering information for a given SSA name. */
178 vn_ssa_aux_t res = VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
179 SSA_NAME_VERSION (name));
184 /* Set the value numbering info for a given SSA name to a given
188 VN_INFO_SET (tree name, vn_ssa_aux_t value)
190 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
191 SSA_NAME_VERSION (name), value);
194 /* Initialize the value numbering info for a given SSA name.
195 This should be called just once for every SSA name. */
198 VN_INFO_GET (tree name)
200 vn_ssa_aux_t newinfo;
202 newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
203 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
204 if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
205 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
206 SSA_NAME_VERSION (name) + 1);
207 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
208 SSA_NAME_VERSION (name), newinfo);
213 /* Get the representative expression for the SSA_NAME NAME. Returns
214 the representative SSA_NAME if there is no expression associated with it. */
217 vn_get_expr_for (tree name)
219 vn_ssa_aux_t vn = VN_INFO (name);
221 tree expr = NULL_TREE;
223 if (vn->valnum == VN_TOP)
226 /* If the value-number is a constant it is the representative
228 if (TREE_CODE (vn->valnum) != SSA_NAME)
231 /* Get to the information of the value of this SSA_NAME. */
232 vn = VN_INFO (vn->valnum);
234 /* If the value-number is a constant it is the representative
236 if (TREE_CODE (vn->valnum) != SSA_NAME)
239 /* Else if we have an expression, return it. */
240 if (vn->expr != NULL_TREE)
243 /* Otherwise use the defining statement to build the expression. */
244 def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
246 /* If the value number is a default-definition or a PHI result
248 if (gimple_nop_p (def_stmt)
249 || gimple_code (def_stmt) == GIMPLE_PHI)
252 if (!is_gimple_assign (def_stmt))
255 /* FIXME tuples. This is incomplete and likely will miss some
257 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)))
260 if (gimple_assign_rhs_code (def_stmt) == VIEW_CONVERT_EXPR
261 || gimple_assign_rhs_code (def_stmt) == REALPART_EXPR
262 || gimple_assign_rhs_code (def_stmt) == IMAGPART_EXPR)
263 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 if (vc1->hashcode != vc2->hashcode)
322 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
325 /* Hash table hash function for vn_constant_t. */
328 vn_constant_hash (const void *p1)
330 const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
331 return vc1->hashcode;
334 /* Lookup a value id for CONSTANT and return it. If it does not
338 get_constant_value_id (tree constant)
341 struct vn_constant_s vc;
343 vc.hashcode = vn_hash_constant_with_type (constant);
344 vc.constant = constant;
345 slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
346 vc.hashcode, NO_INSERT);
348 return ((vn_constant_t)*slot)->value_id;
352 /* Lookup a value id for CONSTANT, and if it does not exist, create a
353 new one and return it. If it does exist, return it. */
356 get_or_alloc_constant_value_id (tree constant)
359 vn_constant_t vc = XNEW (struct vn_constant_s);
361 vc->hashcode = vn_hash_constant_with_type (constant);
362 vc->constant = constant;
363 slot = htab_find_slot_with_hash (constant_to_value_id, vc,
364 vc->hashcode, INSERT);
368 return ((vn_constant_t)*slot)->value_id;
370 vc->value_id = get_next_value_id ();
372 bitmap_set_bit (constant_value_ids, vc->value_id);
376 /* Return true if V is a value id for a constant. */
379 value_id_constant_p (unsigned int v)
381 return bitmap_bit_p (constant_value_ids, v);
384 /* Compare two reference operands P1 and P2 for equality. Return true if
385 they are equal, and false otherwise. */
388 vn_reference_op_eq (const void *p1, const void *p2)
390 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
391 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
393 return vro1->opcode == vro2->opcode
394 && types_compatible_p (vro1->type, vro2->type)
395 && expressions_equal_p (vro1->op0, vro2->op0)
396 && expressions_equal_p (vro1->op1, vro2->op1)
397 && expressions_equal_p (vro1->op2, vro2->op2);
400 /* Compute the hash for a reference operand VRO1. */
403 vn_reference_op_compute_hash (const vn_reference_op_t vro1)
405 hashval_t result = 0;
407 result += iterative_hash_expr (vro1->op0, vro1->opcode);
409 result += iterative_hash_expr (vro1->op1, vro1->opcode);
411 result += iterative_hash_expr (vro1->op2, vro1->opcode);
415 /* Return the hashcode for a given reference operation P1. */
418 vn_reference_hash (const void *p1)
420 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
421 return vr1->hashcode;
424 /* Compute a hash for the reference operation VR1 and return it. */
427 vn_reference_compute_hash (const vn_reference_t vr1)
431 vn_reference_op_t vro;
433 result = iterative_hash_expr (vr1->vuse, 0);
434 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
435 result += vn_reference_op_compute_hash (vro);
440 /* Return true if reference operations P1 and P2 are equivalent. This
441 means they have the same set of operands and vuses. */
444 vn_reference_eq (const void *p1, const void *p2)
447 vn_reference_op_t vro;
449 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
450 const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
451 if (vr1->hashcode != vr2->hashcode)
454 /* Early out if this is not a hash collision. */
455 if (vr1->hashcode != vr2->hashcode)
458 /* The VOP needs to be the same. */
459 if (vr1->vuse != vr2->vuse)
462 /* If the operands are the same we are done. */
463 if (vr1->operands == vr2->operands)
466 /* We require that address operands be canonicalized in a way that
467 two memory references will have the same operands if they are
469 if (VEC_length (vn_reference_op_s, vr1->operands)
470 != VEC_length (vn_reference_op_s, vr2->operands))
473 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
474 if (!vn_reference_op_eq (VEC_index (vn_reference_op_s, vr2->operands, i),
481 /* Copy the operations present in load/store REF into RESULT, a vector of
482 vn_reference_op_s's. */
485 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
487 if (TREE_CODE (ref) == TARGET_MEM_REF)
489 vn_reference_op_s temp;
491 memset (&temp, 0, sizeof (temp));
492 /* We do not care for spurious type qualifications. */
493 temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
494 temp.opcode = TREE_CODE (ref);
495 temp.op0 = TMR_SYMBOL (ref) ? TMR_SYMBOL (ref) : TMR_BASE (ref);
496 temp.op1 = TMR_INDEX (ref);
497 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
499 memset (&temp, 0, sizeof (temp));
500 temp.type = NULL_TREE;
501 temp.opcode = TREE_CODE (ref);
502 temp.op0 = TMR_STEP (ref);
503 temp.op1 = TMR_OFFSET (ref);
504 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
508 /* For non-calls, store the information that makes up the address. */
512 vn_reference_op_s temp;
514 memset (&temp, 0, sizeof (temp));
515 /* We do not care for spurious type qualifications. */
516 temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
517 temp.opcode = TREE_CODE (ref);
521 case ALIGN_INDIRECT_REF:
523 /* The only operand is the address, which gets its own
524 vn_reference_op_s structure. */
526 case MISALIGNED_INDIRECT_REF:
527 temp.op0 = TREE_OPERAND (ref, 1);
530 /* Record bits and position. */
531 temp.op0 = TREE_OPERAND (ref, 1);
532 temp.op1 = TREE_OPERAND (ref, 2);
535 /* The field decl is enough to unambiguously specify the field,
536 a matching type is not necessary and a mismatching type
537 is always a spurious difference. */
538 temp.type = NULL_TREE;
539 /* If this is a reference to a union member, record the union
540 member size as operand. Do so only if we are doing
541 expression insertion (during FRE), as PRE currently gets
542 confused with this. */
544 && TREE_OPERAND (ref, 2) == NULL_TREE
545 && TREE_CODE (DECL_CONTEXT (TREE_OPERAND (ref, 1))) == UNION_TYPE
546 && integer_zerop (DECL_FIELD_OFFSET (TREE_OPERAND (ref, 1)))
547 && integer_zerop (DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1))))
548 temp.op0 = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)));
551 /* Record field as operand. */
552 temp.op0 = TREE_OPERAND (ref, 1);
553 temp.op1 = TREE_OPERAND (ref, 2);
556 case ARRAY_RANGE_REF:
558 /* Record index as operand. */
559 temp.op0 = TREE_OPERAND (ref, 1);
560 temp.op1 = TREE_OPERAND (ref, 2);
561 temp.op2 = TREE_OPERAND (ref, 3);
579 if (is_gimple_min_invariant (ref))
585 /* These are only interesting for their operands, their
586 existence, and their type. They will never be the last
587 ref in the chain of references (IE they require an
588 operand), so we don't have to put anything
589 for op* as it will be handled by the iteration */
592 case VIEW_CONVERT_EXPR:
597 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
599 if (REFERENCE_CLASS_P (ref)
600 || (TREE_CODE (ref) == ADDR_EXPR
601 && !is_gimple_min_invariant (ref)))
602 ref = TREE_OPERAND (ref, 0);
608 /* Re-create a reference tree from the reference ops OPS.
609 Returns NULL_TREE if the ops were not handled.
610 This routine needs to be kept in sync with copy_reference_ops_from_ref. */
613 get_ref_from_reference_ops (VEC(vn_reference_op_s, heap) *ops)
615 vn_reference_op_t op;
617 tree ref, *op0_p = &ref;
619 for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
626 case ALIGN_INDIRECT_REF:
628 *op0_p = build1 (op->opcode, op->type, NULL_TREE);
629 op0_p = &TREE_OPERAND (*op0_p, 0);
632 case MISALIGNED_INDIRECT_REF:
633 *op0_p = build2 (MISALIGNED_INDIRECT_REF, op->type,
635 op0_p = &TREE_OPERAND (*op0_p, 0);
639 *op0_p = build3 (BIT_FIELD_REF, op->type, NULL_TREE,
641 op0_p = &TREE_OPERAND (*op0_p, 0);
645 *op0_p = build3 (COMPONENT_REF, TREE_TYPE (op->op0), NULL_TREE,
647 op0_p = &TREE_OPERAND (*op0_p, 0);
650 case ARRAY_RANGE_REF:
652 *op0_p = build4 (op->opcode, op->type, NULL_TREE,
653 op->op0, op->op1, op->op2);
654 op0_p = &TREE_OPERAND (*op0_p, 0);
674 if (op->op0 != NULL_TREE)
676 gcc_assert (is_gimple_min_invariant (op->op0));
683 case VIEW_CONVERT_EXPR:
684 *op0_p = build1 (op->opcode, op->type, NULL_TREE);
685 op0_p = &TREE_OPERAND (*op0_p, 0);
696 /* Copy the operations present in load/store/call REF into RESULT, a vector of
697 vn_reference_op_s's. */
700 copy_reference_ops_from_call (gimple call,
701 VEC(vn_reference_op_s, heap) **result)
703 vn_reference_op_s temp;
706 /* Copy the type, opcode, function being called and static chain. */
707 memset (&temp, 0, sizeof (temp));
708 temp.type = gimple_call_return_type (call);
709 temp.opcode = CALL_EXPR;
710 temp.op0 = gimple_call_fn (call);
711 temp.op1 = gimple_call_chain (call);
712 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
714 /* Copy the call arguments. As they can be references as well,
715 just chain them together. */
716 for (i = 0; i < gimple_call_num_args (call); ++i)
718 tree callarg = gimple_call_arg (call, i);
719 copy_reference_ops_from_ref (callarg, result);
723 /* Create a vector of vn_reference_op_s structures from REF, a
724 REFERENCE_CLASS_P tree. The vector is not shared. */
726 static VEC(vn_reference_op_s, heap) *
727 create_reference_ops_from_ref (tree ref)
729 VEC (vn_reference_op_s, heap) *result = NULL;
731 copy_reference_ops_from_ref (ref, &result);
735 /* Create a vector of vn_reference_op_s structures from CALL, a
736 call statement. The vector is not shared. */
738 static VEC(vn_reference_op_s, heap) *
739 create_reference_ops_from_call (gimple call)
741 VEC (vn_reference_op_s, heap) *result = NULL;
743 copy_reference_ops_from_call (call, &result);
747 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
749 /* Create a vector of vn_reference_op_s structures from REF, a
750 REFERENCE_CLASS_P tree. The vector is shared among all callers of
753 static VEC(vn_reference_op_s, heap) *
754 shared_reference_ops_from_ref (tree ref)
758 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
759 copy_reference_ops_from_ref (ref, &shared_lookup_references);
760 return shared_lookup_references;
763 /* Create a vector of vn_reference_op_s structures from CALL, a
764 call statement. The vector is shared among all callers of
767 static VEC(vn_reference_op_s, heap) *
768 shared_reference_ops_from_call (gimple call)
772 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
773 copy_reference_ops_from_call (call, &shared_lookup_references);
774 return shared_lookup_references;
778 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
779 structures into their value numbers. This is done in-place, and
780 the vector passed in is returned. */
782 static VEC (vn_reference_op_s, heap) *
783 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
785 vn_reference_op_t vro;
788 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
790 if (vro->opcode == SSA_NAME
791 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
793 vro->op0 = SSA_VAL (vro->op0);
794 /* If it transforms from an SSA_NAME to a constant, update
796 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
797 vro->opcode = TREE_CODE (vro->op0);
799 /* TODO: Do we want to valueize op2 and op1 of
800 ARRAY_REF/COMPONENT_REF for Ada */
807 /* Lookup a SCCVN reference operation VR in the current hash table.
808 Returns the resulting value number if it exists in the hash table,
809 NULL_TREE otherwise. VNRESULT will be filled in with the actual
810 vn_reference_t stored in the hashtable if something is found. */
813 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
819 slot = htab_find_slot_with_hash (current_info->references, vr,
821 if (!slot && current_info == optimistic_info)
822 slot = htab_find_slot_with_hash (valid_info->references, vr,
827 *vnresult = (vn_reference_t)*slot;
828 return ((vn_reference_t)*slot)->result;
834 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
835 with the current VUSE and performs the expression lookup. */
838 vn_reference_lookup_2 (tree op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
840 vn_reference_t vr = (vn_reference_t)vr_;
844 /* Fixup vuse and hash. */
845 vr->hashcode = vr->hashcode - iterative_hash_expr (vr->vuse, 0);
846 vr->vuse = SSA_VAL (vuse);
847 vr->hashcode = vr->hashcode + iterative_hash_expr (vr->vuse, 0);
850 slot = htab_find_slot_with_hash (current_info->references, vr,
852 if (!slot && current_info == optimistic_info)
853 slot = htab_find_slot_with_hash (valid_info->references, vr,
861 /* Lookup a reference operation by it's parts, in the current hash table.
862 Returns the resulting value number if it exists in the hash table,
863 NULL_TREE otherwise. VNRESULT will be filled in with the actual
864 vn_reference_t stored in the hashtable if something is found. */
867 vn_reference_lookup_pieces (tree vuse,
868 VEC (vn_reference_op_s, heap) *operands,
869 vn_reference_t *vnresult, bool maywalk)
871 struct vn_reference_s vr1;
878 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
879 vr1.operands = valueize_refs (operands);
880 vr1.hashcode = vn_reference_compute_hash (&vr1);
881 vn_reference_lookup_1 (&vr1, vnresult);
887 tree ref = get_ref_from_reference_ops (operands);
891 (vn_reference_t)walk_non_aliased_vuses (ref, vr1.vuse,
892 vn_reference_lookup_2, &vr1);
896 return (*vnresult)->result;
901 /* Lookup OP in the current hash table, and return the resulting value
902 number if it exists in the hash table. Return NULL_TREE if it does
903 not exist in the hash table or if the result field of the structure
904 was NULL.. VNRESULT will be filled in with the vn_reference_t
905 stored in the hashtable if one exists. */
908 vn_reference_lookup (tree op, tree vuse, bool maywalk,
909 vn_reference_t *vnresult)
911 struct vn_reference_s vr1;
916 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
917 vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
918 vr1.hashcode = vn_reference_compute_hash (&vr1);
923 vn_reference_t wvnresult;
925 (vn_reference_t)walk_non_aliased_vuses (op, vr1.vuse,
926 vn_reference_lookup_2, &vr1);
930 *vnresult = wvnresult;
931 return wvnresult->result;
937 return vn_reference_lookup_1 (&vr1, vnresult);
941 /* Insert OP into the current hash table with a value number of
942 RESULT, and return the resulting reference structure we created. */
945 vn_reference_insert (tree op, tree result, tree vuse)
950 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
951 if (TREE_CODE (result) == SSA_NAME)
952 vr1->value_id = VN_INFO (result)->value_id;
954 vr1->value_id = get_or_alloc_constant_value_id (result);
955 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
956 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
957 vr1->hashcode = vn_reference_compute_hash (vr1);
958 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
960 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
963 /* Because we lookup stores using vuses, and value number failures
964 using the vdefs (see visit_reference_op_store for how and why),
965 it's possible that on failure we may try to insert an already
966 inserted store. This is not wrong, there is no ssa name for a
967 store that we could use as a differentiator anyway. Thus, unlike
968 the other lookup functions, you cannot gcc_assert (!*slot)
971 /* But free the old slot in case of a collision. */
973 free_reference (*slot);
979 /* Insert a reference by it's pieces into the current hash table with
980 a value number of RESULT. Return the resulting reference
981 structure we created. */
984 vn_reference_insert_pieces (tree vuse,
985 VEC (vn_reference_op_s, heap) *operands,
986 tree result, unsigned int value_id)
992 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
993 vr1->value_id = value_id;
994 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
995 vr1->operands = valueize_refs (operands);
996 vr1->hashcode = vn_reference_compute_hash (vr1);
997 if (result && TREE_CODE (result) == SSA_NAME)
998 result = SSA_VAL (result);
999 vr1->result = result;
1001 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1004 /* At this point we should have all the things inserted that we have
1005 seen before, and we should never try inserting something that
1007 gcc_assert (!*slot);
1009 free_reference (*slot);
1015 /* Compute and return the hash value for nary operation VBO1. */
1018 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1023 for (i = 0; i < vno1->length; ++i)
1024 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1025 vno1->op[i] = SSA_VAL (vno1->op[i]);
1027 if (vno1->length == 2
1028 && commutative_tree_code (vno1->opcode)
1029 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1031 tree temp = vno1->op[0];
1032 vno1->op[0] = vno1->op[1];
1036 for (i = 0; i < vno1->length; ++i)
1037 hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
1042 /* Return the computed hashcode for nary operation P1. */
1045 vn_nary_op_hash (const void *p1)
1047 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1048 return vno1->hashcode;
1051 /* Compare nary operations P1 and P2 and return true if they are
1055 vn_nary_op_eq (const void *p1, const void *p2)
1057 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1058 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1061 if (vno1->hashcode != vno2->hashcode)
1064 if (vno1->opcode != vno2->opcode
1065 || !types_compatible_p (vno1->type, vno2->type))
1068 for (i = 0; i < vno1->length; ++i)
1069 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1075 /* Lookup a n-ary operation by its pieces and return the resulting value
1076 number if it exists in the hash table. Return NULL_TREE if it does
1077 not exist in the hash table or if the result field of the operation
1078 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1082 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
1083 tree type, tree op0, tree op1, tree op2,
1084 tree op3, vn_nary_op_t *vnresult)
1087 struct vn_nary_op_s vno1;
1091 vno1.length = length;
1097 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1098 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1100 if (!slot && current_info == optimistic_info)
1101 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1106 *vnresult = (vn_nary_op_t)*slot;
1107 return ((vn_nary_op_t)*slot)->result;
1110 /* Lookup OP in the current hash table, and return the resulting value
1111 number if it exists in the hash table. Return NULL_TREE if it does
1112 not exist in the hash table or if the result field of the operation
1113 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1117 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
1120 struct vn_nary_op_s vno1;
1125 vno1.opcode = TREE_CODE (op);
1126 vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
1127 vno1.type = TREE_TYPE (op);
1128 for (i = 0; i < vno1.length; ++i)
1129 vno1.op[i] = TREE_OPERAND (op, i);
1130 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1131 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1133 if (!slot && current_info == optimistic_info)
1134 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1139 *vnresult = (vn_nary_op_t)*slot;
1140 return ((vn_nary_op_t)*slot)->result;
1143 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1144 value number if it exists in the hash table. Return NULL_TREE if
1145 it does not exist in the hash table. VNRESULT will contain the
1146 vn_nary_op_t from the hashtable if it exists. */
1149 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
1152 struct vn_nary_op_s vno1;
1157 vno1.opcode = gimple_assign_rhs_code (stmt);
1158 vno1.length = gimple_num_ops (stmt) - 1;
1159 vno1.type = TREE_TYPE (gimple_assign_lhs (stmt));
1160 for (i = 0; i < vno1.length; ++i)
1161 vno1.op[i] = gimple_op (stmt, i + 1);
1162 if (vno1.opcode == REALPART_EXPR
1163 || vno1.opcode == IMAGPART_EXPR
1164 || vno1.opcode == VIEW_CONVERT_EXPR)
1165 vno1.op[0] = TREE_OPERAND (vno1.op[0], 0);
1166 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1167 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1169 if (!slot && current_info == optimistic_info)
1170 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1175 *vnresult = (vn_nary_op_t)*slot;
1176 return ((vn_nary_op_t)*slot)->result;
1179 /* Insert a n-ary operation into the current hash table using it's
1180 pieces. Return the vn_nary_op_t structure we created and put in
1184 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
1185 tree type, tree op0,
1186 tree op1, tree op2, tree op3,
1188 unsigned int value_id)
1193 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1194 (sizeof (struct vn_nary_op_s)
1195 - sizeof (tree) * (4 - length)));
1196 vno1->value_id = value_id;
1197 vno1->opcode = code;
1198 vno1->length = length;
1208 vno1->result = result;
1209 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1210 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1212 gcc_assert (!*slot);
1219 /* Insert OP into the current hash table with a value number of
1220 RESULT. Return the vn_nary_op_t structure we created and put in
1224 vn_nary_op_insert (tree op, tree result)
1226 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
1231 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1232 (sizeof (struct vn_nary_op_s)
1233 - sizeof (tree) * (4 - length)));
1234 vno1->value_id = VN_INFO (result)->value_id;
1235 vno1->opcode = TREE_CODE (op);
1236 vno1->length = length;
1237 vno1->type = TREE_TYPE (op);
1238 for (i = 0; i < vno1->length; ++i)
1239 vno1->op[i] = TREE_OPERAND (op, i);
1240 vno1->result = result;
1241 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1242 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1244 gcc_assert (!*slot);
1250 /* Insert the rhs of STMT into the current hash table with a value number of
1254 vn_nary_op_insert_stmt (gimple stmt, tree result)
1256 unsigned length = gimple_num_ops (stmt) - 1;
1261 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1262 (sizeof (struct vn_nary_op_s)
1263 - sizeof (tree) * (4 - length)));
1264 vno1->value_id = VN_INFO (result)->value_id;
1265 vno1->opcode = gimple_assign_rhs_code (stmt);
1266 vno1->length = length;
1267 vno1->type = TREE_TYPE (gimple_assign_lhs (stmt));
1268 for (i = 0; i < vno1->length; ++i)
1269 vno1->op[i] = gimple_op (stmt, i + 1);
1270 if (vno1->opcode == REALPART_EXPR
1271 || vno1->opcode == IMAGPART_EXPR
1272 || vno1->opcode == VIEW_CONVERT_EXPR)
1273 vno1->op[0] = TREE_OPERAND (vno1->op[0], 0);
1274 vno1->result = result;
1275 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1276 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1278 gcc_assert (!*slot);
1284 /* Compute a hashcode for PHI operation VP1 and return it. */
1286 static inline hashval_t
1287 vn_phi_compute_hash (vn_phi_t vp1)
1289 hashval_t result = 0;
1294 result = vp1->block->index;
1296 /* If all PHI arguments are constants we need to distinguish
1297 the PHI node via its type. */
1298 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
1299 result += (INTEGRAL_TYPE_P (type)
1300 + (INTEGRAL_TYPE_P (type)
1301 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
1303 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1305 if (phi1op == VN_TOP)
1307 result += iterative_hash_expr (phi1op, result);
1313 /* Return the computed hashcode for phi operation P1. */
1316 vn_phi_hash (const void *p1)
1318 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1319 return vp1->hashcode;
1322 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1325 vn_phi_eq (const void *p1, const void *p2)
1327 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1328 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
1330 if (vp1->hashcode != vp2->hashcode)
1333 if (vp1->block == vp2->block)
1338 /* If the PHI nodes do not have compatible types
1339 they are not the same. */
1340 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
1341 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
1344 /* Any phi in the same block will have it's arguments in the
1345 same edge order, because of how we store phi nodes. */
1346 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1348 tree phi2op = VEC_index (tree, vp2->phiargs, i);
1349 if (phi1op == VN_TOP || phi2op == VN_TOP)
1351 if (!expressions_equal_p (phi1op, phi2op))
1359 static VEC(tree, heap) *shared_lookup_phiargs;
1361 /* Lookup PHI in the current hash table, and return the resulting
1362 value number if it exists in the hash table. Return NULL_TREE if
1363 it does not exist in the hash table. */
1366 vn_phi_lookup (gimple phi)
1369 struct vn_phi_s vp1;
1372 VEC_truncate (tree, shared_lookup_phiargs, 0);
1374 /* Canonicalize the SSA_NAME's to their value number. */
1375 for (i = 0; i < gimple_phi_num_args (phi); i++)
1377 tree def = PHI_ARG_DEF (phi, i);
1378 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1379 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
1381 vp1.phiargs = shared_lookup_phiargs;
1382 vp1.block = gimple_bb (phi);
1383 vp1.hashcode = vn_phi_compute_hash (&vp1);
1384 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
1386 if (!slot && current_info == optimistic_info)
1387 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
1391 return ((vn_phi_t)*slot)->result;
1394 /* Insert PHI into the current hash table with a value number of
1398 vn_phi_insert (gimple phi, tree result)
1401 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
1403 VEC (tree, heap) *args = NULL;
1405 /* Canonicalize the SSA_NAME's to their value number. */
1406 for (i = 0; i < gimple_phi_num_args (phi); i++)
1408 tree def = PHI_ARG_DEF (phi, i);
1409 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1410 VEC_safe_push (tree, heap, args, def);
1412 vp1->value_id = VN_INFO (result)->value_id;
1413 vp1->phiargs = args;
1414 vp1->block = gimple_bb (phi);
1415 vp1->result = result;
1416 vp1->hashcode = vn_phi_compute_hash (vp1);
1418 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
1421 /* Because we iterate over phi operations more than once, it's
1422 possible the slot might already exist here, hence no assert.*/
1428 /* Print set of components in strongly connected component SCC to OUT. */
1431 print_scc (FILE *out, VEC (tree, heap) *scc)
1436 fprintf (out, "SCC consists of: ");
1437 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1439 print_generic_expr (out, var, 0);
1442 fprintf (out, "\n");
1445 /* Set the value number of FROM to TO, return true if it has changed
1449 set_ssa_val_to (tree from, tree to)
1454 && TREE_CODE (to) == SSA_NAME
1455 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
1458 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1459 and invariants. So assert that here. */
1460 gcc_assert (to != NULL_TREE
1462 || TREE_CODE (to) == SSA_NAME
1463 || is_gimple_min_invariant (to)));
1465 if (dump_file && (dump_flags & TDF_DETAILS))
1467 fprintf (dump_file, "Setting value number of ");
1468 print_generic_expr (dump_file, from, 0);
1469 fprintf (dump_file, " to ");
1470 print_generic_expr (dump_file, to, 0);
1473 currval = SSA_VAL (from);
1475 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
1477 VN_INFO (from)->valnum = to;
1478 if (dump_file && (dump_flags & TDF_DETAILS))
1479 fprintf (dump_file, " (changed)\n");
1482 if (dump_file && (dump_flags & TDF_DETAILS))
1483 fprintf (dump_file, "\n");
1487 /* Set all definitions in STMT to value number to themselves.
1488 Return true if a value number changed. */
1491 defs_to_varying (gimple stmt)
1493 bool changed = false;
1497 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1499 tree def = DEF_FROM_PTR (defp);
1501 VN_INFO (def)->use_processed = true;
1502 changed |= set_ssa_val_to (def, def);
1507 static bool expr_has_constants (tree expr);
1508 static tree valueize_expr (tree expr);
1510 /* Visit a copy between LHS and RHS, return true if the value number
1514 visit_copy (tree lhs, tree rhs)
1516 /* Follow chains of copies to their destination. */
1517 while (TREE_CODE (rhs) == SSA_NAME
1518 && SSA_VAL (rhs) != rhs)
1519 rhs = SSA_VAL (rhs);
1521 /* The copy may have a more interesting constant filled expression
1522 (we don't, since we know our RHS is just an SSA name). */
1523 if (TREE_CODE (rhs) == SSA_NAME)
1525 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1526 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1529 return set_ssa_val_to (lhs, rhs);
1532 /* Visit a unary operator RHS, value number it, and return true if the
1533 value number of LHS has changed as a result. */
1536 visit_unary_op (tree lhs, gimple stmt)
1538 bool changed = false;
1539 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1543 changed = set_ssa_val_to (lhs, result);
1547 changed = set_ssa_val_to (lhs, lhs);
1548 vn_nary_op_insert_stmt (stmt, lhs);
1554 /* Visit a binary operator RHS, value number it, and return true if the
1555 value number of LHS has changed as a result. */
1558 visit_binary_op (tree lhs, gimple stmt)
1560 bool changed = false;
1561 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1565 changed = set_ssa_val_to (lhs, result);
1569 changed = set_ssa_val_to (lhs, lhs);
1570 vn_nary_op_insert_stmt (stmt, lhs);
1576 /* Visit a call STMT storing into LHS. Return true if the value number
1577 of the LHS has changed as a result. */
1580 visit_reference_op_call (tree lhs, gimple stmt)
1582 bool changed = false;
1583 struct vn_reference_s vr1;
1585 tree vuse = gimple_vuse (stmt);
1587 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1588 vr1.operands = valueize_refs (shared_reference_ops_from_call (stmt));
1589 vr1.hashcode = vn_reference_compute_hash (&vr1);
1590 result = vn_reference_lookup_1 (&vr1, NULL);
1593 changed = set_ssa_val_to (lhs, result);
1594 if (TREE_CODE (result) == SSA_NAME
1595 && VN_INFO (result)->has_constants)
1596 VN_INFO (lhs)->has_constants = true;
1602 changed = set_ssa_val_to (lhs, lhs);
1603 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
1604 vr2->vuse = vr1.vuse;
1605 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
1606 vr2->hashcode = vr1.hashcode;
1608 slot = htab_find_slot_with_hash (current_info->references,
1609 vr2, vr2->hashcode, INSERT);
1611 free_reference (*slot);
1618 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1619 and return true if the value number of the LHS has changed as a result. */
1622 visit_reference_op_load (tree lhs, tree op, gimple stmt)
1624 bool changed = false;
1625 tree result = vn_reference_lookup (op, gimple_vuse (stmt), true, NULL);
1627 /* We handle type-punning through unions by value-numbering based
1628 on offset and size of the access. Be prepared to handle a
1629 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1631 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
1633 /* We will be setting the value number of lhs to the value number
1634 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1635 So first simplify and lookup this expression to see if it
1636 is already available. */
1637 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
1638 if ((CONVERT_EXPR_P (val)
1639 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
1640 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
1642 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
1643 if ((CONVERT_EXPR_P (tem)
1644 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
1645 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
1646 TREE_TYPE (val), tem)))
1650 if (!is_gimple_min_invariant (val)
1651 && TREE_CODE (val) != SSA_NAME)
1652 result = vn_nary_op_lookup (val, NULL);
1653 /* If the expression is not yet available, value-number lhs to
1654 a new SSA_NAME we create. */
1655 if (!result && may_insert)
1657 result = make_ssa_name (SSA_NAME_VAR (lhs), NULL);
1658 /* Initialize value-number information properly. */
1659 VN_INFO_GET (result)->valnum = result;
1660 VN_INFO (result)->value_id = get_next_value_id ();
1661 VN_INFO (result)->expr = val;
1662 VN_INFO (result)->has_constants = expr_has_constants (val);
1663 VN_INFO (result)->needs_insertion = true;
1664 /* As all "inserted" statements are singleton SCCs, insert
1665 to the valid table. This is strictly needed to
1666 avoid re-generating new value SSA_NAMEs for the same
1667 expression during SCC iteration over and over (the
1668 optimistic table gets cleared after each iteration).
1669 We do not need to insert into the optimistic table, as
1670 lookups there will fall back to the valid table. */
1671 if (current_info == optimistic_info)
1673 current_info = valid_info;
1674 vn_nary_op_insert (val, result);
1675 current_info = optimistic_info;
1678 vn_nary_op_insert (val, result);
1679 if (dump_file && (dump_flags & TDF_DETAILS))
1681 fprintf (dump_file, "Inserting name ");
1682 print_generic_expr (dump_file, result, 0);
1683 fprintf (dump_file, " for expression ");
1684 print_generic_expr (dump_file, val, 0);
1685 fprintf (dump_file, "\n");
1692 changed = set_ssa_val_to (lhs, result);
1693 if (TREE_CODE (result) == SSA_NAME
1694 && VN_INFO (result)->has_constants)
1696 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
1697 VN_INFO (lhs)->has_constants = true;
1702 changed = set_ssa_val_to (lhs, lhs);
1703 vn_reference_insert (op, lhs, gimple_vuse (stmt));
1710 /* Visit a store to a reference operator LHS, 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_store (tree lhs, tree op, gimple stmt)
1716 bool changed = false;
1718 bool resultsame = false;
1720 /* First we want to lookup using the *vuses* from the store and see
1721 if there the last store to this location with the same address
1724 The vuses represent the memory state before the store. If the
1725 memory state, address, and value of the store is the same as the
1726 last store to this location, then this store will produce the
1727 same memory state as that store.
1729 In this case the vdef versions for this store are value numbered to those
1730 vuse versions, since they represent the same memory state after
1733 Otherwise, the vdefs for the store are used when inserting into
1734 the table, since the store generates a new memory state. */
1736 result = vn_reference_lookup (lhs, gimple_vuse (stmt), false, NULL);
1740 if (TREE_CODE (result) == SSA_NAME)
1741 result = SSA_VAL (result);
1742 if (TREE_CODE (op) == SSA_NAME)
1744 resultsame = expressions_equal_p (result, op);
1747 if (!result || !resultsame)
1751 if (dump_file && (dump_flags & TDF_DETAILS))
1753 fprintf (dump_file, "No store match\n");
1754 fprintf (dump_file, "Value numbering store ");
1755 print_generic_expr (dump_file, lhs, 0);
1756 fprintf (dump_file, " to ");
1757 print_generic_expr (dump_file, op, 0);
1758 fprintf (dump_file, "\n");
1760 /* Have to set value numbers before insert, since insert is
1761 going to valueize the references in-place. */
1762 if ((vdef = gimple_vdef (stmt)))
1764 VN_INFO (vdef)->use_processed = true;
1765 changed |= set_ssa_val_to (vdef, vdef);
1768 /* Do not insert structure copies into the tables. */
1769 if (is_gimple_min_invariant (op)
1770 || is_gimple_reg (op))
1771 vn_reference_insert (lhs, op, vdef);
1775 /* We had a match, so value number the vdef to have the value
1776 number of the vuse it came from. */
1779 if (dump_file && (dump_flags & TDF_DETAILS))
1780 fprintf (dump_file, "Store matched earlier value,"
1781 "value numbering store vdefs to matching vuses.\n");
1783 def = gimple_vdef (stmt);
1784 use = gimple_vuse (stmt);
1786 VN_INFO (def)->use_processed = true;
1787 changed |= set_ssa_val_to (def, SSA_VAL (use));
1793 /* Visit and value number PHI, return true if the value number
1797 visit_phi (gimple phi)
1799 bool changed = false;
1801 tree sameval = VN_TOP;
1802 bool allsame = true;
1805 /* TODO: We could check for this in init_sccvn, and replace this
1806 with a gcc_assert. */
1807 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
1808 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1810 /* See if all non-TOP arguments have the same value. TOP is
1811 equivalent to everything, so we can ignore it. */
1812 for (i = 0; i < gimple_phi_num_args (phi); i++)
1814 tree def = PHI_ARG_DEF (phi, i);
1816 if (TREE_CODE (def) == SSA_NAME)
1817 def = SSA_VAL (def);
1820 if (sameval == VN_TOP)
1826 if (!expressions_equal_p (def, sameval))
1834 /* If all value numbered to the same value, the phi node has that
1838 if (is_gimple_min_invariant (sameval))
1840 VN_INFO (PHI_RESULT (phi))->has_constants = true;
1841 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1845 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1846 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1849 if (TREE_CODE (sameval) == SSA_NAME)
1850 return visit_copy (PHI_RESULT (phi), sameval);
1852 return set_ssa_val_to (PHI_RESULT (phi), sameval);
1855 /* Otherwise, see if it is equivalent to a phi node in this block. */
1856 result = vn_phi_lookup (phi);
1859 if (TREE_CODE (result) == SSA_NAME)
1860 changed = visit_copy (PHI_RESULT (phi), result);
1862 changed = set_ssa_val_to (PHI_RESULT (phi), result);
1866 vn_phi_insert (phi, PHI_RESULT (phi));
1867 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1868 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1869 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1875 /* Return true if EXPR contains constants. */
1878 expr_has_constants (tree expr)
1880 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1883 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1886 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1887 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1888 /* Constants inside reference ops are rarely interesting, but
1889 it can take a lot of looking to find them. */
1891 case tcc_declaration:
1894 return is_gimple_min_invariant (expr);
1899 /* Return true if STMT contains constants. */
1902 stmt_has_constants (gimple stmt)
1904 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1907 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
1909 case GIMPLE_UNARY_RHS:
1910 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
1912 case GIMPLE_BINARY_RHS:
1913 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
1914 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
1915 case GIMPLE_SINGLE_RHS:
1916 /* Constants inside reference ops are rarely interesting, but
1917 it can take a lot of looking to find them. */
1918 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
1925 /* Replace SSA_NAMES in expr with their value numbers, and return the
1927 This is performed in place. */
1930 valueize_expr (tree expr)
1932 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1935 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1936 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1937 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1940 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1941 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1942 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1943 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
1944 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
1945 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
1953 /* Simplify the binary expression RHS, and return the result if
1957 simplify_binary_expression (gimple stmt)
1959 tree result = NULL_TREE;
1960 tree op0 = gimple_assign_rhs1 (stmt);
1961 tree op1 = gimple_assign_rhs2 (stmt);
1963 /* This will not catch every single case we could combine, but will
1964 catch those with constants. The goal here is to simultaneously
1965 combine constants between expressions, but avoid infinite
1966 expansion of expressions during simplification. */
1967 if (TREE_CODE (op0) == SSA_NAME)
1969 if (VN_INFO (op0)->has_constants
1970 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
1971 op0 = valueize_expr (vn_get_expr_for (op0));
1972 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
1973 op0 = SSA_VAL (op0);
1976 if (TREE_CODE (op1) == SSA_NAME)
1978 if (VN_INFO (op1)->has_constants)
1979 op1 = valueize_expr (vn_get_expr_for (op1));
1980 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
1981 op1 = SSA_VAL (op1);
1984 /* Avoid folding if nothing changed. */
1985 if (op0 == gimple_assign_rhs1 (stmt)
1986 && op1 == gimple_assign_rhs2 (stmt))
1989 fold_defer_overflow_warnings ();
1991 result = fold_binary (gimple_assign_rhs_code (stmt),
1992 TREE_TYPE (gimple_get_lhs (stmt)), op0, op1);
1994 STRIP_USELESS_TYPE_CONVERSION (result);
1996 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
1999 /* Make sure result is not a complex expression consisting
2000 of operators of operators (IE (a + b) + (a + c))
2001 Otherwise, we will end up with unbounded expressions if
2002 fold does anything at all. */
2003 if (result && valid_gimple_rhs_p (result))
2009 /* Simplify the unary expression RHS, and return the result if
2013 simplify_unary_expression (gimple stmt)
2015 tree result = NULL_TREE;
2016 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2018 /* We handle some tcc_reference codes here that are all
2019 GIMPLE_ASSIGN_SINGLE codes. */
2020 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2021 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2022 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2023 op0 = TREE_OPERAND (op0, 0);
2025 if (TREE_CODE (op0) != SSA_NAME)
2029 if (VN_INFO (op0)->has_constants)
2030 op0 = valueize_expr (vn_get_expr_for (op0));
2031 else if (gimple_assign_cast_p (stmt)
2032 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2033 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2034 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2036 /* We want to do tree-combining on conversion-like expressions.
2037 Make sure we feed only SSA_NAMEs or constants to fold though. */
2038 tree tem = valueize_expr (vn_get_expr_for (op0));
2039 if (UNARY_CLASS_P (tem)
2040 || BINARY_CLASS_P (tem)
2041 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2042 || TREE_CODE (tem) == SSA_NAME
2043 || is_gimple_min_invariant (tem))
2047 /* Avoid folding if nothing changed, but remember the expression. */
2048 if (op0 == orig_op0)
2051 result = fold_unary_ignore_overflow (gimple_assign_rhs_code (stmt),
2052 gimple_expr_type (stmt), op0);
2055 STRIP_USELESS_TYPE_CONVERSION (result);
2056 if (valid_gimple_rhs_p (result))
2063 /* Try to simplify RHS using equivalences and constant folding. */
2066 try_to_simplify (gimple stmt)
2070 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2071 in this case, there is no point in doing extra work. */
2072 if (gimple_assign_copy_p (stmt)
2073 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2076 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2078 case tcc_declaration:
2079 tem = get_symbol_constant_value (gimple_assign_rhs1 (stmt));
2085 /* Do not do full-blown reference lookup here, but simplify
2086 reads from constant aggregates. */
2087 tem = fold_const_aggregate_ref (gimple_assign_rhs1 (stmt));
2091 /* Fallthrough for some codes that can operate on registers. */
2092 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2093 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2094 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2096 /* We could do a little more with unary ops, if they expand
2097 into binary ops, but it's debatable whether it is worth it. */
2099 return simplify_unary_expression (stmt);
2101 case tcc_comparison:
2103 return simplify_binary_expression (stmt);
2112 /* Visit and value number USE, return true if the value number
2116 visit_use (tree use)
2118 bool changed = false;
2119 gimple stmt = SSA_NAME_DEF_STMT (use);
2121 VN_INFO (use)->use_processed = true;
2123 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
2124 if (dump_file && (dump_flags & TDF_DETAILS)
2125 && !SSA_NAME_IS_DEFAULT_DEF (use))
2127 fprintf (dump_file, "Value numbering ");
2128 print_generic_expr (dump_file, use, 0);
2129 fprintf (dump_file, " stmt = ");
2130 print_gimple_stmt (dump_file, stmt, 0, 0);
2133 /* Handle uninitialized uses. */
2134 if (SSA_NAME_IS_DEFAULT_DEF (use))
2135 changed = set_ssa_val_to (use, use);
2138 if (gimple_code (stmt) == GIMPLE_PHI)
2139 changed = visit_phi (stmt);
2140 else if (!gimple_has_lhs (stmt)
2141 || gimple_has_volatile_ops (stmt)
2142 || stmt_could_throw_p (stmt))
2143 changed = defs_to_varying (stmt);
2144 else if (is_gimple_assign (stmt))
2146 tree lhs = gimple_assign_lhs (stmt);
2149 /* Shortcut for copies. Simplifying copies is pointless,
2150 since we copy the expression and value they represent. */
2151 if (gimple_assign_copy_p (stmt)
2152 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2153 && TREE_CODE (lhs) == SSA_NAME)
2155 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
2158 simplified = try_to_simplify (stmt);
2161 if (dump_file && (dump_flags & TDF_DETAILS))
2163 fprintf (dump_file, "RHS ");
2164 print_gimple_expr (dump_file, stmt, 0, 0);
2165 fprintf (dump_file, " simplified to ");
2166 print_generic_expr (dump_file, simplified, 0);
2167 if (TREE_CODE (lhs) == SSA_NAME)
2168 fprintf (dump_file, " has constants %d\n",
2169 expr_has_constants (simplified));
2171 fprintf (dump_file, "\n");
2174 /* Setting value numbers to constants will occasionally
2175 screw up phi congruence because constants are not
2176 uniquely associated with a single ssa name that can be
2179 && is_gimple_min_invariant (simplified)
2180 && TREE_CODE (lhs) == SSA_NAME)
2182 VN_INFO (lhs)->expr = simplified;
2183 VN_INFO (lhs)->has_constants = true;
2184 changed = set_ssa_val_to (lhs, simplified);
2188 && TREE_CODE (simplified) == SSA_NAME
2189 && TREE_CODE (lhs) == SSA_NAME)
2191 changed = visit_copy (lhs, simplified);
2194 else if (simplified)
2196 if (TREE_CODE (lhs) == SSA_NAME)
2198 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
2199 /* We have to unshare the expression or else
2200 valuizing may change the IL stream. */
2201 VN_INFO (lhs)->expr = unshare_expr (simplified);
2204 else if (stmt_has_constants (stmt)
2205 && TREE_CODE (lhs) == SSA_NAME)
2206 VN_INFO (lhs)->has_constants = true;
2207 else if (TREE_CODE (lhs) == SSA_NAME)
2209 /* We reset expr and constantness here because we may
2210 have been value numbering optimistically, and
2211 iterating. They may become non-constant in this case,
2212 even if they were optimistically constant. */
2214 VN_INFO (lhs)->has_constants = false;
2215 VN_INFO (lhs)->expr = NULL_TREE;
2218 if ((TREE_CODE (lhs) == SSA_NAME
2219 /* We can substitute SSA_NAMEs that are live over
2220 abnormal edges with their constant value. */
2221 && !(gimple_assign_copy_p (stmt)
2222 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2224 && is_gimple_min_invariant (simplified))
2225 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2226 /* Stores or copies from SSA_NAMEs that are live over
2227 abnormal edges are a problem. */
2228 || (gimple_assign_single_p (stmt)
2229 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2230 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))))
2231 changed = defs_to_varying (stmt);
2232 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
2234 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
2236 else if (TREE_CODE (lhs) == SSA_NAME)
2238 if ((gimple_assign_copy_p (stmt)
2239 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2241 && is_gimple_min_invariant (simplified)))
2243 VN_INFO (lhs)->has_constants = true;
2245 changed = set_ssa_val_to (lhs, simplified);
2247 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
2251 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2253 case GIMPLE_UNARY_RHS:
2254 changed = visit_unary_op (lhs, stmt);
2256 case GIMPLE_BINARY_RHS:
2257 changed = visit_binary_op (lhs, stmt);
2259 case GIMPLE_SINGLE_RHS:
2260 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2263 /* VOP-less references can go through unary case. */
2264 if ((gimple_assign_rhs_code (stmt) == REALPART_EXPR
2265 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2266 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR )
2267 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (stmt), 0)) == SSA_NAME)
2269 changed = visit_unary_op (lhs, stmt);
2273 case tcc_declaration:
2274 changed = visit_reference_op_load
2275 (lhs, gimple_assign_rhs1 (stmt), stmt);
2277 case tcc_expression:
2278 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
2280 changed = visit_unary_op (lhs, stmt);
2285 changed = defs_to_varying (stmt);
2289 changed = defs_to_varying (stmt);
2295 changed = defs_to_varying (stmt);
2297 else if (is_gimple_call (stmt))
2299 tree lhs = gimple_call_lhs (stmt);
2301 /* ??? We could try to simplify calls. */
2303 if (stmt_has_constants (stmt)
2304 && TREE_CODE (lhs) == SSA_NAME)
2305 VN_INFO (lhs)->has_constants = true;
2306 else if (TREE_CODE (lhs) == SSA_NAME)
2308 /* We reset expr and constantness here because we may
2309 have been value numbering optimistically, and
2310 iterating. They may become non-constant in this case,
2311 even if they were optimistically constant. */
2312 VN_INFO (lhs)->has_constants = false;
2313 VN_INFO (lhs)->expr = NULL_TREE;
2316 if (TREE_CODE (lhs) == SSA_NAME
2317 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2318 changed = defs_to_varying (stmt);
2319 /* ??? We should handle stores from calls. */
2320 else if (TREE_CODE (lhs) == SSA_NAME)
2322 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2323 changed = visit_reference_op_call (lhs, stmt);
2325 changed = defs_to_varying (stmt);
2328 changed = defs_to_varying (stmt);
2335 /* Compare two operands by reverse postorder index */
2338 compare_ops (const void *pa, const void *pb)
2340 const tree opa = *((const tree *)pa);
2341 const tree opb = *((const tree *)pb);
2342 gimple opstmta = SSA_NAME_DEF_STMT (opa);
2343 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
2347 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
2349 else if (gimple_nop_p (opstmta))
2351 else if (gimple_nop_p (opstmtb))
2354 bba = gimple_bb (opstmta);
2355 bbb = gimple_bb (opstmtb);
2366 if (gimple_code (opstmta) == GIMPLE_PHI
2367 && gimple_code (opstmtb) == GIMPLE_PHI)
2369 else if (gimple_code (opstmta) == GIMPLE_PHI)
2371 else if (gimple_code (opstmtb) == GIMPLE_PHI)
2373 return gimple_uid (opstmta) - gimple_uid (opstmtb);
2375 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
2378 /* Sort an array containing members of a strongly connected component
2379 SCC so that the members are ordered by RPO number.
2380 This means that when the sort is complete, iterating through the
2381 array will give you the members in RPO order. */
2384 sort_scc (VEC (tree, heap) *scc)
2386 qsort (VEC_address (tree, scc),
2387 VEC_length (tree, scc),
2392 /* Process a strongly connected component in the SSA graph. */
2395 process_scc (VEC (tree, heap) *scc)
2397 /* If the SCC has a single member, just visit it. */
2399 if (VEC_length (tree, scc) == 1)
2401 tree use = VEC_index (tree, scc, 0);
2402 if (!VN_INFO (use)->use_processed)
2409 unsigned int iterations = 0;
2410 bool changed = true;
2412 /* Iterate over the SCC with the optimistic table until it stops
2414 current_info = optimistic_info;
2419 /* As we are value-numbering optimistically we have to
2420 clear the expression tables and the simplified expressions
2421 in each iteration until we converge. */
2422 htab_empty (optimistic_info->nary);
2423 htab_empty (optimistic_info->phis);
2424 htab_empty (optimistic_info->references);
2425 obstack_free (&optimistic_info->nary_obstack, NULL);
2426 gcc_obstack_init (&optimistic_info->nary_obstack);
2427 empty_alloc_pool (optimistic_info->phis_pool);
2428 empty_alloc_pool (optimistic_info->references_pool);
2429 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2430 VN_INFO (var)->expr = NULL_TREE;
2431 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2432 changed |= visit_use (var);
2435 statistics_histogram_event (cfun, "SCC iterations", iterations);
2437 /* Finally, visit the SCC once using the valid table. */
2438 current_info = valid_info;
2439 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2444 DEF_VEC_O(ssa_op_iter);
2445 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
2447 /* Pop the components of the found SCC for NAME off the SCC stack
2448 and process them. Returns true if all went well, false if
2449 we run into resource limits. */
2452 extract_and_process_scc_for_name (tree name)
2454 VEC (tree, heap) *scc = NULL;
2457 /* Found an SCC, pop the components off the SCC stack and
2461 x = VEC_pop (tree, sccstack);
2463 VN_INFO (x)->on_sccstack = false;
2464 VEC_safe_push (tree, heap, scc, x);
2465 } while (x != name);
2467 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2468 if (VEC_length (tree, scc)
2469 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
2472 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
2473 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
2474 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
2478 if (VEC_length (tree, scc) > 1)
2481 if (dump_file && (dump_flags & TDF_DETAILS))
2482 print_scc (dump_file, scc);
2486 VEC_free (tree, heap, scc);
2491 /* Depth first search on NAME to discover and process SCC's in the SSA
2493 Execution of this algorithm relies on the fact that the SCC's are
2494 popped off the stack in topological order.
2495 Returns true if successful, false if we stopped processing SCC's due
2496 to resource constraints. */
2501 VEC(ssa_op_iter, heap) *itervec = NULL;
2502 VEC(tree, heap) *namevec = NULL;
2503 use_operand_p usep = NULL;
2510 VN_INFO (name)->dfsnum = next_dfs_num++;
2511 VN_INFO (name)->visited = true;
2512 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
2514 VEC_safe_push (tree, heap, sccstack, name);
2515 VN_INFO (name)->on_sccstack = true;
2516 defstmt = SSA_NAME_DEF_STMT (name);
2518 /* Recursively DFS on our operands, looking for SCC's. */
2519 if (!gimple_nop_p (defstmt))
2521 /* Push a new iterator. */
2522 if (gimple_code (defstmt) == GIMPLE_PHI)
2523 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
2525 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
2528 clear_and_done_ssa_iter (&iter);
2532 /* If we are done processing uses of a name, go up the stack
2533 of iterators and process SCCs as we found them. */
2534 if (op_iter_done (&iter))
2536 /* See if we found an SCC. */
2537 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
2538 if (!extract_and_process_scc_for_name (name))
2540 VEC_free (tree, heap, namevec);
2541 VEC_free (ssa_op_iter, heap, itervec);
2545 /* Check if we are done. */
2546 if (VEC_empty (tree, namevec))
2548 VEC_free (tree, heap, namevec);
2549 VEC_free (ssa_op_iter, heap, itervec);
2553 /* Restore the last use walker and continue walking there. */
2555 name = VEC_pop (tree, namevec);
2556 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
2557 sizeof (ssa_op_iter));
2558 VEC_pop (ssa_op_iter, itervec);
2559 goto continue_walking;
2562 use = USE_FROM_PTR (usep);
2564 /* Since we handle phi nodes, we will sometimes get
2565 invariants in the use expression. */
2566 if (TREE_CODE (use) == SSA_NAME)
2568 if (! (VN_INFO (use)->visited))
2570 /* Recurse by pushing the current use walking state on
2571 the stack and starting over. */
2572 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
2573 VEC_safe_push(tree, heap, namevec, name);
2578 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
2579 VN_INFO (use)->low);
2581 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
2582 && VN_INFO (use)->on_sccstack)
2584 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
2585 VN_INFO (name)->low);
2589 usep = op_iter_next_use (&iter);
2593 /* Allocate a value number table. */
2596 allocate_vn_table (vn_tables_t table)
2598 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
2599 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
2600 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
2603 gcc_obstack_init (&table->nary_obstack);
2604 table->phis_pool = create_alloc_pool ("VN phis",
2605 sizeof (struct vn_phi_s),
2607 table->references_pool = create_alloc_pool ("VN references",
2608 sizeof (struct vn_reference_s),
2612 /* Free a value number table. */
2615 free_vn_table (vn_tables_t table)
2617 htab_delete (table->phis);
2618 htab_delete (table->nary);
2619 htab_delete (table->references);
2620 obstack_free (&table->nary_obstack, NULL);
2621 free_alloc_pool (table->phis_pool);
2622 free_alloc_pool (table->references_pool);
2630 int *rpo_numbers_temp;
2632 calculate_dominance_info (CDI_DOMINATORS);
2634 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
2637 constant_value_ids = BITMAP_ALLOC (NULL);
2642 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
2643 /* VEC_alloc doesn't actually grow it to the right size, it just
2644 preallocates the space to do so. */
2645 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
2646 gcc_obstack_init (&vn_ssa_aux_obstack);
2648 shared_lookup_phiargs = NULL;
2649 shared_lookup_references = NULL;
2650 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2651 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2652 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
2654 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
2655 the i'th block in RPO order is bb. We want to map bb's to RPO
2656 numbers, so we need to rearrange this array. */
2657 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
2658 rpo_numbers[rpo_numbers_temp[j]] = j;
2660 XDELETE (rpo_numbers_temp);
2662 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
2664 /* Create the VN_INFO structures, and initialize value numbers to
2666 for (i = 0; i < num_ssa_names; i++)
2668 tree name = ssa_name (i);
2671 VN_INFO_GET (name)->valnum = VN_TOP;
2672 VN_INFO (name)->expr = NULL_TREE;
2673 VN_INFO (name)->value_id = 0;
2677 renumber_gimple_stmt_uids ();
2679 /* Create the valid and optimistic value numbering tables. */
2680 valid_info = XCNEW (struct vn_tables_s);
2681 allocate_vn_table (valid_info);
2682 optimistic_info = XCNEW (struct vn_tables_s);
2683 allocate_vn_table (optimistic_info);
2691 htab_delete (constant_to_value_id);
2692 BITMAP_FREE (constant_value_ids);
2693 VEC_free (tree, heap, shared_lookup_phiargs);
2694 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
2695 XDELETEVEC (rpo_numbers);
2697 for (i = 0; i < num_ssa_names; i++)
2699 tree name = ssa_name (i);
2701 && VN_INFO (name)->needs_insertion)
2702 release_ssa_name (name);
2704 obstack_free (&vn_ssa_aux_obstack, NULL);
2705 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
2707 VEC_free (tree, heap, sccstack);
2708 free_vn_table (valid_info);
2709 XDELETE (valid_info);
2710 free_vn_table (optimistic_info);
2711 XDELETE (optimistic_info);
2714 /* Set the value ids in the valid hash tables. */
2717 set_hashtable_value_ids (void)
2724 /* Now set the value ids of the things we had put in the hash
2727 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
2728 vno, vn_nary_op_t, hi)
2732 if (TREE_CODE (vno->result) == SSA_NAME)
2733 vno->value_id = VN_INFO (vno->result)->value_id;
2734 else if (is_gimple_min_invariant (vno->result))
2735 vno->value_id = get_or_alloc_constant_value_id (vno->result);
2739 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
2744 if (TREE_CODE (vp->result) == SSA_NAME)
2745 vp->value_id = VN_INFO (vp->result)->value_id;
2746 else if (is_gimple_min_invariant (vp->result))
2747 vp->value_id = get_or_alloc_constant_value_id (vp->result);
2751 FOR_EACH_HTAB_ELEMENT (valid_info->references,
2752 vr, vn_reference_t, hi)
2756 if (TREE_CODE (vr->result) == SSA_NAME)
2757 vr->value_id = VN_INFO (vr->result)->value_id;
2758 else if (is_gimple_min_invariant (vr->result))
2759 vr->value_id = get_or_alloc_constant_value_id (vr->result);
2764 /* Do SCCVN. Returns true if it finished, false if we bailed out
2765 due to resource constraints. */
2768 run_scc_vn (bool may_insert_arg)
2772 bool changed = true;
2774 may_insert = may_insert_arg;
2777 current_info = valid_info;
2779 for (param = DECL_ARGUMENTS (current_function_decl);
2781 param = TREE_CHAIN (param))
2783 if (gimple_default_def (cfun, param) != NULL)
2785 tree def = gimple_default_def (cfun, param);
2786 VN_INFO (def)->valnum = def;
2790 for (i = 1; i < num_ssa_names; ++i)
2792 tree name = ssa_name (i);
2794 && VN_INFO (name)->visited == false
2795 && !has_zero_uses (name))
2804 /* Initialize the value ids. */
2806 for (i = 1; i < num_ssa_names; ++i)
2808 tree name = ssa_name (i);
2812 info = VN_INFO (name);
2813 if (info->valnum == name)
2814 info->value_id = get_next_value_id ();
2815 else if (is_gimple_min_invariant (info->valnum))
2816 info->value_id = get_or_alloc_constant_value_id (info->valnum);
2819 /* Propagate until they stop changing. */
2823 for (i = 1; i < num_ssa_names; ++i)
2825 tree name = ssa_name (i);
2829 info = VN_INFO (name);
2830 if (TREE_CODE (info->valnum) == SSA_NAME
2831 && info->valnum != name
2832 && info->value_id != VN_INFO (info->valnum)->value_id)
2835 info->value_id = VN_INFO (info->valnum)->value_id;
2840 set_hashtable_value_ids ();
2842 if (dump_file && (dump_flags & TDF_DETAILS))
2844 fprintf (dump_file, "Value numbers:\n");
2845 for (i = 0; i < num_ssa_names; i++)
2847 tree name = ssa_name (i);
2849 && VN_INFO (name)->visited
2850 && SSA_VAL (name) != name)
2852 print_generic_expr (dump_file, name, 0);
2853 fprintf (dump_file, " = ");
2854 print_generic_expr (dump_file, SSA_VAL (name), 0);
2855 fprintf (dump_file, "\n");
2864 /* Return the maximum value id we have ever seen. */
2867 get_max_value_id (void)
2869 return next_value_id;
2872 /* Return the next unique value id. */
2875 get_next_value_id (void)
2877 return next_value_id++;
2881 /* Compare two expressions E1 and E2 and return true if they are equal. */
2884 expressions_equal_p (tree e1, tree e2)
2886 /* The obvious case. */
2890 /* If only one of them is null, they cannot be equal. */
2894 /* Recurse on elements of lists. */
2895 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
2899 for (lop1 = e1, lop2 = e2;
2901 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
2905 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
2911 /* Now perform the actual comparison. */
2912 if (TREE_CODE (e1) == TREE_CODE (e2)
2913 && operand_equal_p (e1, e2, OEP_PURE_SAME))
2920 /* Return true if the nary operation NARY may trap. This is a copy
2921 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
2924 vn_nary_may_trap (vn_nary_op_t nary)
2928 bool honor_nans = false;
2929 bool honor_snans = false;
2930 bool fp_operation = false;
2931 bool honor_trapv = false;
2935 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
2936 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
2937 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
2940 fp_operation = FLOAT_TYPE_P (type);
2943 honor_nans = flag_trapping_math && !flag_finite_math_only;
2944 honor_snans = flag_signaling_nans != 0;
2946 else if (INTEGRAL_TYPE_P (type)
2947 && TYPE_OVERFLOW_TRAPS (type))
2951 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
2953 honor_nans, honor_snans, rhs2,
2959 for (i = 0; i < nary->length; ++i)
2960 if (tree_could_trap_p (nary->op[i]))