1 /* SCC value numbering for trees
2 Copyright (C) 2006, 2007
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"
32 #include "tree-gimple.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"
45 #include "tree-ssa-propagate.h"
46 #include "tree-ssa-sccvn.h"
48 /* This algorithm is based on the SCC algorithm presented by Keith
49 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
50 (http://citeseer.ist.psu.edu/41805.html). In
51 straight line code, it is equivalent to a regular hash based value
52 numbering that is performed in reverse postorder.
54 For code with cycles, there are two alternatives, both of which
55 require keeping the hashtables separate from the actual list of
56 value numbers for SSA names.
58 1. Iterate value numbering in an RPO walk of the blocks, removing
59 all the entries from the hashtable after each iteration (but
60 keeping the SSA name->value number mapping between iterations).
61 Iterate until it does not change.
63 2. Perform value numbering as part of an SCC walk on the SSA graph,
64 iterating only the cycles in the SSA graph until they do not change
65 (using a separate, optimistic hashtable for value numbering the SCC
68 The second is not just faster in practice (because most SSA graph
69 cycles do not involve all the variables in the graph), it also has
72 One of these nice properties is that when we pop an SCC off the
73 stack, we are guaranteed to have processed all the operands coming from
74 *outside of that SCC*, so we do not need to do anything special to
75 ensure they have value numbers.
77 Another nice property is that the SCC walk is done as part of a DFS
78 of the SSA graph, which makes it easy to perform combining and
79 simplifying operations at the same time.
81 The code below is deliberately written in a way that makes it easy
82 to separate the SCC walk from the other work it does.
84 In order to propagate constants through the code, we track which
85 expressions contain constants, and use those while folding. In
86 theory, we could also track expressions whose value numbers are
87 replaced, in case we end up folding based on expression
90 In order to value number memory, we assign value numbers to vuses.
91 This enables us to note that, for example, stores to the same
92 address of the same value from the same starting memory states are
96 1. We can iterate only the changing portions of the SCC's, but
97 I have not seen an SCC big enough for this to be a win.
98 2. If you differentiate between phi nodes for loops and phi nodes
99 for if-then-else, you can properly consider phi nodes in different
100 blocks for equivalence.
101 3. We could value number vuses in more cases, particularly, whole
105 /* The set of hashtables and alloc_pool's for their items. */
107 typedef struct vn_tables_s
113 alloc_pool unary_op_pool;
114 alloc_pool binary_op_pool;
115 alloc_pool phis_pool;
116 alloc_pool references_pool;
119 /* Binary operations in the hashtable consist of two operands, an
120 opcode, and a type. Result is the value number of the operation,
121 and hashcode is stored to avoid having to calculate it
124 typedef struct vn_binary_op_s
126 enum tree_code opcode;
133 typedef const struct vn_binary_op_s *const_vn_binary_op_t;
135 /* Unary operations in the hashtable consist of a single operand, an
136 opcode, and a type. Result is the value number of the operation,
137 and hashcode is stored to avoid having to calculate it repeatedly. */
139 typedef struct vn_unary_op_s
141 enum tree_code opcode;
147 typedef const struct vn_unary_op_s *const_vn_unary_op_t;
149 /* Phi nodes in the hashtable consist of their non-VN_TOP phi
150 arguments, and the basic block the phi is in. Result is the value
151 number of the operation, and hashcode is stored to avoid having to
152 calculate it repeatedly. Phi nodes not in the same block are never
153 considered equivalent. */
155 typedef struct vn_phi_s
157 VEC (tree, heap) *phiargs;
162 typedef const struct vn_phi_s *const_vn_phi_t;
164 /* Reference operands only exist in reference operations structures.
165 They consist of an opcode, type, and some number of operands. For
166 a given opcode, some, all, or none of the operands may be used.
167 The operands are there to store the information that makes up the
168 portion of the addressing calculation that opcode performs. */
170 typedef struct vn_reference_op_struct
172 enum tree_code opcode;
178 typedef vn_reference_op_s *vn_reference_op_t;
179 typedef const vn_reference_op_s *const_vn_reference_op_t;
181 DEF_VEC_O(vn_reference_op_s);
182 DEF_VEC_ALLOC_O(vn_reference_op_s, heap);
184 /* A reference operation in the hashtable is representation as a
185 collection of vuses, representing the memory state at the time of
186 the operation, and a collection of operands that make up the
187 addressing calculation. If two vn_reference_t's have the same set
188 of operands, they access the same memory location. We also store
189 the resulting value number, and the hashcode. The vuses are
190 always stored in order sorted by ssa name version. */
192 typedef struct vn_reference_s
194 VEC (tree, gc) *vuses;
195 VEC (vn_reference_op_s, heap) *operands;
199 typedef const struct vn_reference_s *const_vn_reference_t;
201 /* Valid hashtables storing information we have proven to be
204 static vn_tables_t valid_info;
206 /* Optimistic hashtables storing information we are making assumptions about
207 during iterations. */
209 static vn_tables_t optimistic_info;
211 /* PRE hashtables storing information about mapping from expressions to
214 static vn_tables_t pre_info;
216 /* Pointer to the set of hashtables that is currently being used.
217 Should always point to either the optimistic_info, or the
220 static vn_tables_t current_info;
223 /* Reverse post order index for each basic block. */
225 static int *rpo_numbers;
227 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
229 /* This represents the top of the VN lattice, which is the universal
234 /* Next DFS number and the stack for strongly connected component
237 static unsigned int next_dfs_num;
238 static VEC (tree, heap) *sccstack;
240 DEF_VEC_P(vn_ssa_aux_t);
241 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
243 /* Table of vn_ssa_aux_t's, one per ssa_name. */
245 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
247 /* Return the value numbering information for a given SSA name. */
252 return VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
253 SSA_NAME_VERSION (name));
256 /* Set the value numbering info for a given SSA name to a given
260 VN_INFO_SET (tree name, vn_ssa_aux_t value)
262 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
263 SSA_NAME_VERSION (name), value);
266 /* Get the value numbering info for a given SSA name, creating it if
267 it does not exist. */
270 VN_INFO_GET (tree name)
272 vn_ssa_aux_t newinfo = XCNEW (struct vn_ssa_aux);
273 if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
274 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
275 SSA_NAME_VERSION (name) + 1);
276 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
277 SSA_NAME_VERSION (name), newinfo);
282 /* Compare two reference operands P1 and P2 for equality. return true if
283 they are equal, and false otherwise. */
286 vn_reference_op_eq (const void *p1, const void *p2)
288 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
289 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
290 return vro1->opcode == vro2->opcode
291 && vro1->type == vro2->type
292 && expressions_equal_p (vro1->op0, vro2->op0)
293 && expressions_equal_p (vro1->op1, vro2->op1)
294 && expressions_equal_p (vro1->op2, vro2->op2);
297 /* Compute the hash for a reference operand VRO1 */
300 vn_reference_op_compute_hash (const vn_reference_op_t vro1)
302 return iterative_hash_expr (vro1->op0, vro1->opcode)
303 + iterative_hash_expr (vro1->op1, vro1->opcode)
304 + iterative_hash_expr (vro1->op2, vro1->opcode);
307 /* Return the hashcode for a given reference operation P1. */
310 vn_reference_hash (const void *p1)
312 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
313 return vr1->hashcode;
316 /* Compute a hash for the reference operation VR1 and return it. */
318 static inline hashval_t
319 vn_reference_compute_hash (const vn_reference_t vr1)
321 hashval_t result = 0;
324 vn_reference_op_t vro;
326 for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
327 result += iterative_hash_expr (v, 0);
328 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
329 result += vn_reference_op_compute_hash (vro);
334 /* Return true if reference operations P1 and P2 are equivalent. This
335 means they have the same set of operands and vuses. */
338 vn_reference_eq (const void *p1, const void *p2)
342 vn_reference_op_t vro;
344 const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
345 const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
347 if (vr1->vuses == vr2->vuses
348 && vr1->operands == vr2->operands)
351 /* Impossible for them to be equivalent if they have different
353 if (VEC_length (tree, vr1->vuses) != VEC_length (tree, vr2->vuses))
356 /* We require that address operands be canonicalized in a way that
357 two memory references will have the same operands if they are
359 if (VEC_length (vn_reference_op_s, vr1->operands)
360 != VEC_length (vn_reference_op_s, vr2->operands))
363 /* The memory state is more often different than the address of the
364 store/load, so check it first. */
365 for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
367 if (VEC_index (tree, vr2->vuses, i) != v)
371 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
373 if (!vn_reference_op_eq (VEC_index (vn_reference_op_s, vr2->operands, i),
380 /* Place the vuses from STMT into *result */
383 vuses_to_vec (tree stmt, VEC (tree, gc) **result)
391 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
392 VEC_safe_push (tree, gc, *result, vuse);
394 if (VEC_length (tree, *result) > 1)
395 sort_vuses (*result);
399 /* Copy the VUSE names in STMT into a vector, and return
403 copy_vuses_from_stmt (tree stmt)
405 VEC (tree, gc) *vuses = NULL;
407 vuses_to_vec (stmt, &vuses);
412 /* Place the vdefs from STMT into *result */
415 vdefs_to_vec (tree stmt, VEC (tree, gc) **result)
423 FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, iter, SSA_OP_VIRTUAL_DEFS)
424 VEC_safe_push (tree, gc, *result, vdef);
426 if (VEC_length (tree, *result) > 1)
427 sort_vuses (*result);
430 /* Copy the names of vdef results in STMT into a vector, and return
433 static VEC (tree, gc) *
434 copy_vdefs_from_stmt (tree stmt)
436 VEC (tree, gc) *vdefs = NULL;
438 vdefs_to_vec (stmt, &vdefs);
443 /* Place for shared_v{uses/defs}_from_stmt to shove vuses/vdefs. */
444 static VEC (tree, gc) *shared_lookup_vops;
446 /* Copy the virtual uses from STMT into SHARED_LOOKUP_VOPS.
447 This function will overwrite the current SHARED_LOOKUP_VOPS
451 shared_vuses_from_stmt (tree stmt)
453 VEC_truncate (tree, shared_lookup_vops, 0);
454 vuses_to_vec (stmt, &shared_lookup_vops);
456 return shared_lookup_vops;
459 /* Copy the operations present in load/store/call REF into RESULT, a vector of
460 vn_reference_op_s's. */
463 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
465 /* Calls are different from all other reference operations. */
466 if (TREE_CODE (ref) == CALL_EXPR)
468 vn_reference_op_s temp;
470 call_expr_arg_iterator iter;
473 /* Copy the call_expr opcode, type, function being called, and
475 memset (&temp, 0, sizeof (temp));
476 temp.type = TREE_TYPE (ref);
477 temp.opcode = CALL_EXPR;
478 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
480 callfn = get_callee_fndecl (ref);
482 callfn = CALL_EXPR_FN (ref);
483 temp.type = TREE_TYPE (callfn);
484 temp.opcode = TREE_CODE (callfn);
486 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
488 FOR_EACH_CALL_EXPR_ARG (callarg, iter, ref)
490 memset (&temp, 0, sizeof (temp));
491 temp.type = TREE_TYPE (callarg);
492 temp.opcode = TREE_CODE (callarg);
494 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
499 /* For non-calls, store the information that makes up the address. */
503 vn_reference_op_s temp;
505 memset (&temp, 0, sizeof (temp));
506 temp.type = TREE_TYPE (ref);
507 temp.opcode = TREE_CODE (ref);
511 case ALIGN_INDIRECT_REF:
512 case MISALIGNED_INDIRECT_REF:
514 /* The only operand is the address, which gets its own
515 vn_reference_op_s structure. */
518 /* Record bits and position. */
519 temp.op0 = TREE_OPERAND (ref, 1);
520 temp.op1 = TREE_OPERAND (ref, 2);
523 /* Record field as operand. */
524 temp.op0 = TREE_OPERAND (ref, 1);
526 case ARRAY_RANGE_REF:
528 /* Record index as operand. */
529 temp.op0 = TREE_OPERAND (ref, 1);
530 temp.op1 = TREE_OPERAND (ref, 3);
545 /* These are only interesting for their operands, their
546 existence, and their type. They will never be the last
547 ref in the chain of references (IE they require an
548 operand), so we don't have to put anything
549 for op* as it will be handled by the iteration */
552 case VIEW_CONVERT_EXPR:
559 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
561 if (REFERENCE_CLASS_P (ref) || TREE_CODE (ref) == ADDR_EXPR)
562 ref = TREE_OPERAND (ref, 0);
568 /* Create a vector of vn_reference_op_s structures from REF, a
569 REFERENCE_CLASS_P tree. The vector is not shared. */
571 static VEC(vn_reference_op_s, heap) *
572 create_reference_ops_from_ref (tree ref)
574 VEC (vn_reference_op_s, heap) *result = NULL;
576 copy_reference_ops_from_ref (ref, &result);
580 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
582 /* Create a vector of vn_reference_op_s structures from REF, a
583 REFERENCE_CLASS_P tree. The vector is shared among all callers of
586 static VEC(vn_reference_op_s, heap) *
587 shared_reference_ops_from_ref (tree ref)
591 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
592 copy_reference_ops_from_ref (ref, &shared_lookup_references);
593 return shared_lookup_references;
597 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
598 structures into their value numbers. This is done in-place, and
599 the vector passed in is returned. */
601 static VEC (vn_reference_op_s, heap) *
602 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
604 vn_reference_op_t vro;
607 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
609 if (vro->opcode == SSA_NAME
610 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
611 vro->op0 = SSA_VAL (vro->op0);
617 /* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
618 their value numbers. This is done in-place, and the vector passed
621 static VEC (tree, gc) *
622 valueize_vuses (VEC (tree, gc) *orig)
624 bool made_replacement = false;
628 for (i = 0; VEC_iterate (tree, orig, i, vuse); i++)
630 if (vuse != SSA_VAL (vuse))
632 made_replacement = true;
633 VEC_replace (tree, orig, i, SSA_VAL (vuse));
637 if (made_replacement && VEC_length (tree, orig) > 1)
643 /* Lookup OP in the current hash table, and return the resulting
644 value number if it exists in the hash table. Return NULL_TREE if
645 it does not exist in the hash table. */
648 vn_reference_lookup (tree op, VEC (tree, gc) *vuses)
651 struct vn_reference_s vr1;
653 vr1.vuses = valueize_vuses (vuses);
654 vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
655 vr1.hashcode = vn_reference_compute_hash (&vr1);
656 slot = htab_find_slot_with_hash (current_info->references, &vr1, vr1.hashcode,
661 return ((vn_reference_t)*slot)->result;
664 /* Insert OP into the current hash table with a value number of
668 vn_reference_insert (tree op, tree result, VEC (tree, gc) *vuses)
673 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
675 vr1->vuses = valueize_vuses (vuses);
676 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
677 vr1->hashcode = vn_reference_compute_hash (vr1);
678 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
680 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
683 /* Because we lookup stores using vuses, and value number failures
684 using the vdefs (see visit_reference_op_store for how and why),
685 it's possible that on failure we may try to insert an already
686 inserted store. This is not wrong, there is no ssa name for a
687 store that we could use as a differentiator anyway. Thus, unlike
688 the other lookup functions, you cannot gcc_assert (!*slot)
696 /* Return the stored hashcode for a unary operation. */
699 vn_unary_op_hash (const void *p1)
701 const_vn_unary_op_t const vuo1 = (const_vn_unary_op_t) p1;
702 return vuo1->hashcode;
705 /* Hash a unary operation P1 and return the result. */
707 static inline hashval_t
708 vn_unary_op_compute_hash (const vn_unary_op_t vuo1)
710 return iterative_hash_expr (vuo1->op0, vuo1->opcode);
713 /* Return true if P1 and P2, two unary operations, are equivalent. */
716 vn_unary_op_eq (const void *p1, const void *p2)
718 const_vn_unary_op_t const vuo1 = (const_vn_unary_op_t) p1;
719 const_vn_unary_op_t const vuo2 = (const_vn_unary_op_t) p2;
720 return vuo1->opcode == vuo2->opcode
721 && vuo1->type == vuo2->type
722 && expressions_equal_p (vuo1->op0, vuo2->op0);
725 /* Lookup OP in the current hash table, and return the resulting
726 value number if it exists in the hash table. Return NULL_TREE if
727 it does not exist in the hash table. */
730 vn_unary_op_lookup (tree op)
733 struct vn_unary_op_s vuo1;
735 vuo1.opcode = TREE_CODE (op);
736 vuo1.type = TREE_TYPE (op);
737 vuo1.op0 = TREE_OPERAND (op, 0);
739 if (TREE_CODE (vuo1.op0) == SSA_NAME)
740 vuo1.op0 = SSA_VAL (vuo1.op0);
742 vuo1.hashcode = vn_unary_op_compute_hash (&vuo1);
743 slot = htab_find_slot_with_hash (current_info->unary, &vuo1, vuo1.hashcode,
747 return ((vn_unary_op_t)*slot)->result;
750 /* Insert OP into the current hash table with a value number of
754 vn_unary_op_insert (tree op, tree result)
757 vn_unary_op_t vuo1 = (vn_unary_op_t) pool_alloc (current_info->unary_op_pool);
759 vuo1->opcode = TREE_CODE (op);
760 vuo1->type = TREE_TYPE (op);
761 vuo1->op0 = TREE_OPERAND (op, 0);
762 vuo1->result = result;
764 if (TREE_CODE (vuo1->op0) == SSA_NAME)
765 vuo1->op0 = SSA_VAL (vuo1->op0);
767 vuo1->hashcode = vn_unary_op_compute_hash (vuo1);
768 slot = htab_find_slot_with_hash (current_info->unary, vuo1, vuo1->hashcode,
774 /* Compute and return the hash value for binary operation VBO1. */
776 static inline hashval_t
777 vn_binary_op_compute_hash (const vn_binary_op_t vbo1)
779 return iterative_hash_expr (vbo1->op0, vbo1->opcode)
780 + iterative_hash_expr (vbo1->op1, vbo1->opcode);
783 /* Return the computed hashcode for binary operation P1. */
786 vn_binary_op_hash (const void *p1)
788 const_vn_binary_op_t const vbo1 = (const_vn_binary_op_t) p1;
789 return vbo1->hashcode;
792 /* Compare binary operations P1 and P2 and return true if they are
796 vn_binary_op_eq (const void *p1, const void *p2)
798 const_vn_binary_op_t const vbo1 = (const_vn_binary_op_t) p1;
799 const_vn_binary_op_t const vbo2 = (const_vn_binary_op_t) p2;
800 return vbo1->opcode == vbo2->opcode
801 && vbo1->type == vbo2->type
802 && expressions_equal_p (vbo1->op0, vbo2->op0)
803 && expressions_equal_p (vbo1->op1, vbo2->op1);
806 /* Lookup OP in the current hash table, and return the resulting
807 value number if it exists in the hash table. Return NULL_TREE if
808 it does not exist in the hash table. */
811 vn_binary_op_lookup (tree op)
814 struct vn_binary_op_s vbo1;
816 vbo1.opcode = TREE_CODE (op);
817 vbo1.type = TREE_TYPE (op);
818 vbo1.op0 = TREE_OPERAND (op, 0);
819 vbo1.op1 = TREE_OPERAND (op, 1);
821 if (TREE_CODE (vbo1.op0) == SSA_NAME)
822 vbo1.op0 = SSA_VAL (vbo1.op0);
823 if (TREE_CODE (vbo1.op1) == SSA_NAME)
824 vbo1.op1 = SSA_VAL (vbo1.op1);
826 if (tree_swap_operands_p (vbo1.op0, vbo1.op1, false)
827 && commutative_tree_code (vbo1.opcode))
829 tree temp = vbo1.op0;
834 vbo1.hashcode = vn_binary_op_compute_hash (&vbo1);
835 slot = htab_find_slot_with_hash (current_info->binary, &vbo1, vbo1.hashcode,
839 return ((vn_binary_op_t)*slot)->result;
842 /* Insert OP into the current hash table with a value number of
846 vn_binary_op_insert (tree op, tree result)
850 vbo1 = (vn_binary_op_t) pool_alloc (current_info->binary_op_pool);
852 vbo1->opcode = TREE_CODE (op);
853 vbo1->type = TREE_TYPE (op);
854 vbo1->op0 = TREE_OPERAND (op, 0);
855 vbo1->op1 = TREE_OPERAND (op, 1);
856 vbo1->result = result;
858 if (TREE_CODE (vbo1->op0) == SSA_NAME)
859 vbo1->op0 = SSA_VAL (vbo1->op0);
860 if (TREE_CODE (vbo1->op1) == SSA_NAME)
861 vbo1->op1 = SSA_VAL (vbo1->op1);
863 if (tree_swap_operands_p (vbo1->op0, vbo1->op1, false)
864 && commutative_tree_code (vbo1->opcode))
866 tree temp = vbo1->op0;
867 vbo1->op0 = vbo1->op1;
870 vbo1->hashcode = vn_binary_op_compute_hash (vbo1);
871 slot = htab_find_slot_with_hash (current_info->binary, vbo1, vbo1->hashcode,
878 /* Compute a hashcode for PHI operation VP1 and return it. */
880 static inline hashval_t
881 vn_phi_compute_hash (vn_phi_t vp1)
883 hashval_t result = 0;
887 result = vp1->block->index;
889 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
891 if (phi1op == VN_TOP)
893 result += iterative_hash_expr (phi1op, result);
899 /* Return the computed hashcode for phi operation P1. */
902 vn_phi_hash (const void *p1)
904 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
905 return vp1->hashcode;
908 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
911 vn_phi_eq (const void *p1, const void *p2)
913 const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
914 const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
916 if (vp1->block == vp2->block)
921 /* Any phi in the same block will have it's arguments in the
922 same edge order, because of how we store phi nodes. */
923 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
925 tree phi2op = VEC_index (tree, vp2->phiargs, i);
926 if (phi1op == VN_TOP || phi2op == VN_TOP)
928 if (!expressions_equal_p (phi1op, phi2op))
936 static VEC(tree, heap) *shared_lookup_phiargs;
938 /* Lookup PHI in the current hash table, and return the resulting
939 value number if it exists in the hash table. Return NULL_TREE if
940 it does not exist in the hash table. */
943 vn_phi_lookup (tree phi)
949 VEC_truncate (tree, shared_lookup_phiargs, 0);
951 /* Canonicalize the SSA_NAME's to their value number. */
952 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
954 tree def = PHI_ARG_DEF (phi, i);
955 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
956 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
958 vp1.phiargs = shared_lookup_phiargs;
959 vp1.block = bb_for_stmt (phi);
960 vp1.hashcode = vn_phi_compute_hash (&vp1);
961 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
965 return ((vn_phi_t)*slot)->result;
968 /* Insert PHI into the current hash table with a value number of
972 vn_phi_insert (tree phi, tree result)
975 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
977 VEC (tree, heap) *args = NULL;
979 /* Canonicalize the SSA_NAME's to their value number. */
980 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
982 tree def = PHI_ARG_DEF (phi, i);
983 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
984 VEC_safe_push (tree, heap, args, def);
987 vp1->block = bb_for_stmt (phi);
988 vp1->result = result;
989 vp1->hashcode = vn_phi_compute_hash (vp1);
991 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
994 /* Because we iterate over phi operations more than once, it's
995 possible the slot might already exist here, hence no assert.*/
1000 /* Print set of components in strongly connected component SCC to OUT. */
1003 print_scc (FILE *out, VEC (tree, heap) *scc)
1008 fprintf (out, "SCC consists of: ");
1009 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1011 print_generic_expr (out, var, 0);
1014 fprintf (out, "\n");
1017 /* Set the value number of FROM to TO, return true if it has changed
1021 set_ssa_val_to (tree from, tree to)
1025 /* The only thing we allow as value numbers are VN_TOP, ssa_names
1026 and invariants. So assert that here. */
1027 gcc_assert (to != NULL_TREE
1029 || TREE_CODE (to) == SSA_NAME
1030 || is_gimple_min_invariant (to)));
1032 if (dump_file && (dump_flags & TDF_DETAILS))
1034 fprintf (dump_file, "Setting value number of ");
1035 print_generic_expr (dump_file, from, 0);
1036 fprintf (dump_file, " to ");
1037 print_generic_expr (dump_file, to, 0);
1038 fprintf (dump_file, "\n");
1041 currval = SSA_VAL (from);
1043 if (currval != to && !operand_equal_p (currval, to, OEP_PURE_SAME))
1045 SSA_VAL (from) = to;
1051 /* Set all definitions in STMT to value number to themselves.
1052 Return true if a value number changed. */
1055 defs_to_varying (tree stmt)
1057 bool changed = false;
1061 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1063 tree def = DEF_FROM_PTR (defp);
1065 VN_INFO (def)->use_processed = true;
1066 changed |= set_ssa_val_to (def, def);
1071 /* Visit a copy between LHS and RHS, return true if the value number
1075 visit_copy (tree lhs, tree rhs)
1078 /* Follow chains of copies to their destination. */
1079 while (SSA_VAL (rhs) != rhs && TREE_CODE (SSA_VAL (rhs)) == SSA_NAME)
1080 rhs = SSA_VAL (rhs);
1082 /* The copy may have a more interesting constant filled expression
1083 (we don't, since we know our RHS is just an SSA name). */
1084 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1085 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1087 return set_ssa_val_to (lhs, rhs);
1090 /* Visit a unary operator RHS, value number it, and return true if the
1091 value number of LHS has changed as a result. */
1094 visit_unary_op (tree lhs, tree op)
1096 bool changed = false;
1097 tree result = vn_unary_op_lookup (op);
1101 changed = set_ssa_val_to (lhs, result);
1105 changed = set_ssa_val_to (lhs, lhs);
1106 vn_unary_op_insert (op, lhs);
1112 /* Visit a binary operator RHS, value number it, and return true if the
1113 value number of LHS has changed as a result. */
1116 visit_binary_op (tree lhs, tree op)
1118 bool changed = false;
1119 tree result = vn_binary_op_lookup (op);
1123 changed = set_ssa_val_to (lhs, result);
1127 changed = set_ssa_val_to (lhs, lhs);
1128 vn_binary_op_insert (op, lhs);
1134 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1135 and return true if the value number of the LHS has changed as a result. */
1138 visit_reference_op_load (tree lhs, tree op, tree stmt)
1140 bool changed = false;
1141 tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt));
1145 changed = set_ssa_val_to (lhs, result);
1149 changed = set_ssa_val_to (lhs, lhs);
1150 vn_reference_insert (op, lhs, copy_vuses_from_stmt (stmt));
1157 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1158 and return true if the value number of the LHS has changed as a result. */
1161 visit_reference_op_store (tree lhs, tree op, tree stmt)
1163 bool changed = false;
1165 bool resultsame = false;
1167 /* First we want to lookup using the *vuses* from the store and see
1168 if there the last store to this location with the same address
1171 The vuses represent the memory state before the store. If the
1172 memory state, address, and value of the store is the same as the
1173 last store to this location, then this store will produce the
1174 same memory state as that store.
1176 In this case the vdef versions for this store are value numbered to those
1177 vuse versions, since they represent the same memory state after
1180 Otherwise, the vdefs for the store are used when inserting into
1181 the table, since the store generates a new memory state. */
1183 result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt));
1187 if (TREE_CODE (result) == SSA_NAME)
1188 result = SSA_VAL (result);
1189 resultsame = expressions_equal_p (result, op);
1192 if (!result || !resultsame)
1194 VEC(tree, gc) *vdefs = copy_vdefs_from_stmt (stmt);
1198 if (dump_file && (dump_flags & TDF_DETAILS))
1200 fprintf (dump_file, "No store match\n");
1201 fprintf (dump_file, "Value numbering store ");
1202 print_generic_expr (dump_file, lhs, 0);
1203 fprintf (dump_file, " to ");
1204 print_generic_expr (dump_file, op, 0);
1205 fprintf (dump_file, "\n");
1207 /* Have to set value numbers before insert, since insert is
1208 going to valueize the references in-place. */
1209 for (i = 0; VEC_iterate (tree, vdefs, i, vdef); i++)
1211 VN_INFO (vdef)->use_processed = true;
1212 changed |= set_ssa_val_to (vdef, vdef);
1215 vn_reference_insert (lhs, op, vdefs);
1219 /* We had a match, so value number the vdefs to have the value
1220 number of the vuses they came from. */
1221 ssa_op_iter op_iter;
1225 if (dump_file && (dump_flags & TDF_DETAILS))
1226 fprintf (dump_file, "Store matched earlier value,"
1227 "value numbering store vdefs to matching vuses.\n");
1229 FOR_EACH_SSA_VDEF_OPERAND (var, vv, stmt, op_iter)
1231 tree def = DEF_FROM_PTR (var);
1234 /* Uh, if the vuse is a multiuse, we can't really do much
1235 here, sadly, since we don't know which value number of
1236 which vuse to use. */
1237 if (VUSE_VECT_NUM_ELEM (*vv) != 1)
1240 use = VUSE_ELEMENT_VAR (*vv, 0);
1242 VN_INFO (def)->use_processed = true;
1243 changed |= set_ssa_val_to (def, SSA_VAL (use));
1250 /* Visit and value number PHI, return true if the value number
1254 visit_phi (tree phi)
1256 bool changed = false;
1258 tree sameval = VN_TOP;
1259 bool allsame = true;
1262 /* See if all non-TOP arguments have the same value. TOP is
1263 equivalent to everything, so we can ignore it. */
1264 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1266 tree def = PHI_ARG_DEF (phi, i);
1268 if (TREE_CODE (def) == SSA_NAME)
1269 def = SSA_VAL (def);
1272 if (sameval == VN_TOP)
1278 if (!expressions_equal_p (def, sameval))
1286 /* If all value numbered to the same value, the phi node has that
1290 if (is_gimple_min_invariant (sameval))
1292 VN_INFO (PHI_RESULT (phi))->has_constants = true;
1293 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1297 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1298 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1301 if (TREE_CODE (sameval) == SSA_NAME)
1302 return visit_copy (PHI_RESULT (phi), sameval);
1304 return set_ssa_val_to (PHI_RESULT (phi), sameval);
1307 /* Otherwise, see if it is equivalent to a phi node in this block. */
1308 result = vn_phi_lookup (phi);
1311 if (TREE_CODE (result) == SSA_NAME)
1312 changed = visit_copy (PHI_RESULT (phi), result);
1314 changed = set_ssa_val_to (PHI_RESULT (phi), result);
1318 vn_phi_insert (phi, PHI_RESULT (phi));
1319 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1320 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1321 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1327 /* Return true if EXPR contains constants. */
1330 expr_has_constants (tree expr)
1332 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1335 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1338 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1339 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1340 /* Constants inside reference ops are rarely interesting, but
1341 it can take a lot of looking to find them. */
1343 case tcc_declaration:
1346 return is_gimple_min_invariant (expr);
1351 /* Replace SSA_NAMES in expr with their value numbers, and return the
1353 This is performed in place. */
1356 valueize_expr (tree expr)
1358 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1361 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1362 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1363 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1366 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1367 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1368 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1369 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
1370 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
1371 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
1379 /* Simplify the binary expression RHS, and return the result if
1383 simplify_binary_expression (tree rhs)
1385 tree result = NULL_TREE;
1386 tree op0 = TREE_OPERAND (rhs, 0);
1387 tree op1 = TREE_OPERAND (rhs, 1);
1389 /* This will not catch every single case we could combine, but will
1390 catch those with constants. The goal here is to simultaneously
1391 combine constants between expressions, but avoid infinite
1392 expansion of expressions during simplification. */
1393 if (TREE_CODE (op0) == SSA_NAME)
1395 if (VN_INFO (op0)->has_constants)
1396 op0 = valueize_expr (VN_INFO (op0)->expr);
1397 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
1398 op0 = SSA_VAL (op0);
1401 if (TREE_CODE (op1) == SSA_NAME)
1403 if (VN_INFO (op1)->has_constants)
1404 op1 = valueize_expr (VN_INFO (op1)->expr);
1405 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
1406 op1 = SSA_VAL (op1);
1409 result = fold_binary (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);
1411 /* Make sure result is not a complex expression consisting
1412 of operators of operators (IE (a + b) + (a + c))
1413 Otherwise, we will end up with unbounded expressions if
1414 fold does anything at all. */
1415 if (result && valid_gimple_expression_p (result))
1421 /* Try to simplify RHS using equivalences and constant folding. */
1424 try_to_simplify (tree stmt, tree rhs)
1426 if (TREE_CODE (rhs) == SSA_NAME)
1428 if (is_gimple_min_invariant (SSA_VAL (rhs)))
1429 return SSA_VAL (rhs);
1430 else if (VN_INFO (rhs)->has_constants)
1431 return VN_INFO (rhs)->expr;
1435 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1437 /* For references, see if we find a result for the lookup,
1438 and use it if we do. */
1439 case tcc_declaration:
1440 /* Pull out any truly constant values. */
1441 if (TREE_READONLY (rhs)
1442 && TREE_STATIC (rhs)
1443 && DECL_INITIAL (rhs)
1444 && valid_gimple_expression_p (DECL_INITIAL (rhs)))
1445 return DECL_INITIAL (rhs);
1450 tree result = vn_reference_lookup (rhs,
1451 shared_vuses_from_stmt (stmt));
1456 /* We could do a little more with unary ops, if they expand
1457 into binary ops, but it's debatable whether it is worth it. */
1460 tree result = NULL_TREE;
1461 tree op0 = TREE_OPERAND (rhs, 0);
1462 if (TREE_CODE (op0) == SSA_NAME && VN_INFO (op0)->has_constants)
1463 op0 = VN_INFO (op0)->expr;
1464 else if (TREE_CODE (op0) == SSA_NAME && SSA_VAL (op0) != op0)
1465 op0 = SSA_VAL (op0);
1466 result = fold_unary (TREE_CODE (rhs), TREE_TYPE (rhs), op0);
1471 case tcc_comparison:
1473 return simplify_binary_expression (rhs);
1482 /* Visit and value number USE, return true if the value number
1486 visit_use (tree use)
1488 bool changed = false;
1489 tree stmt = SSA_NAME_DEF_STMT (use);
1492 VN_INFO (use)->use_processed = true;
1494 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
1495 if (dump_file && (dump_flags & TDF_DETAILS))
1497 fprintf (dump_file, "Value numbering ");
1498 print_generic_expr (dump_file, use, 0);
1499 fprintf (dump_file, " stmt = ");
1500 print_generic_stmt (dump_file, stmt, 0);
1503 /* RETURN_EXPR may have an embedded MODIFY_STMT. */
1504 if (TREE_CODE (stmt) == RETURN_EXPR
1505 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1506 stmt = TREE_OPERAND (stmt, 0);
1508 ann = stmt_ann (stmt);
1510 /* Handle uninitialized uses. */
1511 if (IS_EMPTY_STMT (stmt))
1513 changed = set_ssa_val_to (use, use);
1517 if (TREE_CODE (stmt) == PHI_NODE)
1519 changed = visit_phi (stmt);
1521 else if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
1522 || (ann && ann->has_volatile_ops))
1524 changed = defs_to_varying (stmt);
1528 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1529 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1532 STRIP_USELESS_TYPE_CONVERSION (rhs);
1534 /* Shortcut for copies. Simplifying copies is pointless,
1535 since we copy the expression and value they represent. */
1536 if (TREE_CODE (rhs) == SSA_NAME && TREE_CODE (lhs) == SSA_NAME)
1538 changed = visit_copy (lhs, rhs);
1541 simplified = try_to_simplify (stmt, rhs);
1542 if (simplified && simplified != rhs)
1544 if (dump_file && (dump_flags & TDF_DETAILS))
1546 fprintf (dump_file, "RHS ");
1547 print_generic_expr (dump_file, rhs, 0);
1548 fprintf (dump_file, " simplified to ");
1549 print_generic_expr (dump_file, simplified, 0);
1550 if (TREE_CODE (lhs) == SSA_NAME)
1551 fprintf (dump_file, " has constants %d\n",
1552 VN_INFO (lhs)->has_constants);
1554 fprintf (dump_file, "\n");
1558 /* Setting value numbers to constants will occasionally
1559 screw up phi congruence because constants are not
1560 uniquely associated with a single ssa name that can be
1562 if (simplified && is_gimple_min_invariant (simplified)
1563 && TREE_CODE (lhs) == SSA_NAME
1564 && simplified != rhs)
1566 VN_INFO (lhs)->expr = simplified;
1567 VN_INFO (lhs)->has_constants = true;
1568 changed = set_ssa_val_to (lhs, simplified);
1571 else if (simplified && TREE_CODE (simplified) == SSA_NAME
1572 && TREE_CODE (lhs) == SSA_NAME)
1574 changed = visit_copy (lhs, simplified);
1577 else if (simplified)
1579 if (TREE_CODE (lhs) == SSA_NAME)
1581 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
1582 /* We have to unshare the expression or else
1583 valuizing may change the IL stream. */
1584 VN_INFO (lhs)->expr = unshare_expr (simplified);
1588 else if (expr_has_constants (rhs) && TREE_CODE (lhs) == SSA_NAME)
1590 VN_INFO (lhs)->has_constants = true;
1591 VN_INFO (lhs)->expr = unshare_expr (rhs);
1593 else if (TREE_CODE (lhs) == SSA_NAME)
1595 /* We reset expr and constantness here because we may
1596 have been value numbering optimistically, and
1597 iterating. They may become non-constant in this case,
1598 even if they were optimistically constant. */
1600 VN_INFO (lhs)->has_constants = false;
1601 VN_INFO (lhs)->expr = lhs;
1604 if (TREE_CODE (lhs) == SSA_NAME
1605 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1606 changed = defs_to_varying (stmt);
1607 else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
1609 changed = visit_reference_op_store (lhs, rhs, stmt);
1611 else if (TREE_CODE (lhs) == SSA_NAME)
1613 if (is_gimple_min_invariant (rhs))
1615 VN_INFO (lhs)->has_constants = true;
1616 VN_INFO (lhs)->expr = rhs;
1617 changed = set_ssa_val_to (lhs, rhs);
1621 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1624 changed = visit_unary_op (lhs, rhs);
1627 changed = visit_binary_op (lhs, rhs);
1629 /* If tcc_vl_expr ever encompasses more than
1630 CALL_EXPR, this will need to be changed. */
1632 if (call_expr_flags (rhs) & (ECF_PURE | ECF_CONST))
1633 changed = visit_reference_op_load (lhs, rhs, stmt);
1635 changed = defs_to_varying (stmt);
1637 case tcc_declaration:
1639 changed = visit_reference_op_load (lhs, rhs, stmt);
1641 case tcc_expression:
1642 if (TREE_CODE (rhs) == ADDR_EXPR)
1644 changed = visit_unary_op (lhs, rhs);
1649 changed = defs_to_varying (stmt);
1655 changed = defs_to_varying (stmt);
1662 /* Compare two operands by reverse postorder index */
1665 compare_ops (const void *pa, const void *pb)
1667 const tree opa = *((const tree *)pa);
1668 const tree opb = *((const tree *)pb);
1669 tree opstmta = SSA_NAME_DEF_STMT (opa);
1670 tree opstmtb = SSA_NAME_DEF_STMT (opb);
1674 if (IS_EMPTY_STMT (opstmta) && IS_EMPTY_STMT (opstmtb))
1676 else if (IS_EMPTY_STMT (opstmta))
1678 else if (IS_EMPTY_STMT (opstmtb))
1681 bba = bb_for_stmt (opstmta);
1682 bbb = bb_for_stmt (opstmtb);
1693 if (TREE_CODE (opstmta) == PHI_NODE && TREE_CODE (opstmtb) == PHI_NODE)
1695 else if (TREE_CODE (opstmta) == PHI_NODE)
1697 else if (TREE_CODE (opstmtb) == PHI_NODE)
1699 return stmt_ann (opstmta)->uid - stmt_ann (opstmtb)->uid;
1701 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
1704 /* Sort an array containing members of a strongly connected component
1705 SCC so that the members are ordered by RPO number.
1706 This means that when the sort is complete, iterating through the
1707 array will give you the members in RPO order. */
1710 sort_scc (VEC (tree, heap) *scc)
1712 qsort (VEC_address (tree, scc),
1713 VEC_length (tree, scc),
1718 /* Process a strongly connected component in the SSA graph. */
1721 process_scc (VEC (tree, heap) *scc)
1723 /* If the SCC has a single member, just visit it. */
1725 if (VEC_length (tree, scc) == 1)
1727 tree use = VEC_index (tree, scc, 0);
1728 if (!VN_INFO (use)->use_processed)
1735 unsigned int iterations = 0;
1736 bool changed = true;
1738 /* Iterate over the SCC with the optimistic table until it stops
1740 current_info = optimistic_info;
1745 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1746 changed |= visit_use (var);
1749 if (dump_file && (dump_flags & TDF_STATS))
1750 fprintf (dump_file, "Processing SCC required %d iterations\n",
1753 /* Finally, visit the SCC once using the valid table. */
1754 current_info = valid_info;
1755 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1760 /* Depth first search on NAME to discover and process SCC's in the SSA
1762 Execution of this algorithm relies on the fact that the SCC's are
1763 popped off the stack in topological order. */
1773 VN_INFO (name)->dfsnum = next_dfs_num++;
1774 VN_INFO (name)->visited = true;
1775 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
1777 VEC_safe_push (tree, heap, sccstack, name);
1778 VN_INFO (name)->on_sccstack = true;
1779 defstmt = SSA_NAME_DEF_STMT (name);
1781 /* Recursively DFS on our operands, looking for SCC's. */
1782 if (!IS_EMPTY_STMT (defstmt))
1784 FOR_EACH_PHI_OR_STMT_USE (usep, SSA_NAME_DEF_STMT (name), iter,
1787 tree use = USE_FROM_PTR (usep);
1789 /* Since we handle phi nodes, we will sometimes get
1790 invariants in the use expression. */
1791 if (TREE_CODE (use) != SSA_NAME)
1794 if (! (VN_INFO (use)->visited))
1797 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
1798 VN_INFO (use)->low);
1800 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
1801 && VN_INFO (use)->on_sccstack)
1803 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
1804 VN_INFO (name)->low);
1809 /* See if we found an SCC. */
1810 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
1812 VEC (tree, heap) *scc = NULL;
1815 /* Found an SCC, pop the components off the SCC stack and
1819 x = VEC_pop (tree, sccstack);
1821 VN_INFO (x)->on_sccstack = false;
1822 VEC_safe_push (tree, heap, scc, x);
1823 } while (x != name);
1825 if (VEC_length (tree, scc) > 1)
1828 if (dump_file && (dump_flags & TDF_DETAILS))
1829 print_scc (dump_file, scc);
1833 VEC_free (tree, heap, scc);
1841 VEC_free (tree, heap, phi->phiargs);
1845 /* Free a reference operation structure VP. */
1848 free_reference (void *vp)
1850 vn_reference_t vr = vp;
1851 VEC_free (vn_reference_op_s, heap, vr->operands);
1854 /* Allocate a value number table. */
1857 allocate_vn_table (vn_tables_t table)
1859 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
1860 table->unary = htab_create (23, vn_unary_op_hash, vn_unary_op_eq, NULL);
1861 table->binary = htab_create (23, vn_binary_op_hash, vn_binary_op_eq, NULL);
1862 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
1865 table->unary_op_pool = create_alloc_pool ("VN unary operations",
1866 sizeof (struct vn_unary_op_s),
1868 table->binary_op_pool = create_alloc_pool ("VN binary operations",
1869 sizeof (struct vn_binary_op_s),
1871 table->phis_pool = create_alloc_pool ("VN phis",
1872 sizeof (struct vn_phi_s),
1874 table->references_pool = create_alloc_pool ("VN references",
1875 sizeof (struct vn_reference_s),
1879 /* Free a value number table. */
1882 free_vn_table (vn_tables_t table)
1884 htab_delete (table->phis);
1885 htab_delete (table->unary);
1886 htab_delete (table->binary);
1887 htab_delete (table->references);
1888 free_alloc_pool (table->unary_op_pool);
1889 free_alloc_pool (table->binary_op_pool);
1890 free_alloc_pool (table->phis_pool);
1891 free_alloc_pool (table->references_pool);
1899 int *rpo_numbers_temp;
1903 calculate_dominance_info (CDI_DOMINATORS);
1907 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
1908 /* VEC_alloc doesn't actually grow it to the right size, it just
1909 preallocates the space to do so. */
1910 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
1911 shared_lookup_phiargs = NULL;
1912 shared_lookup_vops = NULL;
1913 shared_lookup_references = NULL;
1914 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
1915 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
1916 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
1918 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
1919 the i'th block in RPO order is bb. We want to map bb's to RPO
1920 numbers, so we need to rearrange this array. */
1921 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
1922 rpo_numbers[rpo_numbers_temp[j]] = j;
1924 free (rpo_numbers_temp);
1926 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
1928 /* Create the VN_INFO structures, and initialize value numbers to
1930 for (i = 0; i < num_ssa_names; i++)
1932 tree name = ssa_name (i);
1935 VN_INFO_GET (name)->valnum = VN_TOP;
1936 VN_INFO (name)->expr = name;
1942 block_stmt_iterator bsi;
1943 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1945 tree stmt = bsi_stmt (bsi);
1946 stmt_ann (stmt)->uid = id++;
1950 /* Create the valid and optimistic value numbering tables. */
1951 valid_info = XCNEW (struct vn_tables_s);
1952 allocate_vn_table (valid_info);
1953 optimistic_info = XCNEW (struct vn_tables_s);
1954 allocate_vn_table (optimistic_info);
1959 switch_to_PRE_table (void)
1961 pre_info = XCNEW (struct vn_tables_s);
1962 allocate_vn_table (pre_info);
1963 current_info = pre_info;
1971 VEC_free (tree, heap, shared_lookup_phiargs);
1972 VEC_free (tree, gc, shared_lookup_vops);
1973 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
1974 XDELETEVEC (rpo_numbers);
1975 for (i = 0; i < num_ssa_names; i++)
1977 tree name = ssa_name (i);
1980 XDELETE (VN_INFO (name));
1981 if (SSA_NAME_VALUE (name) &&
1982 TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
1983 SSA_NAME_VALUE (name) = NULL;
1987 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
1988 VEC_free (tree, heap, sccstack);
1989 free_vn_table (valid_info);
1990 XDELETE (valid_info);
1991 free_vn_table (optimistic_info);
1992 XDELETE (optimistic_info);
1995 free_vn_table (pre_info);
2007 current_info = valid_info;
2009 for (param = DECL_ARGUMENTS (current_function_decl);
2011 param = TREE_CHAIN (param))
2013 if (gimple_default_def (cfun, param) != NULL)
2015 tree def = gimple_default_def (cfun, param);
2016 SSA_VAL (def) = def;
2020 for (i = num_ssa_names - 1; i > 0; i--)
2022 tree name = ssa_name (i);
2024 && VN_INFO (name)->visited == false
2025 && !has_zero_uses (name))
2029 if (dump_file && (dump_flags & TDF_DETAILS))
2031 fprintf (dump_file, "Value numbers:\n");
2032 for (i = 0; i < num_ssa_names; i++)
2034 tree name = ssa_name (i);
2035 if (name && VN_INFO (name)->visited
2036 && (SSA_VAL (name) != name
2037 || is_gimple_min_invariant (VN_INFO (name)->expr)))
2039 print_generic_expr (dump_file, name, 0);
2040 fprintf (dump_file, " = ");
2041 if (is_gimple_min_invariant (VN_INFO (name)->expr))
2042 print_generic_expr (dump_file, VN_INFO (name)->expr, 0);
2044 print_generic_expr (dump_file, SSA_VAL (name), 0);
2045 fprintf (dump_file, "\n");