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 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
748 *I_P to point to the last element of the replacement. */
750 vn_reference_fold_indirect (VEC (vn_reference_op_s, heap) **ops,
753 VEC(vn_reference_op_s, heap) *mem = NULL;
754 vn_reference_op_t op;
755 unsigned int i = *i_p;
758 /* Get ops for the addressed object. */
759 op = VEC_index (vn_reference_op_s, *ops, i);
760 /* ??? If this is our usual typeof &ARRAY vs. &ARRAY[0] problem, work
761 around it to avoid later ICEs. */
762 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op->op0, 0))) == ARRAY_TYPE
763 && TREE_CODE (TREE_TYPE (TREE_TYPE (op->op0))) != ARRAY_TYPE)
765 vn_reference_op_s aref;
767 aref.type = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (op->op0)));
768 aref.opcode = ARRAY_REF;
769 aref.op0 = integer_zero_node;
770 if ((dom = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (op->op0, 0))))
771 && TYPE_MIN_VALUE (dom))
772 aref.op0 = TYPE_MIN_VALUE (dom);
773 aref.op1 = NULL_TREE;
774 aref.op2 = NULL_TREE;
775 VEC_safe_push (vn_reference_op_s, heap, mem, &aref);
777 copy_reference_ops_from_ref (TREE_OPERAND (op->op0, 0), &mem);
779 /* Do the replacement - we should have at least one op in mem now. */
780 if (VEC_length (vn_reference_op_s, mem) == 1)
782 VEC_replace (vn_reference_op_s, *ops, i - 1,
783 VEC_index (vn_reference_op_s, mem, 0));
784 VEC_ordered_remove (vn_reference_op_s, *ops, i);
787 else if (VEC_length (vn_reference_op_s, mem) == 2)
789 VEC_replace (vn_reference_op_s, *ops, i - 1,
790 VEC_index (vn_reference_op_s, mem, 0));
791 VEC_replace (vn_reference_op_s, *ops, i,
792 VEC_index (vn_reference_op_s, mem, 1));
794 else if (VEC_length (vn_reference_op_s, mem) > 2)
796 VEC_replace (vn_reference_op_s, *ops, i - 1,
797 VEC_index (vn_reference_op_s, mem, 0));
798 VEC_replace (vn_reference_op_s, *ops, i,
799 VEC_index (vn_reference_op_s, mem, 1));
800 /* ??? There is no VEC_splice. */
801 for (j = 2; VEC_iterate (vn_reference_op_s, mem, j, op); j++)
802 VEC_safe_insert (vn_reference_op_s, heap, *ops, ++i, op);
807 VEC_free (vn_reference_op_s, heap, mem);
811 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
812 structures into their value numbers. This is done in-place, and
813 the vector passed in is returned. */
815 static VEC (vn_reference_op_s, heap) *
816 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
818 vn_reference_op_t vro;
821 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
823 if (vro->opcode == SSA_NAME
824 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
826 vro->op0 = SSA_VAL (vro->op0);
827 /* If it transforms from an SSA_NAME to a constant, update
829 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
830 vro->opcode = TREE_CODE (vro->op0);
831 /* If it transforms from an SSA_NAME to an address, fold with
832 a preceding indirect reference. */
833 if (i > 0 && TREE_CODE (vro->op0) == ADDR_EXPR
834 && VEC_index (vn_reference_op_s,
835 orig, i - 1)->opcode == INDIRECT_REF)
837 vn_reference_fold_indirect (&orig, &i);
841 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
842 vro->op1 = SSA_VAL (vro->op1);
843 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
844 vro->op2 = SSA_VAL (vro->op2);
850 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
852 /* Create a vector of vn_reference_op_s structures from REF, a
853 REFERENCE_CLASS_P tree. The vector is shared among all callers of
856 static VEC(vn_reference_op_s, heap) *
857 valueize_shared_reference_ops_from_ref (tree ref)
861 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
862 copy_reference_ops_from_ref (ref, &shared_lookup_references);
863 shared_lookup_references = valueize_refs (shared_lookup_references);
864 return shared_lookup_references;
867 /* Create a vector of vn_reference_op_s structures from CALL, a
868 call statement. The vector is shared among all callers of
871 static VEC(vn_reference_op_s, heap) *
872 valueize_shared_reference_ops_from_call (gimple call)
876 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
877 copy_reference_ops_from_call (call, &shared_lookup_references);
878 shared_lookup_references = valueize_refs (shared_lookup_references);
879 return shared_lookup_references;
882 /* Lookup a SCCVN reference operation VR in the current hash table.
883 Returns the resulting value number if it exists in the hash table,
884 NULL_TREE otherwise. VNRESULT will be filled in with the actual
885 vn_reference_t stored in the hashtable if something is found. */
888 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
894 slot = htab_find_slot_with_hash (current_info->references, vr,
896 if (!slot && current_info == optimistic_info)
897 slot = htab_find_slot_with_hash (valid_info->references, vr,
902 *vnresult = (vn_reference_t)*slot;
903 return ((vn_reference_t)*slot)->result;
909 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
910 with the current VUSE and performs the expression lookup. */
913 vn_reference_lookup_2 (tree op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
915 vn_reference_t vr = (vn_reference_t)vr_;
919 /* Fixup vuse and hash. */
920 vr->hashcode = vr->hashcode - iterative_hash_expr (vr->vuse, 0);
921 vr->vuse = SSA_VAL (vuse);
922 vr->hashcode = vr->hashcode + iterative_hash_expr (vr->vuse, 0);
925 slot = htab_find_slot_with_hash (current_info->references, vr,
927 if (!slot && current_info == optimistic_info)
928 slot = htab_find_slot_with_hash (valid_info->references, vr,
936 /* Lookup a reference operation by it's parts, in the current hash table.
937 Returns the resulting value number if it exists in the hash table,
938 NULL_TREE otherwise. VNRESULT will be filled in with the actual
939 vn_reference_t stored in the hashtable if something is found. */
942 vn_reference_lookup_pieces (tree vuse,
943 VEC (vn_reference_op_s, heap) *operands,
944 vn_reference_t *vnresult, bool maywalk)
946 struct vn_reference_s vr1;
953 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
954 vr1.operands = valueize_refs (operands);
955 vr1.hashcode = vn_reference_compute_hash (&vr1);
956 vn_reference_lookup_1 (&vr1, vnresult);
962 tree ref = get_ref_from_reference_ops (operands);
966 (vn_reference_t)walk_non_aliased_vuses (ref, vr1.vuse,
967 vn_reference_lookup_2, &vr1);
971 return (*vnresult)->result;
976 /* Lookup OP in the current hash table, and return the resulting value
977 number if it exists in the hash table. Return NULL_TREE if it does
978 not exist in the hash table or if the result field of the structure
979 was NULL.. VNRESULT will be filled in with the vn_reference_t
980 stored in the hashtable if one exists. */
983 vn_reference_lookup (tree op, tree vuse, bool maywalk,
984 vn_reference_t *vnresult)
986 struct vn_reference_s vr1;
991 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
992 vr1.operands = valueize_shared_reference_ops_from_ref (op);
993 vr1.hashcode = vn_reference_compute_hash (&vr1);
998 vn_reference_t wvnresult;
1000 (vn_reference_t)walk_non_aliased_vuses (op, vr1.vuse,
1001 vn_reference_lookup_2, &vr1);
1005 *vnresult = wvnresult;
1006 return wvnresult->result;
1012 return vn_reference_lookup_1 (&vr1, vnresult);
1016 /* Insert OP into the current hash table with a value number of
1017 RESULT, and return the resulting reference structure we created. */
1020 vn_reference_insert (tree op, tree result, tree vuse)
1025 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1026 if (TREE_CODE (result) == SSA_NAME)
1027 vr1->value_id = VN_INFO (result)->value_id;
1029 vr1->value_id = get_or_alloc_constant_value_id (result);
1030 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1031 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1032 vr1->hashcode = vn_reference_compute_hash (vr1);
1033 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1035 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1038 /* Because we lookup stores using vuses, and value number failures
1039 using the vdefs (see visit_reference_op_store for how and why),
1040 it's possible that on failure we may try to insert an already
1041 inserted store. This is not wrong, there is no ssa name for a
1042 store that we could use as a differentiator anyway. Thus, unlike
1043 the other lookup functions, you cannot gcc_assert (!*slot)
1046 /* But free the old slot in case of a collision. */
1048 free_reference (*slot);
1054 /* Insert a reference by it's pieces into the current hash table with
1055 a value number of RESULT. Return the resulting reference
1056 structure we created. */
1059 vn_reference_insert_pieces (tree vuse,
1060 VEC (vn_reference_op_s, heap) *operands,
1061 tree result, unsigned int value_id)
1067 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1068 vr1->value_id = value_id;
1069 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1070 vr1->operands = valueize_refs (operands);
1071 vr1->hashcode = vn_reference_compute_hash (vr1);
1072 if (result && TREE_CODE (result) == SSA_NAME)
1073 result = SSA_VAL (result);
1074 vr1->result = result;
1076 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1079 /* At this point we should have all the things inserted that we have
1080 seen before, and we should never try inserting something that
1082 gcc_assert (!*slot);
1084 free_reference (*slot);
1090 /* Compute and return the hash value for nary operation VBO1. */
1093 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1098 for (i = 0; i < vno1->length; ++i)
1099 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1100 vno1->op[i] = SSA_VAL (vno1->op[i]);
1102 if (vno1->length == 2
1103 && commutative_tree_code (vno1->opcode)
1104 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1106 tree temp = vno1->op[0];
1107 vno1->op[0] = vno1->op[1];
1111 for (i = 0; i < vno1->length; ++i)
1112 hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
1117 /* Return the computed hashcode for nary operation P1. */
1120 vn_nary_op_hash (const void *p1)
1122 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1123 return vno1->hashcode;
1126 /* Compare nary operations P1 and P2 and return true if they are
1130 vn_nary_op_eq (const void *p1, const void *p2)
1132 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1133 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1136 if (vno1->hashcode != vno2->hashcode)
1139 if (vno1->opcode != vno2->opcode
1140 || !types_compatible_p (vno1->type, vno2->type))
1143 for (i = 0; i < vno1->length; ++i)
1144 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1150 /* Lookup a n-ary operation by its pieces and return the resulting value
1151 number if it exists in the hash table. Return NULL_TREE if it does
1152 not exist in the hash table or if the result field of the operation
1153 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1157 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
1158 tree type, tree op0, tree op1, tree op2,
1159 tree op3, vn_nary_op_t *vnresult)
1162 struct vn_nary_op_s vno1;
1166 vno1.length = length;
1172 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1173 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1175 if (!slot && current_info == optimistic_info)
1176 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1181 *vnresult = (vn_nary_op_t)*slot;
1182 return ((vn_nary_op_t)*slot)->result;
1185 /* Lookup OP in the current hash table, and return the resulting value
1186 number if it exists in the hash table. Return NULL_TREE if it does
1187 not exist in the hash table or if the result field of the operation
1188 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1192 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
1195 struct vn_nary_op_s vno1;
1200 vno1.opcode = TREE_CODE (op);
1201 vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
1202 vno1.type = TREE_TYPE (op);
1203 for (i = 0; i < vno1.length; ++i)
1204 vno1.op[i] = TREE_OPERAND (op, i);
1205 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1206 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1208 if (!slot && current_info == optimistic_info)
1209 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1214 *vnresult = (vn_nary_op_t)*slot;
1215 return ((vn_nary_op_t)*slot)->result;
1218 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1219 value number if it exists in the hash table. Return NULL_TREE if
1220 it does not exist in the hash table. VNRESULT will contain the
1221 vn_nary_op_t from the hashtable if it exists. */
1224 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
1227 struct vn_nary_op_s vno1;
1232 vno1.opcode = gimple_assign_rhs_code (stmt);
1233 vno1.length = gimple_num_ops (stmt) - 1;
1234 vno1.type = TREE_TYPE (gimple_assign_lhs (stmt));
1235 for (i = 0; i < vno1.length; ++i)
1236 vno1.op[i] = gimple_op (stmt, i + 1);
1237 if (vno1.opcode == REALPART_EXPR
1238 || vno1.opcode == IMAGPART_EXPR
1239 || vno1.opcode == VIEW_CONVERT_EXPR)
1240 vno1.op[0] = TREE_OPERAND (vno1.op[0], 0);
1241 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1242 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1244 if (!slot && current_info == optimistic_info)
1245 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1250 *vnresult = (vn_nary_op_t)*slot;
1251 return ((vn_nary_op_t)*slot)->result;
1254 /* Insert a n-ary operation into the current hash table using it's
1255 pieces. Return the vn_nary_op_t structure we created and put in
1259 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
1260 tree type, tree op0,
1261 tree op1, tree op2, tree op3,
1263 unsigned int value_id)
1268 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1269 (sizeof (struct vn_nary_op_s)
1270 - sizeof (tree) * (4 - length)));
1271 vno1->value_id = value_id;
1272 vno1->opcode = code;
1273 vno1->length = length;
1283 vno1->result = result;
1284 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1285 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1287 gcc_assert (!*slot);
1294 /* Insert OP into the current hash table with a value number of
1295 RESULT. Return the vn_nary_op_t structure we created and put in
1299 vn_nary_op_insert (tree op, tree result)
1301 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
1306 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1307 (sizeof (struct vn_nary_op_s)
1308 - sizeof (tree) * (4 - length)));
1309 vno1->value_id = VN_INFO (result)->value_id;
1310 vno1->opcode = TREE_CODE (op);
1311 vno1->length = length;
1312 vno1->type = TREE_TYPE (op);
1313 for (i = 0; i < vno1->length; ++i)
1314 vno1->op[i] = TREE_OPERAND (op, i);
1315 vno1->result = result;
1316 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1317 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1319 gcc_assert (!*slot);
1325 /* Insert the rhs of STMT into the current hash table with a value number of
1329 vn_nary_op_insert_stmt (gimple stmt, tree result)
1331 unsigned length = gimple_num_ops (stmt) - 1;
1336 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1337 (sizeof (struct vn_nary_op_s)
1338 - sizeof (tree) * (4 - length)));
1339 vno1->value_id = VN_INFO (result)->value_id;
1340 vno1->opcode = gimple_assign_rhs_code (stmt);
1341 vno1->length = length;
1342 vno1->type = TREE_TYPE (gimple_assign_lhs (stmt));
1343 for (i = 0; i < vno1->length; ++i)
1344 vno1->op[i] = gimple_op (stmt, i + 1);
1345 if (vno1->opcode == REALPART_EXPR
1346 || vno1->opcode == IMAGPART_EXPR
1347 || vno1->opcode == VIEW_CONVERT_EXPR)
1348 vno1->op[0] = TREE_OPERAND (vno1->op[0], 0);
1349 vno1->result = result;
1350 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1351 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1353 gcc_assert (!*slot);
1359 /* Compute a hashcode for PHI operation VP1 and return it. */
1361 static inline hashval_t
1362 vn_phi_compute_hash (vn_phi_t vp1)
1364 hashval_t result = 0;
1369 result = vp1->block->index;
1371 /* If all PHI arguments are constants we need to distinguish
1372 the PHI node via its type. */
1373 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
1374 result += (INTEGRAL_TYPE_P (type)
1375 + (INTEGRAL_TYPE_P (type)
1376 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
1378 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1380 if (phi1op == VN_TOP)
1382 result += iterative_hash_expr (phi1op, result);
1388 /* Return the computed hashcode for phi operation P1. */
1391 vn_phi_hash (const void *p1)
1393 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1394 return vp1->hashcode;
1397 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1400 vn_phi_eq (const void *p1, const void *p2)
1402 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1403 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
1405 if (vp1->hashcode != vp2->hashcode)
1408 if (vp1->block == vp2->block)
1413 /* If the PHI nodes do not have compatible types
1414 they are not the same. */
1415 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
1416 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
1419 /* Any phi in the same block will have it's arguments in the
1420 same edge order, because of how we store phi nodes. */
1421 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1423 tree phi2op = VEC_index (tree, vp2->phiargs, i);
1424 if (phi1op == VN_TOP || phi2op == VN_TOP)
1426 if (!expressions_equal_p (phi1op, phi2op))
1434 static VEC(tree, heap) *shared_lookup_phiargs;
1436 /* Lookup PHI in the current hash table, and return the resulting
1437 value number if it exists in the hash table. Return NULL_TREE if
1438 it does not exist in the hash table. */
1441 vn_phi_lookup (gimple phi)
1444 struct vn_phi_s vp1;
1447 VEC_truncate (tree, shared_lookup_phiargs, 0);
1449 /* Canonicalize the SSA_NAME's to their value number. */
1450 for (i = 0; i < gimple_phi_num_args (phi); i++)
1452 tree def = PHI_ARG_DEF (phi, i);
1453 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1454 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
1456 vp1.phiargs = shared_lookup_phiargs;
1457 vp1.block = gimple_bb (phi);
1458 vp1.hashcode = vn_phi_compute_hash (&vp1);
1459 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
1461 if (!slot && current_info == optimistic_info)
1462 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
1466 return ((vn_phi_t)*slot)->result;
1469 /* Insert PHI into the current hash table with a value number of
1473 vn_phi_insert (gimple phi, tree result)
1476 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
1478 VEC (tree, heap) *args = NULL;
1480 /* Canonicalize the SSA_NAME's to their value number. */
1481 for (i = 0; i < gimple_phi_num_args (phi); i++)
1483 tree def = PHI_ARG_DEF (phi, i);
1484 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1485 VEC_safe_push (tree, heap, args, def);
1487 vp1->value_id = VN_INFO (result)->value_id;
1488 vp1->phiargs = args;
1489 vp1->block = gimple_bb (phi);
1490 vp1->result = result;
1491 vp1->hashcode = vn_phi_compute_hash (vp1);
1493 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
1496 /* Because we iterate over phi operations more than once, it's
1497 possible the slot might already exist here, hence no assert.*/
1503 /* Print set of components in strongly connected component SCC to OUT. */
1506 print_scc (FILE *out, VEC (tree, heap) *scc)
1511 fprintf (out, "SCC consists of: ");
1512 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1514 print_generic_expr (out, var, 0);
1517 fprintf (out, "\n");
1520 /* Set the value number of FROM to TO, return true if it has changed
1524 set_ssa_val_to (tree from, tree to)
1529 && TREE_CODE (to) == SSA_NAME
1530 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
1533 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1534 and invariants. So assert that here. */
1535 gcc_assert (to != NULL_TREE
1537 || TREE_CODE (to) == SSA_NAME
1538 || is_gimple_min_invariant (to)));
1540 if (dump_file && (dump_flags & TDF_DETAILS))
1542 fprintf (dump_file, "Setting value number of ");
1543 print_generic_expr (dump_file, from, 0);
1544 fprintf (dump_file, " to ");
1545 print_generic_expr (dump_file, to, 0);
1548 currval = SSA_VAL (from);
1550 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
1552 VN_INFO (from)->valnum = to;
1553 if (dump_file && (dump_flags & TDF_DETAILS))
1554 fprintf (dump_file, " (changed)\n");
1557 if (dump_file && (dump_flags & TDF_DETAILS))
1558 fprintf (dump_file, "\n");
1562 /* Set all definitions in STMT to value number to themselves.
1563 Return true if a value number changed. */
1566 defs_to_varying (gimple stmt)
1568 bool changed = false;
1572 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1574 tree def = DEF_FROM_PTR (defp);
1576 VN_INFO (def)->use_processed = true;
1577 changed |= set_ssa_val_to (def, def);
1582 static bool expr_has_constants (tree expr);
1583 static tree valueize_expr (tree expr);
1585 /* Visit a copy between LHS and RHS, return true if the value number
1589 visit_copy (tree lhs, tree rhs)
1591 /* Follow chains of copies to their destination. */
1592 while (TREE_CODE (rhs) == SSA_NAME
1593 && SSA_VAL (rhs) != rhs)
1594 rhs = SSA_VAL (rhs);
1596 /* The copy may have a more interesting constant filled expression
1597 (we don't, since we know our RHS is just an SSA name). */
1598 if (TREE_CODE (rhs) == SSA_NAME)
1600 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1601 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1604 return set_ssa_val_to (lhs, rhs);
1607 /* Visit a unary operator RHS, value number it, and return true if the
1608 value number of LHS has changed as a result. */
1611 visit_unary_op (tree lhs, gimple stmt)
1613 bool changed = false;
1614 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1618 changed = set_ssa_val_to (lhs, result);
1622 changed = set_ssa_val_to (lhs, lhs);
1623 vn_nary_op_insert_stmt (stmt, lhs);
1629 /* Visit a binary operator RHS, value number it, and return true if the
1630 value number of LHS has changed as a result. */
1633 visit_binary_op (tree lhs, gimple stmt)
1635 bool changed = false;
1636 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1640 changed = set_ssa_val_to (lhs, result);
1644 changed = set_ssa_val_to (lhs, lhs);
1645 vn_nary_op_insert_stmt (stmt, lhs);
1651 /* Visit a call STMT storing into LHS. Return true if the value number
1652 of the LHS has changed as a result. */
1655 visit_reference_op_call (tree lhs, gimple stmt)
1657 bool changed = false;
1658 struct vn_reference_s vr1;
1660 tree vuse = gimple_vuse (stmt);
1662 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1663 vr1.operands = valueize_shared_reference_ops_from_call (stmt);
1664 vr1.hashcode = vn_reference_compute_hash (&vr1);
1665 result = vn_reference_lookup_1 (&vr1, NULL);
1668 changed = set_ssa_val_to (lhs, result);
1669 if (TREE_CODE (result) == SSA_NAME
1670 && VN_INFO (result)->has_constants)
1671 VN_INFO (lhs)->has_constants = true;
1677 changed = set_ssa_val_to (lhs, lhs);
1678 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
1679 vr2->vuse = vr1.vuse;
1680 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
1681 vr2->hashcode = vr1.hashcode;
1683 slot = htab_find_slot_with_hash (current_info->references,
1684 vr2, vr2->hashcode, INSERT);
1686 free_reference (*slot);
1693 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1694 and return true if the value number of the LHS has changed as a result. */
1697 visit_reference_op_load (tree lhs, tree op, gimple stmt)
1699 bool changed = false;
1700 tree result = vn_reference_lookup (op, gimple_vuse (stmt), true, NULL);
1702 /* We handle type-punning through unions by value-numbering based
1703 on offset and size of the access. Be prepared to handle a
1704 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1706 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
1708 /* We will be setting the value number of lhs to the value number
1709 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1710 So first simplify and lookup this expression to see if it
1711 is already available. */
1712 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
1713 if ((CONVERT_EXPR_P (val)
1714 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
1715 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
1717 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
1718 if ((CONVERT_EXPR_P (tem)
1719 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
1720 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
1721 TREE_TYPE (val), tem)))
1725 if (!is_gimple_min_invariant (val)
1726 && TREE_CODE (val) != SSA_NAME)
1727 result = vn_nary_op_lookup (val, NULL);
1728 /* If the expression is not yet available, value-number lhs to
1729 a new SSA_NAME we create. */
1730 if (!result && may_insert)
1732 result = make_ssa_name (SSA_NAME_VAR (lhs), NULL);
1733 /* Initialize value-number information properly. */
1734 VN_INFO_GET (result)->valnum = result;
1735 VN_INFO (result)->value_id = get_next_value_id ();
1736 VN_INFO (result)->expr = val;
1737 VN_INFO (result)->has_constants = expr_has_constants (val);
1738 VN_INFO (result)->needs_insertion = true;
1739 /* As all "inserted" statements are singleton SCCs, insert
1740 to the valid table. This is strictly needed to
1741 avoid re-generating new value SSA_NAMEs for the same
1742 expression during SCC iteration over and over (the
1743 optimistic table gets cleared after each iteration).
1744 We do not need to insert into the optimistic table, as
1745 lookups there will fall back to the valid table. */
1746 if (current_info == optimistic_info)
1748 current_info = valid_info;
1749 vn_nary_op_insert (val, result);
1750 current_info = optimistic_info;
1753 vn_nary_op_insert (val, result);
1754 if (dump_file && (dump_flags & TDF_DETAILS))
1756 fprintf (dump_file, "Inserting name ");
1757 print_generic_expr (dump_file, result, 0);
1758 fprintf (dump_file, " for expression ");
1759 print_generic_expr (dump_file, val, 0);
1760 fprintf (dump_file, "\n");
1767 changed = set_ssa_val_to (lhs, result);
1768 if (TREE_CODE (result) == SSA_NAME
1769 && VN_INFO (result)->has_constants)
1771 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
1772 VN_INFO (lhs)->has_constants = true;
1777 changed = set_ssa_val_to (lhs, lhs);
1778 vn_reference_insert (op, lhs, gimple_vuse (stmt));
1785 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1786 and return true if the value number of the LHS has changed as a result. */
1789 visit_reference_op_store (tree lhs, tree op, gimple stmt)
1791 bool changed = false;
1793 bool resultsame = false;
1795 /* First we want to lookup using the *vuses* from the store and see
1796 if there the last store to this location with the same address
1799 The vuses represent the memory state before the store. If the
1800 memory state, address, and value of the store is the same as the
1801 last store to this location, then this store will produce the
1802 same memory state as that store.
1804 In this case the vdef versions for this store are value numbered to those
1805 vuse versions, since they represent the same memory state after
1808 Otherwise, the vdefs for the store are used when inserting into
1809 the table, since the store generates a new memory state. */
1811 result = vn_reference_lookup (lhs, gimple_vuse (stmt), false, NULL);
1815 if (TREE_CODE (result) == SSA_NAME)
1816 result = SSA_VAL (result);
1817 if (TREE_CODE (op) == SSA_NAME)
1819 resultsame = expressions_equal_p (result, op);
1822 if (!result || !resultsame)
1826 if (dump_file && (dump_flags & TDF_DETAILS))
1828 fprintf (dump_file, "No store match\n");
1829 fprintf (dump_file, "Value numbering store ");
1830 print_generic_expr (dump_file, lhs, 0);
1831 fprintf (dump_file, " to ");
1832 print_generic_expr (dump_file, op, 0);
1833 fprintf (dump_file, "\n");
1835 /* Have to set value numbers before insert, since insert is
1836 going to valueize the references in-place. */
1837 if ((vdef = gimple_vdef (stmt)))
1839 VN_INFO (vdef)->use_processed = true;
1840 changed |= set_ssa_val_to (vdef, vdef);
1843 /* Do not insert structure copies into the tables. */
1844 if (is_gimple_min_invariant (op)
1845 || is_gimple_reg (op))
1846 vn_reference_insert (lhs, op, vdef);
1850 /* We had a match, so value number the vdef to have the value
1851 number of the vuse it came from. */
1854 if (dump_file && (dump_flags & TDF_DETAILS))
1855 fprintf (dump_file, "Store matched earlier value,"
1856 "value numbering store vdefs to matching vuses.\n");
1858 def = gimple_vdef (stmt);
1859 use = gimple_vuse (stmt);
1861 VN_INFO (def)->use_processed = true;
1862 changed |= set_ssa_val_to (def, SSA_VAL (use));
1868 /* Visit and value number PHI, return true if the value number
1872 visit_phi (gimple phi)
1874 bool changed = false;
1876 tree sameval = VN_TOP;
1877 bool allsame = true;
1880 /* TODO: We could check for this in init_sccvn, and replace this
1881 with a gcc_assert. */
1882 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
1883 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1885 /* See if all non-TOP arguments have the same value. TOP is
1886 equivalent to everything, so we can ignore it. */
1887 for (i = 0; i < gimple_phi_num_args (phi); i++)
1889 tree def = PHI_ARG_DEF (phi, i);
1891 if (TREE_CODE (def) == SSA_NAME)
1892 def = SSA_VAL (def);
1895 if (sameval == VN_TOP)
1901 if (!expressions_equal_p (def, sameval))
1909 /* If all value numbered to the same value, the phi node has that
1913 if (is_gimple_min_invariant (sameval))
1915 VN_INFO (PHI_RESULT (phi))->has_constants = true;
1916 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1920 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1921 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1924 if (TREE_CODE (sameval) == SSA_NAME)
1925 return visit_copy (PHI_RESULT (phi), sameval);
1927 return set_ssa_val_to (PHI_RESULT (phi), sameval);
1930 /* Otherwise, see if it is equivalent to a phi node in this block. */
1931 result = vn_phi_lookup (phi);
1934 if (TREE_CODE (result) == SSA_NAME)
1935 changed = visit_copy (PHI_RESULT (phi), result);
1937 changed = set_ssa_val_to (PHI_RESULT (phi), result);
1941 vn_phi_insert (phi, PHI_RESULT (phi));
1942 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1943 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1944 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1950 /* Return true if EXPR contains constants. */
1953 expr_has_constants (tree expr)
1955 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1958 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1961 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1962 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1963 /* Constants inside reference ops are rarely interesting, but
1964 it can take a lot of looking to find them. */
1966 case tcc_declaration:
1969 return is_gimple_min_invariant (expr);
1974 /* Return true if STMT contains constants. */
1977 stmt_has_constants (gimple stmt)
1979 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1982 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
1984 case GIMPLE_UNARY_RHS:
1985 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
1987 case GIMPLE_BINARY_RHS:
1988 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
1989 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
1990 case GIMPLE_SINGLE_RHS:
1991 /* Constants inside reference ops are rarely interesting, but
1992 it can take a lot of looking to find them. */
1993 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2000 /* Replace SSA_NAMES in expr with their value numbers, and return the
2002 This is performed in place. */
2005 valueize_expr (tree expr)
2007 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2010 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2011 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2012 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2015 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2016 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2017 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2018 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
2019 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
2020 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
2028 /* Simplify the binary expression RHS, and return the result if
2032 simplify_binary_expression (gimple stmt)
2034 tree result = NULL_TREE;
2035 tree op0 = gimple_assign_rhs1 (stmt);
2036 tree op1 = gimple_assign_rhs2 (stmt);
2038 /* This will not catch every single case we could combine, but will
2039 catch those with constants. The goal here is to simultaneously
2040 combine constants between expressions, but avoid infinite
2041 expansion of expressions during simplification. */
2042 if (TREE_CODE (op0) == SSA_NAME)
2044 if (VN_INFO (op0)->has_constants
2045 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
2046 op0 = valueize_expr (vn_get_expr_for (op0));
2047 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
2048 op0 = SSA_VAL (op0);
2051 if (TREE_CODE (op1) == SSA_NAME)
2053 if (VN_INFO (op1)->has_constants)
2054 op1 = valueize_expr (vn_get_expr_for (op1));
2055 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
2056 op1 = SSA_VAL (op1);
2059 /* Avoid folding if nothing changed. */
2060 if (op0 == gimple_assign_rhs1 (stmt)
2061 && op1 == gimple_assign_rhs2 (stmt))
2064 fold_defer_overflow_warnings ();
2066 result = fold_binary (gimple_assign_rhs_code (stmt),
2067 TREE_TYPE (gimple_get_lhs (stmt)), op0, op1);
2069 STRIP_USELESS_TYPE_CONVERSION (result);
2071 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2074 /* Make sure result is not a complex expression consisting
2075 of operators of operators (IE (a + b) + (a + c))
2076 Otherwise, we will end up with unbounded expressions if
2077 fold does anything at all. */
2078 if (result && valid_gimple_rhs_p (result))
2084 /* Simplify the unary expression RHS, and return the result if
2088 simplify_unary_expression (gimple stmt)
2090 tree result = NULL_TREE;
2091 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2093 /* We handle some tcc_reference codes here that are all
2094 GIMPLE_ASSIGN_SINGLE codes. */
2095 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2096 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2097 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2098 op0 = TREE_OPERAND (op0, 0);
2100 if (TREE_CODE (op0) != SSA_NAME)
2104 if (VN_INFO (op0)->has_constants)
2105 op0 = valueize_expr (vn_get_expr_for (op0));
2106 else if (gimple_assign_cast_p (stmt)
2107 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2108 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2109 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2111 /* We want to do tree-combining on conversion-like expressions.
2112 Make sure we feed only SSA_NAMEs or constants to fold though. */
2113 tree tem = valueize_expr (vn_get_expr_for (op0));
2114 if (UNARY_CLASS_P (tem)
2115 || BINARY_CLASS_P (tem)
2116 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2117 || TREE_CODE (tem) == SSA_NAME
2118 || is_gimple_min_invariant (tem))
2122 /* Avoid folding if nothing changed, but remember the expression. */
2123 if (op0 == orig_op0)
2126 result = fold_unary_ignore_overflow (gimple_assign_rhs_code (stmt),
2127 gimple_expr_type (stmt), op0);
2130 STRIP_USELESS_TYPE_CONVERSION (result);
2131 if (valid_gimple_rhs_p (result))
2138 /* Try to simplify RHS using equivalences and constant folding. */
2141 try_to_simplify (gimple stmt)
2145 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2146 in this case, there is no point in doing extra work. */
2147 if (gimple_assign_copy_p (stmt)
2148 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2151 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2153 case tcc_declaration:
2154 tem = get_symbol_constant_value (gimple_assign_rhs1 (stmt));
2160 /* Do not do full-blown reference lookup here, but simplify
2161 reads from constant aggregates. */
2162 tem = fold_const_aggregate_ref (gimple_assign_rhs1 (stmt));
2166 /* Fallthrough for some codes that can operate on registers. */
2167 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2168 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2169 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2171 /* We could do a little more with unary ops, if they expand
2172 into binary ops, but it's debatable whether it is worth it. */
2174 return simplify_unary_expression (stmt);
2176 case tcc_comparison:
2178 return simplify_binary_expression (stmt);
2187 /* Visit and value number USE, return true if the value number
2191 visit_use (tree use)
2193 bool changed = false;
2194 gimple stmt = SSA_NAME_DEF_STMT (use);
2196 VN_INFO (use)->use_processed = true;
2198 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
2199 if (dump_file && (dump_flags & TDF_DETAILS)
2200 && !SSA_NAME_IS_DEFAULT_DEF (use))
2202 fprintf (dump_file, "Value numbering ");
2203 print_generic_expr (dump_file, use, 0);
2204 fprintf (dump_file, " stmt = ");
2205 print_gimple_stmt (dump_file, stmt, 0, 0);
2208 /* Handle uninitialized uses. */
2209 if (SSA_NAME_IS_DEFAULT_DEF (use))
2210 changed = set_ssa_val_to (use, use);
2213 if (gimple_code (stmt) == GIMPLE_PHI)
2214 changed = visit_phi (stmt);
2215 else if (!gimple_has_lhs (stmt)
2216 || gimple_has_volatile_ops (stmt)
2217 || stmt_could_throw_p (stmt))
2218 changed = defs_to_varying (stmt);
2219 else if (is_gimple_assign (stmt))
2221 tree lhs = gimple_assign_lhs (stmt);
2224 /* Shortcut for copies. Simplifying copies is pointless,
2225 since we copy the expression and value they represent. */
2226 if (gimple_assign_copy_p (stmt)
2227 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2228 && TREE_CODE (lhs) == SSA_NAME)
2230 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
2233 simplified = try_to_simplify (stmt);
2236 if (dump_file && (dump_flags & TDF_DETAILS))
2238 fprintf (dump_file, "RHS ");
2239 print_gimple_expr (dump_file, stmt, 0, 0);
2240 fprintf (dump_file, " simplified to ");
2241 print_generic_expr (dump_file, simplified, 0);
2242 if (TREE_CODE (lhs) == SSA_NAME)
2243 fprintf (dump_file, " has constants %d\n",
2244 expr_has_constants (simplified));
2246 fprintf (dump_file, "\n");
2249 /* Setting value numbers to constants will occasionally
2250 screw up phi congruence because constants are not
2251 uniquely associated with a single ssa name that can be
2254 && is_gimple_min_invariant (simplified)
2255 && TREE_CODE (lhs) == SSA_NAME)
2257 VN_INFO (lhs)->expr = simplified;
2258 VN_INFO (lhs)->has_constants = true;
2259 changed = set_ssa_val_to (lhs, simplified);
2263 && TREE_CODE (simplified) == SSA_NAME
2264 && TREE_CODE (lhs) == SSA_NAME)
2266 changed = visit_copy (lhs, simplified);
2269 else if (simplified)
2271 if (TREE_CODE (lhs) == SSA_NAME)
2273 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
2274 /* We have to unshare the expression or else
2275 valuizing may change the IL stream. */
2276 VN_INFO (lhs)->expr = unshare_expr (simplified);
2279 else if (stmt_has_constants (stmt)
2280 && TREE_CODE (lhs) == SSA_NAME)
2281 VN_INFO (lhs)->has_constants = true;
2282 else if (TREE_CODE (lhs) == SSA_NAME)
2284 /* We reset expr and constantness here because we may
2285 have been value numbering optimistically, and
2286 iterating. They may become non-constant in this case,
2287 even if they were optimistically constant. */
2289 VN_INFO (lhs)->has_constants = false;
2290 VN_INFO (lhs)->expr = NULL_TREE;
2293 if ((TREE_CODE (lhs) == SSA_NAME
2294 /* We can substitute SSA_NAMEs that are live over
2295 abnormal edges with their constant value. */
2296 && !(gimple_assign_copy_p (stmt)
2297 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2299 && is_gimple_min_invariant (simplified))
2300 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2301 /* Stores or copies from SSA_NAMEs that are live over
2302 abnormal edges are a problem. */
2303 || (gimple_assign_single_p (stmt)
2304 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2305 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))))
2306 changed = defs_to_varying (stmt);
2307 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
2309 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
2311 else if (TREE_CODE (lhs) == SSA_NAME)
2313 if ((gimple_assign_copy_p (stmt)
2314 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2316 && is_gimple_min_invariant (simplified)))
2318 VN_INFO (lhs)->has_constants = true;
2320 changed = set_ssa_val_to (lhs, simplified);
2322 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
2326 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2328 case GIMPLE_UNARY_RHS:
2329 changed = visit_unary_op (lhs, stmt);
2331 case GIMPLE_BINARY_RHS:
2332 changed = visit_binary_op (lhs, stmt);
2334 case GIMPLE_SINGLE_RHS:
2335 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2338 /* VOP-less references can go through unary case. */
2339 if ((gimple_assign_rhs_code (stmt) == REALPART_EXPR
2340 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2341 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR )
2342 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (stmt), 0)) == SSA_NAME)
2344 changed = visit_unary_op (lhs, stmt);
2348 case tcc_declaration:
2349 changed = visit_reference_op_load
2350 (lhs, gimple_assign_rhs1 (stmt), stmt);
2352 case tcc_expression:
2353 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
2355 changed = visit_unary_op (lhs, stmt);
2360 changed = defs_to_varying (stmt);
2364 changed = defs_to_varying (stmt);
2370 changed = defs_to_varying (stmt);
2372 else if (is_gimple_call (stmt))
2374 tree lhs = gimple_call_lhs (stmt);
2376 /* ??? We could try to simplify calls. */
2378 if (stmt_has_constants (stmt)
2379 && TREE_CODE (lhs) == SSA_NAME)
2380 VN_INFO (lhs)->has_constants = true;
2381 else if (TREE_CODE (lhs) == SSA_NAME)
2383 /* We reset expr and constantness here because we may
2384 have been value numbering optimistically, and
2385 iterating. They may become non-constant in this case,
2386 even if they were optimistically constant. */
2387 VN_INFO (lhs)->has_constants = false;
2388 VN_INFO (lhs)->expr = NULL_TREE;
2391 if (TREE_CODE (lhs) == SSA_NAME
2392 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2393 changed = defs_to_varying (stmt);
2394 /* ??? We should handle stores from calls. */
2395 else if (TREE_CODE (lhs) == SSA_NAME)
2397 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2398 changed = visit_reference_op_call (lhs, stmt);
2400 changed = defs_to_varying (stmt);
2403 changed = defs_to_varying (stmt);
2410 /* Compare two operands by reverse postorder index */
2413 compare_ops (const void *pa, const void *pb)
2415 const tree opa = *((const tree *)pa);
2416 const tree opb = *((const tree *)pb);
2417 gimple opstmta = SSA_NAME_DEF_STMT (opa);
2418 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
2422 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
2424 else if (gimple_nop_p (opstmta))
2426 else if (gimple_nop_p (opstmtb))
2429 bba = gimple_bb (opstmta);
2430 bbb = gimple_bb (opstmtb);
2441 if (gimple_code (opstmta) == GIMPLE_PHI
2442 && gimple_code (opstmtb) == GIMPLE_PHI)
2444 else if (gimple_code (opstmta) == GIMPLE_PHI)
2446 else if (gimple_code (opstmtb) == GIMPLE_PHI)
2448 return gimple_uid (opstmta) - gimple_uid (opstmtb);
2450 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
2453 /* Sort an array containing members of a strongly connected component
2454 SCC so that the members are ordered by RPO number.
2455 This means that when the sort is complete, iterating through the
2456 array will give you the members in RPO order. */
2459 sort_scc (VEC (tree, heap) *scc)
2461 qsort (VEC_address (tree, scc),
2462 VEC_length (tree, scc),
2467 /* Process a strongly connected component in the SSA graph. */
2470 process_scc (VEC (tree, heap) *scc)
2472 /* If the SCC has a single member, just visit it. */
2474 if (VEC_length (tree, scc) == 1)
2476 tree use = VEC_index (tree, scc, 0);
2477 if (!VN_INFO (use)->use_processed)
2484 unsigned int iterations = 0;
2485 bool changed = true;
2487 /* Iterate over the SCC with the optimistic table until it stops
2489 current_info = optimistic_info;
2494 /* As we are value-numbering optimistically we have to
2495 clear the expression tables and the simplified expressions
2496 in each iteration until we converge. */
2497 htab_empty (optimistic_info->nary);
2498 htab_empty (optimistic_info->phis);
2499 htab_empty (optimistic_info->references);
2500 obstack_free (&optimistic_info->nary_obstack, NULL);
2501 gcc_obstack_init (&optimistic_info->nary_obstack);
2502 empty_alloc_pool (optimistic_info->phis_pool);
2503 empty_alloc_pool (optimistic_info->references_pool);
2504 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2505 VN_INFO (var)->expr = NULL_TREE;
2506 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2507 changed |= visit_use (var);
2510 statistics_histogram_event (cfun, "SCC iterations", iterations);
2512 /* Finally, visit the SCC once using the valid table. */
2513 current_info = valid_info;
2514 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2519 DEF_VEC_O(ssa_op_iter);
2520 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
2522 /* Pop the components of the found SCC for NAME off the SCC stack
2523 and process them. Returns true if all went well, false if
2524 we run into resource limits. */
2527 extract_and_process_scc_for_name (tree name)
2529 VEC (tree, heap) *scc = NULL;
2532 /* Found an SCC, pop the components off the SCC stack and
2536 x = VEC_pop (tree, sccstack);
2538 VN_INFO (x)->on_sccstack = false;
2539 VEC_safe_push (tree, heap, scc, x);
2540 } while (x != name);
2542 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2543 if (VEC_length (tree, scc)
2544 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
2547 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
2548 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
2549 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
2553 if (VEC_length (tree, scc) > 1)
2556 if (dump_file && (dump_flags & TDF_DETAILS))
2557 print_scc (dump_file, scc);
2561 VEC_free (tree, heap, scc);
2566 /* Depth first search on NAME to discover and process SCC's in the SSA
2568 Execution of this algorithm relies on the fact that the SCC's are
2569 popped off the stack in topological order.
2570 Returns true if successful, false if we stopped processing SCC's due
2571 to resource constraints. */
2576 VEC(ssa_op_iter, heap) *itervec = NULL;
2577 VEC(tree, heap) *namevec = NULL;
2578 use_operand_p usep = NULL;
2585 VN_INFO (name)->dfsnum = next_dfs_num++;
2586 VN_INFO (name)->visited = true;
2587 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
2589 VEC_safe_push (tree, heap, sccstack, name);
2590 VN_INFO (name)->on_sccstack = true;
2591 defstmt = SSA_NAME_DEF_STMT (name);
2593 /* Recursively DFS on our operands, looking for SCC's. */
2594 if (!gimple_nop_p (defstmt))
2596 /* Push a new iterator. */
2597 if (gimple_code (defstmt) == GIMPLE_PHI)
2598 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
2600 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
2603 clear_and_done_ssa_iter (&iter);
2607 /* If we are done processing uses of a name, go up the stack
2608 of iterators and process SCCs as we found them. */
2609 if (op_iter_done (&iter))
2611 /* See if we found an SCC. */
2612 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
2613 if (!extract_and_process_scc_for_name (name))
2615 VEC_free (tree, heap, namevec);
2616 VEC_free (ssa_op_iter, heap, itervec);
2620 /* Check if we are done. */
2621 if (VEC_empty (tree, namevec))
2623 VEC_free (tree, heap, namevec);
2624 VEC_free (ssa_op_iter, heap, itervec);
2628 /* Restore the last use walker and continue walking there. */
2630 name = VEC_pop (tree, namevec);
2631 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
2632 sizeof (ssa_op_iter));
2633 VEC_pop (ssa_op_iter, itervec);
2634 goto continue_walking;
2637 use = USE_FROM_PTR (usep);
2639 /* Since we handle phi nodes, we will sometimes get
2640 invariants in the use expression. */
2641 if (TREE_CODE (use) == SSA_NAME)
2643 if (! (VN_INFO (use)->visited))
2645 /* Recurse by pushing the current use walking state on
2646 the stack and starting over. */
2647 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
2648 VEC_safe_push(tree, heap, namevec, name);
2653 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
2654 VN_INFO (use)->low);
2656 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
2657 && VN_INFO (use)->on_sccstack)
2659 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
2660 VN_INFO (name)->low);
2664 usep = op_iter_next_use (&iter);
2668 /* Allocate a value number table. */
2671 allocate_vn_table (vn_tables_t table)
2673 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
2674 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
2675 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
2678 gcc_obstack_init (&table->nary_obstack);
2679 table->phis_pool = create_alloc_pool ("VN phis",
2680 sizeof (struct vn_phi_s),
2682 table->references_pool = create_alloc_pool ("VN references",
2683 sizeof (struct vn_reference_s),
2687 /* Free a value number table. */
2690 free_vn_table (vn_tables_t table)
2692 htab_delete (table->phis);
2693 htab_delete (table->nary);
2694 htab_delete (table->references);
2695 obstack_free (&table->nary_obstack, NULL);
2696 free_alloc_pool (table->phis_pool);
2697 free_alloc_pool (table->references_pool);
2705 int *rpo_numbers_temp;
2707 calculate_dominance_info (CDI_DOMINATORS);
2709 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
2712 constant_value_ids = BITMAP_ALLOC (NULL);
2717 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
2718 /* VEC_alloc doesn't actually grow it to the right size, it just
2719 preallocates the space to do so. */
2720 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
2721 gcc_obstack_init (&vn_ssa_aux_obstack);
2723 shared_lookup_phiargs = NULL;
2724 shared_lookup_references = NULL;
2725 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2726 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2727 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
2729 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
2730 the i'th block in RPO order is bb. We want to map bb's to RPO
2731 numbers, so we need to rearrange this array. */
2732 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
2733 rpo_numbers[rpo_numbers_temp[j]] = j;
2735 XDELETE (rpo_numbers_temp);
2737 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
2739 /* Create the VN_INFO structures, and initialize value numbers to
2741 for (i = 0; i < num_ssa_names; i++)
2743 tree name = ssa_name (i);
2746 VN_INFO_GET (name)->valnum = VN_TOP;
2747 VN_INFO (name)->expr = NULL_TREE;
2748 VN_INFO (name)->value_id = 0;
2752 renumber_gimple_stmt_uids ();
2754 /* Create the valid and optimistic value numbering tables. */
2755 valid_info = XCNEW (struct vn_tables_s);
2756 allocate_vn_table (valid_info);
2757 optimistic_info = XCNEW (struct vn_tables_s);
2758 allocate_vn_table (optimistic_info);
2766 htab_delete (constant_to_value_id);
2767 BITMAP_FREE (constant_value_ids);
2768 VEC_free (tree, heap, shared_lookup_phiargs);
2769 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
2770 XDELETEVEC (rpo_numbers);
2772 for (i = 0; i < num_ssa_names; i++)
2774 tree name = ssa_name (i);
2776 && VN_INFO (name)->needs_insertion)
2777 release_ssa_name (name);
2779 obstack_free (&vn_ssa_aux_obstack, NULL);
2780 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
2782 VEC_free (tree, heap, sccstack);
2783 free_vn_table (valid_info);
2784 XDELETE (valid_info);
2785 free_vn_table (optimistic_info);
2786 XDELETE (optimistic_info);
2789 /* Set the value ids in the valid hash tables. */
2792 set_hashtable_value_ids (void)
2799 /* Now set the value ids of the things we had put in the hash
2802 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
2803 vno, vn_nary_op_t, hi)
2807 if (TREE_CODE (vno->result) == SSA_NAME)
2808 vno->value_id = VN_INFO (vno->result)->value_id;
2809 else if (is_gimple_min_invariant (vno->result))
2810 vno->value_id = get_or_alloc_constant_value_id (vno->result);
2814 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
2819 if (TREE_CODE (vp->result) == SSA_NAME)
2820 vp->value_id = VN_INFO (vp->result)->value_id;
2821 else if (is_gimple_min_invariant (vp->result))
2822 vp->value_id = get_or_alloc_constant_value_id (vp->result);
2826 FOR_EACH_HTAB_ELEMENT (valid_info->references,
2827 vr, vn_reference_t, hi)
2831 if (TREE_CODE (vr->result) == SSA_NAME)
2832 vr->value_id = VN_INFO (vr->result)->value_id;
2833 else if (is_gimple_min_invariant (vr->result))
2834 vr->value_id = get_or_alloc_constant_value_id (vr->result);
2839 /* Do SCCVN. Returns true if it finished, false if we bailed out
2840 due to resource constraints. */
2843 run_scc_vn (bool may_insert_arg)
2847 bool changed = true;
2849 may_insert = may_insert_arg;
2852 current_info = valid_info;
2854 for (param = DECL_ARGUMENTS (current_function_decl);
2856 param = TREE_CHAIN (param))
2858 if (gimple_default_def (cfun, param) != NULL)
2860 tree def = gimple_default_def (cfun, param);
2861 VN_INFO (def)->valnum = def;
2865 for (i = 1; i < num_ssa_names; ++i)
2867 tree name = ssa_name (i);
2869 && VN_INFO (name)->visited == false
2870 && !has_zero_uses (name))
2879 /* Initialize the value ids. */
2881 for (i = 1; i < num_ssa_names; ++i)
2883 tree name = ssa_name (i);
2887 info = VN_INFO (name);
2888 if (info->valnum == name)
2889 info->value_id = get_next_value_id ();
2890 else if (is_gimple_min_invariant (info->valnum))
2891 info->value_id = get_or_alloc_constant_value_id (info->valnum);
2894 /* Propagate until they stop changing. */
2898 for (i = 1; i < num_ssa_names; ++i)
2900 tree name = ssa_name (i);
2904 info = VN_INFO (name);
2905 if (TREE_CODE (info->valnum) == SSA_NAME
2906 && info->valnum != name
2907 && info->value_id != VN_INFO (info->valnum)->value_id)
2910 info->value_id = VN_INFO (info->valnum)->value_id;
2915 set_hashtable_value_ids ();
2917 if (dump_file && (dump_flags & TDF_DETAILS))
2919 fprintf (dump_file, "Value numbers:\n");
2920 for (i = 0; i < num_ssa_names; i++)
2922 tree name = ssa_name (i);
2924 && VN_INFO (name)->visited
2925 && SSA_VAL (name) != name)
2927 print_generic_expr (dump_file, name, 0);
2928 fprintf (dump_file, " = ");
2929 print_generic_expr (dump_file, SSA_VAL (name), 0);
2930 fprintf (dump_file, "\n");
2939 /* Return the maximum value id we have ever seen. */
2942 get_max_value_id (void)
2944 return next_value_id;
2947 /* Return the next unique value id. */
2950 get_next_value_id (void)
2952 return next_value_id++;
2956 /* Compare two expressions E1 and E2 and return true if they are equal. */
2959 expressions_equal_p (tree e1, tree e2)
2961 /* The obvious case. */
2965 /* If only one of them is null, they cannot be equal. */
2969 /* Recurse on elements of lists. */
2970 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
2974 for (lop1 = e1, lop2 = e2;
2976 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
2980 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
2986 /* Now perform the actual comparison. */
2987 if (TREE_CODE (e1) == TREE_CODE (e2)
2988 && operand_equal_p (e1, e2, OEP_PURE_SAME))
2995 /* Return true if the nary operation NARY may trap. This is a copy
2996 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
2999 vn_nary_may_trap (vn_nary_op_t nary)
3003 bool honor_nans = false;
3004 bool honor_snans = false;
3005 bool fp_operation = false;
3006 bool honor_trapv = false;
3010 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
3011 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
3012 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
3015 fp_operation = FLOAT_TYPE_P (type);
3018 honor_nans = flag_trapping_math && !flag_finite_math_only;
3019 honor_snans = flag_signaling_nans != 0;
3021 else if (INTEGRAL_TYPE_P (type)
3022 && TYPE_OVERFLOW_TRAPS (type))
3026 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
3028 honor_nans, honor_snans, rhs2,
3034 for (i = 0; i < nary->length; ++i)
3035 if (tree_could_trap_p (nary->op[i]))