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)
836 vn_reference_fold_indirect (&orig, &i);
838 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
839 vro->op1 = SSA_VAL (vro->op1);
840 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
841 vro->op2 = SSA_VAL (vro->op2);
847 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
849 /* Create a vector of vn_reference_op_s structures from REF, a
850 REFERENCE_CLASS_P tree. The vector is shared among all callers of
853 static VEC(vn_reference_op_s, heap) *
854 valueize_shared_reference_ops_from_ref (tree ref)
858 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
859 copy_reference_ops_from_ref (ref, &shared_lookup_references);
860 shared_lookup_references = valueize_refs (shared_lookup_references);
861 return shared_lookup_references;
864 /* Create a vector of vn_reference_op_s structures from CALL, a
865 call statement. The vector is shared among all callers of
868 static VEC(vn_reference_op_s, heap) *
869 valueize_shared_reference_ops_from_call (gimple call)
873 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
874 copy_reference_ops_from_call (call, &shared_lookup_references);
875 shared_lookup_references = valueize_refs (shared_lookup_references);
876 return shared_lookup_references;
879 /* Lookup a SCCVN reference operation VR in the current hash table.
880 Returns the resulting value number if it exists in the hash table,
881 NULL_TREE otherwise. VNRESULT will be filled in with the actual
882 vn_reference_t stored in the hashtable if something is found. */
885 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
891 slot = htab_find_slot_with_hash (current_info->references, vr,
893 if (!slot && current_info == optimistic_info)
894 slot = htab_find_slot_with_hash (valid_info->references, vr,
899 *vnresult = (vn_reference_t)*slot;
900 return ((vn_reference_t)*slot)->result;
906 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
907 with the current VUSE and performs the expression lookup. */
910 vn_reference_lookup_2 (tree op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
912 vn_reference_t vr = (vn_reference_t)vr_;
916 /* Fixup vuse and hash. */
917 vr->hashcode = vr->hashcode - iterative_hash_expr (vr->vuse, 0);
918 vr->vuse = SSA_VAL (vuse);
919 vr->hashcode = vr->hashcode + iterative_hash_expr (vr->vuse, 0);
922 slot = htab_find_slot_with_hash (current_info->references, vr,
924 if (!slot && current_info == optimistic_info)
925 slot = htab_find_slot_with_hash (valid_info->references, vr,
933 /* Lookup a reference operation by it's parts, in the current hash table.
934 Returns the resulting value number if it exists in the hash table,
935 NULL_TREE otherwise. VNRESULT will be filled in with the actual
936 vn_reference_t stored in the hashtable if something is found. */
939 vn_reference_lookup_pieces (tree vuse,
940 VEC (vn_reference_op_s, heap) *operands,
941 vn_reference_t *vnresult, bool maywalk)
943 struct vn_reference_s vr1;
950 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
951 vr1.operands = valueize_refs (operands);
952 vr1.hashcode = vn_reference_compute_hash (&vr1);
953 vn_reference_lookup_1 (&vr1, vnresult);
959 tree ref = get_ref_from_reference_ops (operands);
963 (vn_reference_t)walk_non_aliased_vuses (ref, vr1.vuse,
964 vn_reference_lookup_2, &vr1);
968 return (*vnresult)->result;
973 /* Lookup OP in the current hash table, and return the resulting value
974 number if it exists in the hash table. Return NULL_TREE if it does
975 not exist in the hash table or if the result field of the structure
976 was NULL.. VNRESULT will be filled in with the vn_reference_t
977 stored in the hashtable if one exists. */
980 vn_reference_lookup (tree op, tree vuse, bool maywalk,
981 vn_reference_t *vnresult)
983 struct vn_reference_s vr1;
988 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
989 vr1.operands = valueize_shared_reference_ops_from_ref (op);
990 vr1.hashcode = vn_reference_compute_hash (&vr1);
995 vn_reference_t wvnresult;
997 (vn_reference_t)walk_non_aliased_vuses (op, vr1.vuse,
998 vn_reference_lookup_2, &vr1);
1002 *vnresult = wvnresult;
1003 return wvnresult->result;
1009 return vn_reference_lookup_1 (&vr1, vnresult);
1013 /* Insert OP into the current hash table with a value number of
1014 RESULT, and return the resulting reference structure we created. */
1017 vn_reference_insert (tree op, tree result, tree vuse)
1022 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1023 if (TREE_CODE (result) == SSA_NAME)
1024 vr1->value_id = VN_INFO (result)->value_id;
1026 vr1->value_id = get_or_alloc_constant_value_id (result);
1027 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1028 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1029 vr1->hashcode = vn_reference_compute_hash (vr1);
1030 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1032 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1035 /* Because we lookup stores using vuses, and value number failures
1036 using the vdefs (see visit_reference_op_store for how and why),
1037 it's possible that on failure we may try to insert an already
1038 inserted store. This is not wrong, there is no ssa name for a
1039 store that we could use as a differentiator anyway. Thus, unlike
1040 the other lookup functions, you cannot gcc_assert (!*slot)
1043 /* But free the old slot in case of a collision. */
1045 free_reference (*slot);
1051 /* Insert a reference by it's pieces into the current hash table with
1052 a value number of RESULT. Return the resulting reference
1053 structure we created. */
1056 vn_reference_insert_pieces (tree vuse,
1057 VEC (vn_reference_op_s, heap) *operands,
1058 tree result, unsigned int value_id)
1064 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1065 vr1->value_id = value_id;
1066 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1067 vr1->operands = valueize_refs (operands);
1068 vr1->hashcode = vn_reference_compute_hash (vr1);
1069 if (result && TREE_CODE (result) == SSA_NAME)
1070 result = SSA_VAL (result);
1071 vr1->result = result;
1073 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1076 /* At this point we should have all the things inserted that we have
1077 seen before, and we should never try inserting something that
1079 gcc_assert (!*slot);
1081 free_reference (*slot);
1087 /* Compute and return the hash value for nary operation VBO1. */
1090 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
1095 for (i = 0; i < vno1->length; ++i)
1096 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
1097 vno1->op[i] = SSA_VAL (vno1->op[i]);
1099 if (vno1->length == 2
1100 && commutative_tree_code (vno1->opcode)
1101 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
1103 tree temp = vno1->op[0];
1104 vno1->op[0] = vno1->op[1];
1108 for (i = 0; i < vno1->length; ++i)
1109 hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
1114 /* Return the computed hashcode for nary operation P1. */
1117 vn_nary_op_hash (const void *p1)
1119 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1120 return vno1->hashcode;
1123 /* Compare nary operations P1 and P2 and return true if they are
1127 vn_nary_op_eq (const void *p1, const void *p2)
1129 const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
1130 const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
1133 if (vno1->hashcode != vno2->hashcode)
1136 if (vno1->opcode != vno2->opcode
1137 || !types_compatible_p (vno1->type, vno2->type))
1140 for (i = 0; i < vno1->length; ++i)
1141 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
1147 /* Lookup a n-ary operation by its pieces and return the resulting value
1148 number if it exists in the hash table. Return NULL_TREE if it does
1149 not exist in the hash table or if the result field of the operation
1150 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1154 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
1155 tree type, tree op0, tree op1, tree op2,
1156 tree op3, vn_nary_op_t *vnresult)
1159 struct vn_nary_op_s vno1;
1163 vno1.length = length;
1169 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1170 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1172 if (!slot && current_info == optimistic_info)
1173 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1178 *vnresult = (vn_nary_op_t)*slot;
1179 return ((vn_nary_op_t)*slot)->result;
1182 /* Lookup OP in the current hash table, and return the resulting value
1183 number if it exists in the hash table. Return NULL_TREE if it does
1184 not exist in the hash table or if the result field of the operation
1185 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
1189 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
1192 struct vn_nary_op_s vno1;
1197 vno1.opcode = TREE_CODE (op);
1198 vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
1199 vno1.type = TREE_TYPE (op);
1200 for (i = 0; i < vno1.length; ++i)
1201 vno1.op[i] = TREE_OPERAND (op, i);
1202 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1203 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1205 if (!slot && current_info == optimistic_info)
1206 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1211 *vnresult = (vn_nary_op_t)*slot;
1212 return ((vn_nary_op_t)*slot)->result;
1215 /* Lookup the rhs of STMT in the current hash table, and return the resulting
1216 value number if it exists in the hash table. Return NULL_TREE if
1217 it does not exist in the hash table. VNRESULT will contain the
1218 vn_nary_op_t from the hashtable if it exists. */
1221 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
1224 struct vn_nary_op_s vno1;
1229 vno1.opcode = gimple_assign_rhs_code (stmt);
1230 vno1.length = gimple_num_ops (stmt) - 1;
1231 vno1.type = TREE_TYPE (gimple_assign_lhs (stmt));
1232 for (i = 0; i < vno1.length; ++i)
1233 vno1.op[i] = gimple_op (stmt, i + 1);
1234 if (vno1.opcode == REALPART_EXPR
1235 || vno1.opcode == IMAGPART_EXPR
1236 || vno1.opcode == VIEW_CONVERT_EXPR)
1237 vno1.op[0] = TREE_OPERAND (vno1.op[0], 0);
1238 vno1.hashcode = vn_nary_op_compute_hash (&vno1);
1239 slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
1241 if (!slot && current_info == optimistic_info)
1242 slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
1247 *vnresult = (vn_nary_op_t)*slot;
1248 return ((vn_nary_op_t)*slot)->result;
1251 /* Insert a n-ary operation into the current hash table using it's
1252 pieces. Return the vn_nary_op_t structure we created and put in
1256 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
1257 tree type, tree op0,
1258 tree op1, tree op2, tree op3,
1260 unsigned int value_id)
1265 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1266 (sizeof (struct vn_nary_op_s)
1267 - sizeof (tree) * (4 - length)));
1268 vno1->value_id = value_id;
1269 vno1->opcode = code;
1270 vno1->length = length;
1280 vno1->result = result;
1281 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1282 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1284 gcc_assert (!*slot);
1291 /* Insert OP into the current hash table with a value number of
1292 RESULT. Return the vn_nary_op_t structure we created and put in
1296 vn_nary_op_insert (tree op, tree result)
1298 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
1303 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1304 (sizeof (struct vn_nary_op_s)
1305 - sizeof (tree) * (4 - length)));
1306 vno1->value_id = VN_INFO (result)->value_id;
1307 vno1->opcode = TREE_CODE (op);
1308 vno1->length = length;
1309 vno1->type = TREE_TYPE (op);
1310 for (i = 0; i < vno1->length; ++i)
1311 vno1->op[i] = TREE_OPERAND (op, i);
1312 vno1->result = result;
1313 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1314 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1316 gcc_assert (!*slot);
1322 /* Insert the rhs of STMT into the current hash table with a value number of
1326 vn_nary_op_insert_stmt (gimple stmt, tree result)
1328 unsigned length = gimple_num_ops (stmt) - 1;
1333 vno1 = (vn_nary_op_t) obstack_alloc (¤t_info->nary_obstack,
1334 (sizeof (struct vn_nary_op_s)
1335 - sizeof (tree) * (4 - length)));
1336 vno1->value_id = VN_INFO (result)->value_id;
1337 vno1->opcode = gimple_assign_rhs_code (stmt);
1338 vno1->length = length;
1339 vno1->type = TREE_TYPE (gimple_assign_lhs (stmt));
1340 for (i = 0; i < vno1->length; ++i)
1341 vno1->op[i] = gimple_op (stmt, i + 1);
1342 if (vno1->opcode == REALPART_EXPR
1343 || vno1->opcode == IMAGPART_EXPR
1344 || vno1->opcode == VIEW_CONVERT_EXPR)
1345 vno1->op[0] = TREE_OPERAND (vno1->op[0], 0);
1346 vno1->result = result;
1347 vno1->hashcode = vn_nary_op_compute_hash (vno1);
1348 slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
1350 gcc_assert (!*slot);
1356 /* Compute a hashcode for PHI operation VP1 and return it. */
1358 static inline hashval_t
1359 vn_phi_compute_hash (vn_phi_t vp1)
1361 hashval_t result = 0;
1366 result = vp1->block->index;
1368 /* If all PHI arguments are constants we need to distinguish
1369 the PHI node via its type. */
1370 type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
1371 result += (INTEGRAL_TYPE_P (type)
1372 + (INTEGRAL_TYPE_P (type)
1373 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
1375 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1377 if (phi1op == VN_TOP)
1379 result += iterative_hash_expr (phi1op, result);
1385 /* Return the computed hashcode for phi operation P1. */
1388 vn_phi_hash (const void *p1)
1390 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1391 return vp1->hashcode;
1394 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
1397 vn_phi_eq (const void *p1, const void *p2)
1399 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
1400 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
1402 if (vp1->hashcode != vp2->hashcode)
1405 if (vp1->block == vp2->block)
1410 /* If the PHI nodes do not have compatible types
1411 they are not the same. */
1412 if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
1413 TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
1416 /* Any phi in the same block will have it's arguments in the
1417 same edge order, because of how we store phi nodes. */
1418 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
1420 tree phi2op = VEC_index (tree, vp2->phiargs, i);
1421 if (phi1op == VN_TOP || phi2op == VN_TOP)
1423 if (!expressions_equal_p (phi1op, phi2op))
1431 static VEC(tree, heap) *shared_lookup_phiargs;
1433 /* Lookup PHI in the current hash table, and return the resulting
1434 value number if it exists in the hash table. Return NULL_TREE if
1435 it does not exist in the hash table. */
1438 vn_phi_lookup (gimple phi)
1441 struct vn_phi_s vp1;
1444 VEC_truncate (tree, shared_lookup_phiargs, 0);
1446 /* Canonicalize the SSA_NAME's to their value number. */
1447 for (i = 0; i < gimple_phi_num_args (phi); i++)
1449 tree def = PHI_ARG_DEF (phi, i);
1450 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1451 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
1453 vp1.phiargs = shared_lookup_phiargs;
1454 vp1.block = gimple_bb (phi);
1455 vp1.hashcode = vn_phi_compute_hash (&vp1);
1456 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
1458 if (!slot && current_info == optimistic_info)
1459 slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
1463 return ((vn_phi_t)*slot)->result;
1466 /* Insert PHI into the current hash table with a value number of
1470 vn_phi_insert (gimple phi, tree result)
1473 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
1475 VEC (tree, heap) *args = NULL;
1477 /* Canonicalize the SSA_NAME's to their value number. */
1478 for (i = 0; i < gimple_phi_num_args (phi); i++)
1480 tree def = PHI_ARG_DEF (phi, i);
1481 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1482 VEC_safe_push (tree, heap, args, def);
1484 vp1->value_id = VN_INFO (result)->value_id;
1485 vp1->phiargs = args;
1486 vp1->block = gimple_bb (phi);
1487 vp1->result = result;
1488 vp1->hashcode = vn_phi_compute_hash (vp1);
1490 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
1493 /* Because we iterate over phi operations more than once, it's
1494 possible the slot might already exist here, hence no assert.*/
1500 /* Print set of components in strongly connected component SCC to OUT. */
1503 print_scc (FILE *out, VEC (tree, heap) *scc)
1508 fprintf (out, "SCC consists of: ");
1509 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1511 print_generic_expr (out, var, 0);
1514 fprintf (out, "\n");
1517 /* Set the value number of FROM to TO, return true if it has changed
1521 set_ssa_val_to (tree from, tree to)
1526 && TREE_CODE (to) == SSA_NAME
1527 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
1530 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1531 and invariants. So assert that here. */
1532 gcc_assert (to != NULL_TREE
1534 || TREE_CODE (to) == SSA_NAME
1535 || is_gimple_min_invariant (to)));
1537 if (dump_file && (dump_flags & TDF_DETAILS))
1539 fprintf (dump_file, "Setting value number of ");
1540 print_generic_expr (dump_file, from, 0);
1541 fprintf (dump_file, " to ");
1542 print_generic_expr (dump_file, to, 0);
1545 currval = SSA_VAL (from);
1547 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
1549 VN_INFO (from)->valnum = to;
1550 if (dump_file && (dump_flags & TDF_DETAILS))
1551 fprintf (dump_file, " (changed)\n");
1554 if (dump_file && (dump_flags & TDF_DETAILS))
1555 fprintf (dump_file, "\n");
1559 /* Set all definitions in STMT to value number to themselves.
1560 Return true if a value number changed. */
1563 defs_to_varying (gimple stmt)
1565 bool changed = false;
1569 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1571 tree def = DEF_FROM_PTR (defp);
1573 VN_INFO (def)->use_processed = true;
1574 changed |= set_ssa_val_to (def, def);
1579 static bool expr_has_constants (tree expr);
1580 static tree valueize_expr (tree expr);
1582 /* Visit a copy between LHS and RHS, return true if the value number
1586 visit_copy (tree lhs, tree rhs)
1588 /* Follow chains of copies to their destination. */
1589 while (TREE_CODE (rhs) == SSA_NAME
1590 && SSA_VAL (rhs) != rhs)
1591 rhs = SSA_VAL (rhs);
1593 /* The copy may have a more interesting constant filled expression
1594 (we don't, since we know our RHS is just an SSA name). */
1595 if (TREE_CODE (rhs) == SSA_NAME)
1597 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1598 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1601 return set_ssa_val_to (lhs, rhs);
1604 /* Visit a unary operator RHS, value number it, and return true if the
1605 value number of LHS has changed as a result. */
1608 visit_unary_op (tree lhs, gimple stmt)
1610 bool changed = false;
1611 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1615 changed = set_ssa_val_to (lhs, result);
1619 changed = set_ssa_val_to (lhs, lhs);
1620 vn_nary_op_insert_stmt (stmt, lhs);
1626 /* Visit a binary operator RHS, value number it, and return true if the
1627 value number of LHS has changed as a result. */
1630 visit_binary_op (tree lhs, gimple stmt)
1632 bool changed = false;
1633 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
1637 changed = set_ssa_val_to (lhs, result);
1641 changed = set_ssa_val_to (lhs, lhs);
1642 vn_nary_op_insert_stmt (stmt, lhs);
1648 /* Visit a call STMT storing into LHS. Return true if the value number
1649 of the LHS has changed as a result. */
1652 visit_reference_op_call (tree lhs, gimple stmt)
1654 bool changed = false;
1655 struct vn_reference_s vr1;
1657 tree vuse = gimple_vuse (stmt);
1659 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1660 vr1.operands = valueize_shared_reference_ops_from_call (stmt);
1661 vr1.hashcode = vn_reference_compute_hash (&vr1);
1662 result = vn_reference_lookup_1 (&vr1, NULL);
1665 changed = set_ssa_val_to (lhs, result);
1666 if (TREE_CODE (result) == SSA_NAME
1667 && VN_INFO (result)->has_constants)
1668 VN_INFO (lhs)->has_constants = true;
1674 changed = set_ssa_val_to (lhs, lhs);
1675 vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
1676 vr2->vuse = vr1.vuse;
1677 vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
1678 vr2->hashcode = vr1.hashcode;
1680 slot = htab_find_slot_with_hash (current_info->references,
1681 vr2, vr2->hashcode, INSERT);
1683 free_reference (*slot);
1690 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1691 and return true if the value number of the LHS has changed as a result. */
1694 visit_reference_op_load (tree lhs, tree op, gimple stmt)
1696 bool changed = false;
1697 tree result = vn_reference_lookup (op, gimple_vuse (stmt), true, NULL);
1699 /* We handle type-punning through unions by value-numbering based
1700 on offset and size of the access. Be prepared to handle a
1701 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
1703 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
1705 /* We will be setting the value number of lhs to the value number
1706 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1707 So first simplify and lookup this expression to see if it
1708 is already available. */
1709 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
1710 if ((CONVERT_EXPR_P (val)
1711 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
1712 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
1714 tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
1715 if ((CONVERT_EXPR_P (tem)
1716 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
1717 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
1718 TREE_TYPE (val), tem)))
1722 if (!is_gimple_min_invariant (val)
1723 && TREE_CODE (val) != SSA_NAME)
1724 result = vn_nary_op_lookup (val, NULL);
1725 /* If the expression is not yet available, value-number lhs to
1726 a new SSA_NAME we create. */
1727 if (!result && may_insert)
1729 result = make_ssa_name (SSA_NAME_VAR (lhs), NULL);
1730 /* Initialize value-number information properly. */
1731 VN_INFO_GET (result)->valnum = result;
1732 VN_INFO (result)->value_id = get_next_value_id ();
1733 VN_INFO (result)->expr = val;
1734 VN_INFO (result)->has_constants = expr_has_constants (val);
1735 VN_INFO (result)->needs_insertion = true;
1736 /* As all "inserted" statements are singleton SCCs, insert
1737 to the valid table. This is strictly needed to
1738 avoid re-generating new value SSA_NAMEs for the same
1739 expression during SCC iteration over and over (the
1740 optimistic table gets cleared after each iteration).
1741 We do not need to insert into the optimistic table, as
1742 lookups there will fall back to the valid table. */
1743 if (current_info == optimistic_info)
1745 current_info = valid_info;
1746 vn_nary_op_insert (val, result);
1747 current_info = optimistic_info;
1750 vn_nary_op_insert (val, result);
1751 if (dump_file && (dump_flags & TDF_DETAILS))
1753 fprintf (dump_file, "Inserting name ");
1754 print_generic_expr (dump_file, result, 0);
1755 fprintf (dump_file, " for expression ");
1756 print_generic_expr (dump_file, val, 0);
1757 fprintf (dump_file, "\n");
1764 changed = set_ssa_val_to (lhs, result);
1765 if (TREE_CODE (result) == SSA_NAME
1766 && VN_INFO (result)->has_constants)
1768 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
1769 VN_INFO (lhs)->has_constants = true;
1774 changed = set_ssa_val_to (lhs, lhs);
1775 vn_reference_insert (op, lhs, gimple_vuse (stmt));
1782 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1783 and return true if the value number of the LHS has changed as a result. */
1786 visit_reference_op_store (tree lhs, tree op, gimple stmt)
1788 bool changed = false;
1790 bool resultsame = false;
1792 /* First we want to lookup using the *vuses* from the store and see
1793 if there the last store to this location with the same address
1796 The vuses represent the memory state before the store. If the
1797 memory state, address, and value of the store is the same as the
1798 last store to this location, then this store will produce the
1799 same memory state as that store.
1801 In this case the vdef versions for this store are value numbered to those
1802 vuse versions, since they represent the same memory state after
1805 Otherwise, the vdefs for the store are used when inserting into
1806 the table, since the store generates a new memory state. */
1808 result = vn_reference_lookup (lhs, gimple_vuse (stmt), false, NULL);
1812 if (TREE_CODE (result) == SSA_NAME)
1813 result = SSA_VAL (result);
1814 if (TREE_CODE (op) == SSA_NAME)
1816 resultsame = expressions_equal_p (result, op);
1819 if (!result || !resultsame)
1823 if (dump_file && (dump_flags & TDF_DETAILS))
1825 fprintf (dump_file, "No store match\n");
1826 fprintf (dump_file, "Value numbering store ");
1827 print_generic_expr (dump_file, lhs, 0);
1828 fprintf (dump_file, " to ");
1829 print_generic_expr (dump_file, op, 0);
1830 fprintf (dump_file, "\n");
1832 /* Have to set value numbers before insert, since insert is
1833 going to valueize the references in-place. */
1834 if ((vdef = gimple_vdef (stmt)))
1836 VN_INFO (vdef)->use_processed = true;
1837 changed |= set_ssa_val_to (vdef, vdef);
1840 /* Do not insert structure copies into the tables. */
1841 if (is_gimple_min_invariant (op)
1842 || is_gimple_reg (op))
1843 vn_reference_insert (lhs, op, vdef);
1847 /* We had a match, so value number the vdef to have the value
1848 number of the vuse it came from. */
1851 if (dump_file && (dump_flags & TDF_DETAILS))
1852 fprintf (dump_file, "Store matched earlier value,"
1853 "value numbering store vdefs to matching vuses.\n");
1855 def = gimple_vdef (stmt);
1856 use = gimple_vuse (stmt);
1858 VN_INFO (def)->use_processed = true;
1859 changed |= set_ssa_val_to (def, SSA_VAL (use));
1865 /* Visit and value number PHI, return true if the value number
1869 visit_phi (gimple phi)
1871 bool changed = false;
1873 tree sameval = VN_TOP;
1874 bool allsame = true;
1877 /* TODO: We could check for this in init_sccvn, and replace this
1878 with a gcc_assert. */
1879 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
1880 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1882 /* See if all non-TOP arguments have the same value. TOP is
1883 equivalent to everything, so we can ignore it. */
1884 for (i = 0; i < gimple_phi_num_args (phi); i++)
1886 tree def = PHI_ARG_DEF (phi, i);
1888 if (TREE_CODE (def) == SSA_NAME)
1889 def = SSA_VAL (def);
1892 if (sameval == VN_TOP)
1898 if (!expressions_equal_p (def, sameval))
1906 /* If all value numbered to the same value, the phi node has that
1910 if (is_gimple_min_invariant (sameval))
1912 VN_INFO (PHI_RESULT (phi))->has_constants = true;
1913 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1917 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1918 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1921 if (TREE_CODE (sameval) == SSA_NAME)
1922 return visit_copy (PHI_RESULT (phi), sameval);
1924 return set_ssa_val_to (PHI_RESULT (phi), sameval);
1927 /* Otherwise, see if it is equivalent to a phi node in this block. */
1928 result = vn_phi_lookup (phi);
1931 if (TREE_CODE (result) == SSA_NAME)
1932 changed = visit_copy (PHI_RESULT (phi), result);
1934 changed = set_ssa_val_to (PHI_RESULT (phi), result);
1938 vn_phi_insert (phi, PHI_RESULT (phi));
1939 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1940 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1941 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1947 /* Return true if EXPR contains constants. */
1950 expr_has_constants (tree expr)
1952 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1955 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1958 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1959 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1960 /* Constants inside reference ops are rarely interesting, but
1961 it can take a lot of looking to find them. */
1963 case tcc_declaration:
1966 return is_gimple_min_invariant (expr);
1971 /* Return true if STMT contains constants. */
1974 stmt_has_constants (gimple stmt)
1976 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1979 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
1981 case GIMPLE_UNARY_RHS:
1982 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
1984 case GIMPLE_BINARY_RHS:
1985 return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
1986 || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
1987 case GIMPLE_SINGLE_RHS:
1988 /* Constants inside reference ops are rarely interesting, but
1989 it can take a lot of looking to find them. */
1990 return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
1997 /* Replace SSA_NAMES in expr with their value numbers, and return the
1999 This is performed in place. */
2002 valueize_expr (tree expr)
2004 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2007 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2008 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2009 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2012 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
2013 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
2014 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
2015 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
2016 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
2017 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
2025 /* Simplify the binary expression RHS, and return the result if
2029 simplify_binary_expression (gimple stmt)
2031 tree result = NULL_TREE;
2032 tree op0 = gimple_assign_rhs1 (stmt);
2033 tree op1 = gimple_assign_rhs2 (stmt);
2035 /* This will not catch every single case we could combine, but will
2036 catch those with constants. The goal here is to simultaneously
2037 combine constants between expressions, but avoid infinite
2038 expansion of expressions during simplification. */
2039 if (TREE_CODE (op0) == SSA_NAME)
2041 if (VN_INFO (op0)->has_constants
2042 || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
2043 op0 = valueize_expr (vn_get_expr_for (op0));
2044 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
2045 op0 = SSA_VAL (op0);
2048 if (TREE_CODE (op1) == SSA_NAME)
2050 if (VN_INFO (op1)->has_constants)
2051 op1 = valueize_expr (vn_get_expr_for (op1));
2052 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
2053 op1 = SSA_VAL (op1);
2056 /* Avoid folding if nothing changed. */
2057 if (op0 == gimple_assign_rhs1 (stmt)
2058 && op1 == gimple_assign_rhs2 (stmt))
2061 fold_defer_overflow_warnings ();
2063 result = fold_binary (gimple_assign_rhs_code (stmt),
2064 TREE_TYPE (gimple_get_lhs (stmt)), op0, op1);
2066 STRIP_USELESS_TYPE_CONVERSION (result);
2068 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
2071 /* Make sure result is not a complex expression consisting
2072 of operators of operators (IE (a + b) + (a + c))
2073 Otherwise, we will end up with unbounded expressions if
2074 fold does anything at all. */
2075 if (result && valid_gimple_rhs_p (result))
2081 /* Simplify the unary expression RHS, and return the result if
2085 simplify_unary_expression (gimple stmt)
2087 tree result = NULL_TREE;
2088 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
2090 /* We handle some tcc_reference codes here that are all
2091 GIMPLE_ASSIGN_SINGLE codes. */
2092 if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
2093 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2094 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2095 op0 = TREE_OPERAND (op0, 0);
2097 if (TREE_CODE (op0) != SSA_NAME)
2101 if (VN_INFO (op0)->has_constants)
2102 op0 = valueize_expr (vn_get_expr_for (op0));
2103 else if (gimple_assign_cast_p (stmt)
2104 || gimple_assign_rhs_code (stmt) == REALPART_EXPR
2105 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2106 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR)
2108 /* We want to do tree-combining on conversion-like expressions.
2109 Make sure we feed only SSA_NAMEs or constants to fold though. */
2110 tree tem = valueize_expr (vn_get_expr_for (op0));
2111 if (UNARY_CLASS_P (tem)
2112 || BINARY_CLASS_P (tem)
2113 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
2114 || TREE_CODE (tem) == SSA_NAME
2115 || is_gimple_min_invariant (tem))
2119 /* Avoid folding if nothing changed, but remember the expression. */
2120 if (op0 == orig_op0)
2123 result = fold_unary_ignore_overflow (gimple_assign_rhs_code (stmt),
2124 gimple_expr_type (stmt), op0);
2127 STRIP_USELESS_TYPE_CONVERSION (result);
2128 if (valid_gimple_rhs_p (result))
2135 /* Try to simplify RHS using equivalences and constant folding. */
2138 try_to_simplify (gimple stmt)
2142 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
2143 in this case, there is no point in doing extra work. */
2144 if (gimple_assign_copy_p (stmt)
2145 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2148 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2150 case tcc_declaration:
2151 tem = get_symbol_constant_value (gimple_assign_rhs1 (stmt));
2157 /* Do not do full-blown reference lookup here, but simplify
2158 reads from constant aggregates. */
2159 tem = fold_const_aggregate_ref (gimple_assign_rhs1 (stmt));
2163 /* Fallthrough for some codes that can operate on registers. */
2164 if (!(TREE_CODE (gimple_assign_rhs1 (stmt)) == REALPART_EXPR
2165 || TREE_CODE (gimple_assign_rhs1 (stmt)) == IMAGPART_EXPR
2166 || TREE_CODE (gimple_assign_rhs1 (stmt)) == VIEW_CONVERT_EXPR))
2168 /* We could do a little more with unary ops, if they expand
2169 into binary ops, but it's debatable whether it is worth it. */
2171 return simplify_unary_expression (stmt);
2173 case tcc_comparison:
2175 return simplify_binary_expression (stmt);
2184 /* Visit and value number USE, return true if the value number
2188 visit_use (tree use)
2190 bool changed = false;
2191 gimple stmt = SSA_NAME_DEF_STMT (use);
2193 VN_INFO (use)->use_processed = true;
2195 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
2196 if (dump_file && (dump_flags & TDF_DETAILS)
2197 && !SSA_NAME_IS_DEFAULT_DEF (use))
2199 fprintf (dump_file, "Value numbering ");
2200 print_generic_expr (dump_file, use, 0);
2201 fprintf (dump_file, " stmt = ");
2202 print_gimple_stmt (dump_file, stmt, 0, 0);
2205 /* Handle uninitialized uses. */
2206 if (SSA_NAME_IS_DEFAULT_DEF (use))
2207 changed = set_ssa_val_to (use, use);
2210 if (gimple_code (stmt) == GIMPLE_PHI)
2211 changed = visit_phi (stmt);
2212 else if (!gimple_has_lhs (stmt)
2213 || gimple_has_volatile_ops (stmt)
2214 || stmt_could_throw_p (stmt))
2215 changed = defs_to_varying (stmt);
2216 else if (is_gimple_assign (stmt))
2218 tree lhs = gimple_assign_lhs (stmt);
2221 /* Shortcut for copies. Simplifying copies is pointless,
2222 since we copy the expression and value they represent. */
2223 if (gimple_assign_copy_p (stmt)
2224 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2225 && TREE_CODE (lhs) == SSA_NAME)
2227 changed = visit_copy (lhs, gimple_assign_rhs1 (stmt));
2230 simplified = try_to_simplify (stmt);
2233 if (dump_file && (dump_flags & TDF_DETAILS))
2235 fprintf (dump_file, "RHS ");
2236 print_gimple_expr (dump_file, stmt, 0, 0);
2237 fprintf (dump_file, " simplified to ");
2238 print_generic_expr (dump_file, simplified, 0);
2239 if (TREE_CODE (lhs) == SSA_NAME)
2240 fprintf (dump_file, " has constants %d\n",
2241 expr_has_constants (simplified));
2243 fprintf (dump_file, "\n");
2246 /* Setting value numbers to constants will occasionally
2247 screw up phi congruence because constants are not
2248 uniquely associated with a single ssa name that can be
2251 && is_gimple_min_invariant (simplified)
2252 && TREE_CODE (lhs) == SSA_NAME)
2254 VN_INFO (lhs)->expr = simplified;
2255 VN_INFO (lhs)->has_constants = true;
2256 changed = set_ssa_val_to (lhs, simplified);
2260 && TREE_CODE (simplified) == SSA_NAME
2261 && TREE_CODE (lhs) == SSA_NAME)
2263 changed = visit_copy (lhs, simplified);
2266 else if (simplified)
2268 if (TREE_CODE (lhs) == SSA_NAME)
2270 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
2271 /* We have to unshare the expression or else
2272 valuizing may change the IL stream. */
2273 VN_INFO (lhs)->expr = unshare_expr (simplified);
2276 else if (stmt_has_constants (stmt)
2277 && TREE_CODE (lhs) == SSA_NAME)
2278 VN_INFO (lhs)->has_constants = true;
2279 else if (TREE_CODE (lhs) == SSA_NAME)
2281 /* We reset expr and constantness here because we may
2282 have been value numbering optimistically, and
2283 iterating. They may become non-constant in this case,
2284 even if they were optimistically constant. */
2286 VN_INFO (lhs)->has_constants = false;
2287 VN_INFO (lhs)->expr = NULL_TREE;
2290 if ((TREE_CODE (lhs) == SSA_NAME
2291 /* We can substitute SSA_NAMEs that are live over
2292 abnormal edges with their constant value. */
2293 && !(gimple_assign_copy_p (stmt)
2294 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2296 && is_gimple_min_invariant (simplified))
2297 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2298 /* Stores or copies from SSA_NAMEs that are live over
2299 abnormal edges are a problem. */
2300 || (gimple_assign_single_p (stmt)
2301 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2302 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))))
2303 changed = defs_to_varying (stmt);
2304 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
2306 changed = visit_reference_op_store (lhs, gimple_assign_rhs1 (stmt), stmt);
2308 else if (TREE_CODE (lhs) == SSA_NAME)
2310 if ((gimple_assign_copy_p (stmt)
2311 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2313 && is_gimple_min_invariant (simplified)))
2315 VN_INFO (lhs)->has_constants = true;
2317 changed = set_ssa_val_to (lhs, simplified);
2319 changed = set_ssa_val_to (lhs, gimple_assign_rhs1 (stmt));
2323 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2325 case GIMPLE_UNARY_RHS:
2326 changed = visit_unary_op (lhs, stmt);
2328 case GIMPLE_BINARY_RHS:
2329 changed = visit_binary_op (lhs, stmt);
2331 case GIMPLE_SINGLE_RHS:
2332 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
2335 /* VOP-less references can go through unary case. */
2336 if ((gimple_assign_rhs_code (stmt) == REALPART_EXPR
2337 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR
2338 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR )
2339 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (stmt), 0)) == SSA_NAME)
2341 changed = visit_unary_op (lhs, stmt);
2345 case tcc_declaration:
2346 changed = visit_reference_op_load
2347 (lhs, gimple_assign_rhs1 (stmt), stmt);
2349 case tcc_expression:
2350 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
2352 changed = visit_unary_op (lhs, stmt);
2357 changed = defs_to_varying (stmt);
2361 changed = defs_to_varying (stmt);
2367 changed = defs_to_varying (stmt);
2369 else if (is_gimple_call (stmt))
2371 tree lhs = gimple_call_lhs (stmt);
2373 /* ??? We could try to simplify calls. */
2375 if (stmt_has_constants (stmt)
2376 && TREE_CODE (lhs) == SSA_NAME)
2377 VN_INFO (lhs)->has_constants = true;
2378 else if (TREE_CODE (lhs) == SSA_NAME)
2380 /* We reset expr and constantness here because we may
2381 have been value numbering optimistically, and
2382 iterating. They may become non-constant in this case,
2383 even if they were optimistically constant. */
2384 VN_INFO (lhs)->has_constants = false;
2385 VN_INFO (lhs)->expr = NULL_TREE;
2388 if (TREE_CODE (lhs) == SSA_NAME
2389 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
2390 changed = defs_to_varying (stmt);
2391 /* ??? We should handle stores from calls. */
2392 else if (TREE_CODE (lhs) == SSA_NAME)
2394 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2395 changed = visit_reference_op_call (lhs, stmt);
2397 changed = defs_to_varying (stmt);
2400 changed = defs_to_varying (stmt);
2407 /* Compare two operands by reverse postorder index */
2410 compare_ops (const void *pa, const void *pb)
2412 const tree opa = *((const tree *)pa);
2413 const tree opb = *((const tree *)pb);
2414 gimple opstmta = SSA_NAME_DEF_STMT (opa);
2415 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
2419 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
2421 else if (gimple_nop_p (opstmta))
2423 else if (gimple_nop_p (opstmtb))
2426 bba = gimple_bb (opstmta);
2427 bbb = gimple_bb (opstmtb);
2438 if (gimple_code (opstmta) == GIMPLE_PHI
2439 && gimple_code (opstmtb) == GIMPLE_PHI)
2441 else if (gimple_code (opstmta) == GIMPLE_PHI)
2443 else if (gimple_code (opstmtb) == GIMPLE_PHI)
2445 return gimple_uid (opstmta) - gimple_uid (opstmtb);
2447 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
2450 /* Sort an array containing members of a strongly connected component
2451 SCC so that the members are ordered by RPO number.
2452 This means that when the sort is complete, iterating through the
2453 array will give you the members in RPO order. */
2456 sort_scc (VEC (tree, heap) *scc)
2458 qsort (VEC_address (tree, scc),
2459 VEC_length (tree, scc),
2464 /* Process a strongly connected component in the SSA graph. */
2467 process_scc (VEC (tree, heap) *scc)
2469 /* If the SCC has a single member, just visit it. */
2471 if (VEC_length (tree, scc) == 1)
2473 tree use = VEC_index (tree, scc, 0);
2474 if (!VN_INFO (use)->use_processed)
2481 unsigned int iterations = 0;
2482 bool changed = true;
2484 /* Iterate over the SCC with the optimistic table until it stops
2486 current_info = optimistic_info;
2491 /* As we are value-numbering optimistically we have to
2492 clear the expression tables and the simplified expressions
2493 in each iteration until we converge. */
2494 htab_empty (optimistic_info->nary);
2495 htab_empty (optimistic_info->phis);
2496 htab_empty (optimistic_info->references);
2497 obstack_free (&optimistic_info->nary_obstack, NULL);
2498 gcc_obstack_init (&optimistic_info->nary_obstack);
2499 empty_alloc_pool (optimistic_info->phis_pool);
2500 empty_alloc_pool (optimistic_info->references_pool);
2501 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2502 VN_INFO (var)->expr = NULL_TREE;
2503 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2504 changed |= visit_use (var);
2507 statistics_histogram_event (cfun, "SCC iterations", iterations);
2509 /* Finally, visit the SCC once using the valid table. */
2510 current_info = valid_info;
2511 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
2516 DEF_VEC_O(ssa_op_iter);
2517 DEF_VEC_ALLOC_O(ssa_op_iter,heap);
2519 /* Pop the components of the found SCC for NAME off the SCC stack
2520 and process them. Returns true if all went well, false if
2521 we run into resource limits. */
2524 extract_and_process_scc_for_name (tree name)
2526 VEC (tree, heap) *scc = NULL;
2529 /* Found an SCC, pop the components off the SCC stack and
2533 x = VEC_pop (tree, sccstack);
2535 VN_INFO (x)->on_sccstack = false;
2536 VEC_safe_push (tree, heap, scc, x);
2537 } while (x != name);
2539 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
2540 if (VEC_length (tree, scc)
2541 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
2544 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
2545 "SCC size %u exceeding %u\n", VEC_length (tree, scc),
2546 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
2550 if (VEC_length (tree, scc) > 1)
2553 if (dump_file && (dump_flags & TDF_DETAILS))
2554 print_scc (dump_file, scc);
2558 VEC_free (tree, heap, scc);
2563 /* Depth first search on NAME to discover and process SCC's in the SSA
2565 Execution of this algorithm relies on the fact that the SCC's are
2566 popped off the stack in topological order.
2567 Returns true if successful, false if we stopped processing SCC's due
2568 to resource constraints. */
2573 VEC(ssa_op_iter, heap) *itervec = NULL;
2574 VEC(tree, heap) *namevec = NULL;
2575 use_operand_p usep = NULL;
2582 VN_INFO (name)->dfsnum = next_dfs_num++;
2583 VN_INFO (name)->visited = true;
2584 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
2586 VEC_safe_push (tree, heap, sccstack, name);
2587 VN_INFO (name)->on_sccstack = true;
2588 defstmt = SSA_NAME_DEF_STMT (name);
2590 /* Recursively DFS on our operands, looking for SCC's. */
2591 if (!gimple_nop_p (defstmt))
2593 /* Push a new iterator. */
2594 if (gimple_code (defstmt) == GIMPLE_PHI)
2595 usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
2597 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
2600 clear_and_done_ssa_iter (&iter);
2604 /* If we are done processing uses of a name, go up the stack
2605 of iterators and process SCCs as we found them. */
2606 if (op_iter_done (&iter))
2608 /* See if we found an SCC. */
2609 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
2610 if (!extract_and_process_scc_for_name (name))
2612 VEC_free (tree, heap, namevec);
2613 VEC_free (ssa_op_iter, heap, itervec);
2617 /* Check if we are done. */
2618 if (VEC_empty (tree, namevec))
2620 VEC_free (tree, heap, namevec);
2621 VEC_free (ssa_op_iter, heap, itervec);
2625 /* Restore the last use walker and continue walking there. */
2627 name = VEC_pop (tree, namevec);
2628 memcpy (&iter, VEC_last (ssa_op_iter, itervec),
2629 sizeof (ssa_op_iter));
2630 VEC_pop (ssa_op_iter, itervec);
2631 goto continue_walking;
2634 use = USE_FROM_PTR (usep);
2636 /* Since we handle phi nodes, we will sometimes get
2637 invariants in the use expression. */
2638 if (TREE_CODE (use) == SSA_NAME)
2640 if (! (VN_INFO (use)->visited))
2642 /* Recurse by pushing the current use walking state on
2643 the stack and starting over. */
2644 VEC_safe_push(ssa_op_iter, heap, itervec, &iter);
2645 VEC_safe_push(tree, heap, namevec, name);
2650 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
2651 VN_INFO (use)->low);
2653 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
2654 && VN_INFO (use)->on_sccstack)
2656 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
2657 VN_INFO (name)->low);
2661 usep = op_iter_next_use (&iter);
2665 /* Allocate a value number table. */
2668 allocate_vn_table (vn_tables_t table)
2670 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
2671 table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
2672 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
2675 gcc_obstack_init (&table->nary_obstack);
2676 table->phis_pool = create_alloc_pool ("VN phis",
2677 sizeof (struct vn_phi_s),
2679 table->references_pool = create_alloc_pool ("VN references",
2680 sizeof (struct vn_reference_s),
2684 /* Free a value number table. */
2687 free_vn_table (vn_tables_t table)
2689 htab_delete (table->phis);
2690 htab_delete (table->nary);
2691 htab_delete (table->references);
2692 obstack_free (&table->nary_obstack, NULL);
2693 free_alloc_pool (table->phis_pool);
2694 free_alloc_pool (table->references_pool);
2702 int *rpo_numbers_temp;
2704 calculate_dominance_info (CDI_DOMINATORS);
2706 constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
2709 constant_value_ids = BITMAP_ALLOC (NULL);
2714 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
2715 /* VEC_alloc doesn't actually grow it to the right size, it just
2716 preallocates the space to do so. */
2717 VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
2718 gcc_obstack_init (&vn_ssa_aux_obstack);
2720 shared_lookup_phiargs = NULL;
2721 shared_lookup_references = NULL;
2722 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2723 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2724 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
2726 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
2727 the i'th block in RPO order is bb. We want to map bb's to RPO
2728 numbers, so we need to rearrange this array. */
2729 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
2730 rpo_numbers[rpo_numbers_temp[j]] = j;
2732 XDELETE (rpo_numbers_temp);
2734 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
2736 /* Create the VN_INFO structures, and initialize value numbers to
2738 for (i = 0; i < num_ssa_names; i++)
2740 tree name = ssa_name (i);
2743 VN_INFO_GET (name)->valnum = VN_TOP;
2744 VN_INFO (name)->expr = NULL_TREE;
2745 VN_INFO (name)->value_id = 0;
2749 renumber_gimple_stmt_uids ();
2751 /* Create the valid and optimistic value numbering tables. */
2752 valid_info = XCNEW (struct vn_tables_s);
2753 allocate_vn_table (valid_info);
2754 optimistic_info = XCNEW (struct vn_tables_s);
2755 allocate_vn_table (optimistic_info);
2763 htab_delete (constant_to_value_id);
2764 BITMAP_FREE (constant_value_ids);
2765 VEC_free (tree, heap, shared_lookup_phiargs);
2766 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
2767 XDELETEVEC (rpo_numbers);
2769 for (i = 0; i < num_ssa_names; i++)
2771 tree name = ssa_name (i);
2773 && VN_INFO (name)->needs_insertion)
2774 release_ssa_name (name);
2776 obstack_free (&vn_ssa_aux_obstack, NULL);
2777 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
2779 VEC_free (tree, heap, sccstack);
2780 free_vn_table (valid_info);
2781 XDELETE (valid_info);
2782 free_vn_table (optimistic_info);
2783 XDELETE (optimistic_info);
2786 /* Set the value ids in the valid hash tables. */
2789 set_hashtable_value_ids (void)
2796 /* Now set the value ids of the things we had put in the hash
2799 FOR_EACH_HTAB_ELEMENT (valid_info->nary,
2800 vno, vn_nary_op_t, hi)
2804 if (TREE_CODE (vno->result) == SSA_NAME)
2805 vno->value_id = VN_INFO (vno->result)->value_id;
2806 else if (is_gimple_min_invariant (vno->result))
2807 vno->value_id = get_or_alloc_constant_value_id (vno->result);
2811 FOR_EACH_HTAB_ELEMENT (valid_info->phis,
2816 if (TREE_CODE (vp->result) == SSA_NAME)
2817 vp->value_id = VN_INFO (vp->result)->value_id;
2818 else if (is_gimple_min_invariant (vp->result))
2819 vp->value_id = get_or_alloc_constant_value_id (vp->result);
2823 FOR_EACH_HTAB_ELEMENT (valid_info->references,
2824 vr, vn_reference_t, hi)
2828 if (TREE_CODE (vr->result) == SSA_NAME)
2829 vr->value_id = VN_INFO (vr->result)->value_id;
2830 else if (is_gimple_min_invariant (vr->result))
2831 vr->value_id = get_or_alloc_constant_value_id (vr->result);
2836 /* Do SCCVN. Returns true if it finished, false if we bailed out
2837 due to resource constraints. */
2840 run_scc_vn (bool may_insert_arg)
2844 bool changed = true;
2846 may_insert = may_insert_arg;
2849 current_info = valid_info;
2851 for (param = DECL_ARGUMENTS (current_function_decl);
2853 param = TREE_CHAIN (param))
2855 if (gimple_default_def (cfun, param) != NULL)
2857 tree def = gimple_default_def (cfun, param);
2858 VN_INFO (def)->valnum = def;
2862 for (i = 1; i < num_ssa_names; ++i)
2864 tree name = ssa_name (i);
2866 && VN_INFO (name)->visited == false
2867 && !has_zero_uses (name))
2876 /* Initialize the value ids. */
2878 for (i = 1; i < num_ssa_names; ++i)
2880 tree name = ssa_name (i);
2884 info = VN_INFO (name);
2885 if (info->valnum == name)
2886 info->value_id = get_next_value_id ();
2887 else if (is_gimple_min_invariant (info->valnum))
2888 info->value_id = get_or_alloc_constant_value_id (info->valnum);
2891 /* Propagate until they stop changing. */
2895 for (i = 1; i < num_ssa_names; ++i)
2897 tree name = ssa_name (i);
2901 info = VN_INFO (name);
2902 if (TREE_CODE (info->valnum) == SSA_NAME
2903 && info->valnum != name
2904 && info->value_id != VN_INFO (info->valnum)->value_id)
2907 info->value_id = VN_INFO (info->valnum)->value_id;
2912 set_hashtable_value_ids ();
2914 if (dump_file && (dump_flags & TDF_DETAILS))
2916 fprintf (dump_file, "Value numbers:\n");
2917 for (i = 0; i < num_ssa_names; i++)
2919 tree name = ssa_name (i);
2921 && VN_INFO (name)->visited
2922 && SSA_VAL (name) != name)
2924 print_generic_expr (dump_file, name, 0);
2925 fprintf (dump_file, " = ");
2926 print_generic_expr (dump_file, SSA_VAL (name), 0);
2927 fprintf (dump_file, "\n");
2936 /* Return the maximum value id we have ever seen. */
2939 get_max_value_id (void)
2941 return next_value_id;
2944 /* Return the next unique value id. */
2947 get_next_value_id (void)
2949 return next_value_id++;
2953 /* Compare two expressions E1 and E2 and return true if they are equal. */
2956 expressions_equal_p (tree e1, tree e2)
2958 /* The obvious case. */
2962 /* If only one of them is null, they cannot be equal. */
2966 /* Recurse on elements of lists. */
2967 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
2971 for (lop1 = e1, lop2 = e2;
2973 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
2977 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
2983 /* Now perform the actual comparison. */
2984 if (TREE_CODE (e1) == TREE_CODE (e2)
2985 && operand_equal_p (e1, e2, OEP_PURE_SAME))
2992 /* Return true if the nary operation NARY may trap. This is a copy
2993 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
2996 vn_nary_may_trap (vn_nary_op_t nary)
3000 bool honor_nans = false;
3001 bool honor_snans = false;
3002 bool fp_operation = false;
3003 bool honor_trapv = false;
3007 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
3008 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
3009 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
3012 fp_operation = FLOAT_TYPE_P (type);
3015 honor_nans = flag_trapping_math && !flag_finite_math_only;
3016 honor_snans = flag_signaling_nans != 0;
3018 else if (INTEGRAL_TYPE_P (type)
3019 && TYPE_OVERFLOW_TRAPS (type))
3023 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
3025 honor_nans, honor_snans, rhs2,
3031 for (i = 0; i < nary->length; ++i)
3032 if (tree_could_trap_p (nary->op[i]))