1 /* SCC value numbering for trees
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 2, 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 COPYING. If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
25 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
41 #include "tree-pass.h"
44 #include "langhooks.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;
134 /* Unary operations in the hashtable consist of a single operand, an
135 opcode, and a type. Result is the value number of the operation,
136 and hashcode is stored to avoid having to calculate it repeatedly. */
138 typedef struct vn_unary_op_s
140 enum tree_code opcode;
147 /* Phi nodes in the hashtable consist of their non-VN_TOP phi
148 arguments, and the basic block the phi is in. Result is the value
149 number of the operation, and hashcode is stored to avoid having to
150 calculate it repeatedly. Phi nodes not in the same block are never
151 considered equivalent. */
153 typedef struct vn_phi_s
155 VEC (tree, heap) *phiargs;
161 /* Reference operands only exist in reference operations structures.
162 They consist of an opcode, type, and some number of operands. For
163 a given opcode, some, all, or none of the operands may be used.
164 The operands are there to store the information that makes up the
165 portion of the addressing calculation that opcode performs. */
167 typedef struct vn_reference_op_struct
169 enum tree_code opcode;
175 typedef vn_reference_op_s *vn_reference_op_t;
177 DEF_VEC_O(vn_reference_op_s);
178 DEF_VEC_ALLOC_O(vn_reference_op_s, heap);
180 /* A reference operation in the hashtable is representation as a
181 collection of vuses, representing the memory state at the time of
182 the operation, and a collection of operands that make up the
183 addressing calculation. If two vn_reference_t's have the same set
184 of operands, they access the same memory location. We also store
185 the resulting value number, and the hashcode. The vuses are
186 always stored in order sorted by ssa name version. */
188 typedef struct vn_reference_s
190 VEC (tree, gc) *vuses;
191 VEC (vn_reference_op_s, heap) *operands;
196 /* Valid hashtables storing information we have proven to be
199 static vn_tables_t valid_info;
201 /* Optimistic hashtables storing information we are making assumptions about
202 during iterations. */
204 static vn_tables_t optimistic_info;
206 /* PRE hashtables storing information about mapping from expressions to
209 static vn_tables_t pre_info;
211 /* Pointer to the set of hashtables that is currently being used.
212 Should always point to either the optimistic_info, or the
215 static vn_tables_t current_info;
218 /* Reverse post order index for each basic block. */
220 static int *rpo_numbers;
222 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
224 /* This represents the top of the VN lattice, which is the universal
229 /* Next DFS number and the stack for strongly connected component
232 static unsigned int next_dfs_num;
233 static VEC (tree, heap) *sccstack;
235 DEF_VEC_P(vn_ssa_aux_t);
236 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
238 /* Table of vn_ssa_aux_t's, one per ssa_name. */
240 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
242 /* Return the value numbering information for a given SSA name. */
247 return VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
248 SSA_NAME_VERSION (name));
251 /* Set the value numbering info for a given SSA name to a given
255 VN_INFO_SET (tree name, vn_ssa_aux_t value)
257 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
258 SSA_NAME_VERSION (name), value);
261 /* Get the value numbering info for a given SSA name, creating it if
262 it does not exist. */
265 VN_INFO_GET (tree name)
267 vn_ssa_aux_t newinfo = XCNEW (struct vn_ssa_aux);
268 if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
269 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
270 SSA_NAME_VERSION (name) + 1);
271 VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
272 SSA_NAME_VERSION (name), newinfo);
277 /* Compare two reference operands P1 and P2 for equality. return true if
278 they are equal, and false otherwise. */
281 vn_reference_op_eq (const void *p1, const void *p2)
283 const vn_reference_op_t vro1 = (vn_reference_op_t) p1;
284 const vn_reference_op_t vro2 = (vn_reference_op_t) p2;
285 return vro1->opcode == vro2->opcode
286 && vro1->type == vro2->type
287 && expressions_equal_p (vro1->op0, vro2->op0)
288 && expressions_equal_p (vro1->op1, vro2->op1)
289 && expressions_equal_p (vro1->op2, vro2->op2);
292 /* Compute the hash for a reference operand VRO1 */
295 vn_reference_op_compute_hash (const vn_reference_op_t vro1)
297 return iterative_hash_expr (vro1->op0, vro1->opcode)
298 + iterative_hash_expr (vro1->op1, vro1->opcode)
299 + iterative_hash_expr (vro1->op2, vro1->opcode);
302 /* Return the hashcode for a given reference operation P1. */
305 vn_reference_hash (const void *p1)
307 const vn_reference_t vr1 = (vn_reference_t) p1;
308 return vr1->hashcode;
311 /* Compute a hash for the reference operation VR1 and return it. */
313 static inline hashval_t
314 vn_reference_compute_hash (const vn_reference_t vr1)
316 hashval_t result = 0;
319 vn_reference_op_t vro;
321 for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
322 result += iterative_hash_expr (v, 0);
323 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
324 result += vn_reference_op_compute_hash (vro);
329 /* Return true if reference operations P1 and P2 are equivalent. This
330 means they have the same set of operands and vuses. */
333 vn_reference_eq (const void *p1, const void *p2)
337 vn_reference_op_t vro;
339 const vn_reference_t vr1 = (vn_reference_t) p1;
340 const vn_reference_t vr2 = (vn_reference_t) p2;
342 if (vr1->vuses == vr2->vuses
343 && vr1->operands == vr2->operands)
346 /* Impossible for them to be equivalent if they have different
348 if (VEC_length (tree, vr1->vuses) != VEC_length (tree, vr2->vuses))
351 /* We require that address operands be canonicalized in a way that
352 two memory references will have the same operands if they are
354 if (VEC_length (vn_reference_op_s, vr1->operands)
355 != VEC_length (vn_reference_op_s, vr2->operands))
358 /* The memory state is more often different than the address of the
359 store/load, so check it first. */
360 for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
362 if (VEC_index (tree, vr2->vuses, i) != v)
366 for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
368 if (!vn_reference_op_eq (VEC_index (vn_reference_op_s, vr2->operands, i),
375 /* Place the vuses from STMT into *result */
378 vuses_to_vec (tree stmt, VEC (tree, gc) **result)
386 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
387 VEC_safe_push (tree, gc, *result, vuse);
389 if (VEC_length (tree, *result) > 1)
390 sort_vuses (*result);
394 /* Copy the VUSE names in STMT into a vector, and return
398 copy_vuses_from_stmt (tree stmt)
400 VEC (tree, gc) *vuses = NULL;
402 vuses_to_vec (stmt, &vuses);
407 /* Place the vdefs from STMT into *result */
410 vdefs_to_vec (tree stmt, VEC (tree, gc) **result)
418 FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, iter, SSA_OP_VIRTUAL_DEFS)
419 VEC_safe_push (tree, gc, *result, vdef);
421 if (VEC_length (tree, *result) > 1)
422 sort_vuses (*result);
425 /* Copy the names of vdef results in STMT into a vector, and return
428 static VEC (tree, gc) *
429 copy_vdefs_from_stmt (tree stmt)
431 VEC (tree, gc) *vdefs = NULL;
433 vdefs_to_vec (stmt, &vdefs);
438 /* Place for shared_v{uses/defs}_from_stmt to shove vuses/vdefs. */
439 static VEC (tree, gc) *shared_lookup_vops;
441 /* Copy the virtual uses from STMT into SHARED_LOOKUP_VOPS.
442 This function will overwrite the current SHARED_LOOKUP_VOPS
446 shared_vuses_from_stmt (tree stmt)
448 VEC_truncate (tree, shared_lookup_vops, 0);
449 vuses_to_vec (stmt, &shared_lookup_vops);
451 return shared_lookup_vops;
454 /* Copy the operations present in load/store/call REF into RESULT, a vector of
455 vn_reference_op_s's. */
458 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
460 /* Calls are different from all other reference operations. */
461 if (TREE_CODE (ref) == CALL_EXPR)
463 vn_reference_op_s temp;
465 call_expr_arg_iterator iter;
468 /* Copy the call_expr opcode, type, function being called, and
470 memset (&temp, 0, sizeof (temp));
471 temp.type = TREE_TYPE (ref);
472 temp.opcode = CALL_EXPR;
473 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
475 callfn = get_callee_fndecl (ref);
477 callfn = CALL_EXPR_FN (ref);
478 temp.type = TREE_TYPE (callfn);
479 temp.opcode = TREE_CODE (callfn);
481 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
483 FOR_EACH_CALL_EXPR_ARG (callarg, iter, ref)
485 memset (&temp, 0, sizeof (temp));
486 temp.type = TREE_TYPE (callarg);
487 temp.opcode = TREE_CODE (callarg);
489 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
494 /* For non-calls, store the information that makes up the address. */
498 vn_reference_op_s temp;
500 memset (&temp, 0, sizeof (temp));
501 temp.type = TREE_TYPE (ref);
502 temp.opcode = TREE_CODE (ref);
506 case ALIGN_INDIRECT_REF:
507 case MISALIGNED_INDIRECT_REF:
509 /* The only operand is the address, which gets its own
510 vn_reference_op_s structure. */
513 /* Record bits and position. */
514 temp.op0 = TREE_OPERAND (ref, 1);
515 temp.op1 = TREE_OPERAND (ref, 2);
518 /* Record field as operand. */
519 temp.op0 = TREE_OPERAND (ref, 1);
521 case ARRAY_RANGE_REF:
523 /* Record index as operand. */
524 temp.op0 = TREE_OPERAND (ref, 1);
525 temp.op1 = TREE_OPERAND (ref, 3);
539 /* These are only interesting for their operands, their
540 existence, and their type. They will never be the last
541 ref in the chain of references (IE they require an
542 operand), so we don't have to put anything
543 for op* as it will be handled by the iteration */
546 case VIEW_CONVERT_EXPR:
553 VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
555 if (REFERENCE_CLASS_P (ref) || TREE_CODE (ref) == ADDR_EXPR)
556 ref = TREE_OPERAND (ref, 0);
562 /* Create a vector of vn_reference_op_s structures from REF, a
563 REFERENCE_CLASS_P tree. The vector is not shared. */
565 static VEC(vn_reference_op_s, heap) *
566 create_reference_ops_from_ref (tree ref)
568 VEC (vn_reference_op_s, heap) *result = NULL;
570 copy_reference_ops_from_ref (ref, &result);
574 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
576 /* Create a vector of vn_reference_op_s structures from REF, a
577 REFERENCE_CLASS_P tree. The vector is shared among all callers of
580 static VEC(vn_reference_op_s, heap) *
581 shared_reference_ops_from_ref (tree ref)
585 VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
586 copy_reference_ops_from_ref (ref, &shared_lookup_references);
587 return shared_lookup_references;
591 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
592 structures into their value numbers. This is done in-place, and
593 the vector passed in is returned. */
595 static VEC (vn_reference_op_s, heap) *
596 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
598 vn_reference_op_t vro;
601 for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
603 if (vro->opcode == SSA_NAME
604 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
605 vro->op0 = SSA_VAL (vro->op0);
611 /* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
612 their value numbers. This is done in-place, and the vector passed
615 static VEC (tree, gc) *
616 valueize_vuses (VEC (tree, gc) *orig)
618 bool made_replacement = false;
622 for (i = 0; VEC_iterate (tree, orig, i, vuse); i++)
624 if (vuse != SSA_VAL (vuse))
626 made_replacement = true;
627 VEC_replace (tree, orig, i, SSA_VAL (vuse));
631 if (made_replacement && VEC_length (tree, orig) > 1)
637 /* Lookup OP in the current hash table, and return the resulting
638 value number if it exists in the hash table. Return NULL_TREE if
639 it does not exist in the hash table. */
642 vn_reference_lookup (tree op, VEC (tree, gc) *vuses)
645 struct vn_reference_s vr1;
647 vr1.vuses = valueize_vuses (vuses);
648 vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
649 vr1.hashcode = vn_reference_compute_hash (&vr1);
650 slot = htab_find_slot_with_hash (current_info->references, &vr1, vr1.hashcode,
655 return ((vn_reference_t)*slot)->result;
658 /* Insert OP into the current hash table with a value number of
662 vn_reference_insert (tree op, tree result, VEC (tree, gc) *vuses)
667 vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
669 vr1->vuses = valueize_vuses (vuses);
670 vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
671 vr1->hashcode = vn_reference_compute_hash (vr1);
672 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
674 slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
677 /* Because we lookup stores using vuses, and value number failures
678 using the vdefs (see visit_reference_op_store for how and why),
679 it's possible that on failure we may try to insert an already
680 inserted store. This is not wrong, there is no ssa name for a
681 store that we could use as a differentiator anyway. Thus, unlike
682 the other lookup functions, you cannot gcc_assert (!*slot)
690 /* Return the stored hashcode for a unary operation. */
693 vn_unary_op_hash (const void *p1)
695 const vn_unary_op_t vuo1 = (vn_unary_op_t) p1;
696 return vuo1->hashcode;
699 /* Hash a unary operation P1 and return the result. */
701 static inline hashval_t
702 vn_unary_op_compute_hash (const vn_unary_op_t vuo1)
704 return iterative_hash_expr (vuo1->op0, vuo1->opcode);
707 /* Return true if P1 and P2, two unary operations, are equivalent. */
710 vn_unary_op_eq (const void *p1, const void *p2)
712 const vn_unary_op_t vuo1 = (vn_unary_op_t) p1;
713 const vn_unary_op_t vuo2 = (vn_unary_op_t) p2;
714 return vuo1->opcode == vuo2->opcode
715 && vuo1->type == vuo2->type
716 && expressions_equal_p (vuo1->op0, vuo2->op0);
719 /* Lookup OP in the current hash table, and return the resulting
720 value number if it exists in the hash table. Return NULL_TREE if
721 it does not exist in the hash table. */
724 vn_unary_op_lookup (tree op)
727 struct vn_unary_op_s vuo1;
729 vuo1.opcode = TREE_CODE (op);
730 vuo1.type = TREE_TYPE (op);
731 vuo1.op0 = TREE_OPERAND (op, 0);
733 if (TREE_CODE (vuo1.op0) == SSA_NAME)
734 vuo1.op0 = SSA_VAL (vuo1.op0);
736 vuo1.hashcode = vn_unary_op_compute_hash (&vuo1);
737 slot = htab_find_slot_with_hash (current_info->unary, &vuo1, vuo1.hashcode,
741 return ((vn_unary_op_t)*slot)->result;
744 /* Insert OP into the current hash table with a value number of
748 vn_unary_op_insert (tree op, tree result)
751 vn_unary_op_t vuo1 = (vn_unary_op_t) pool_alloc (current_info->unary_op_pool);
753 vuo1->opcode = TREE_CODE (op);
754 vuo1->type = TREE_TYPE (op);
755 vuo1->op0 = TREE_OPERAND (op, 0);
756 vuo1->result = result;
758 if (TREE_CODE (vuo1->op0) == SSA_NAME)
759 vuo1->op0 = SSA_VAL (vuo1->op0);
761 vuo1->hashcode = vn_unary_op_compute_hash (vuo1);
762 slot = htab_find_slot_with_hash (current_info->unary, vuo1, vuo1->hashcode,
768 /* Compute and return the hash value for binary operation VBO1. */
770 static inline hashval_t
771 vn_binary_op_compute_hash (const vn_binary_op_t vbo1)
773 return iterative_hash_expr (vbo1->op0, vbo1->opcode)
774 + iterative_hash_expr (vbo1->op1, vbo1->opcode);
777 /* Return the computed hashcode for binary operation P1. */
780 vn_binary_op_hash (const void *p1)
782 const vn_binary_op_t vbo1 = (vn_binary_op_t) p1;
783 return vbo1->hashcode;
786 /* Compare binary operations P1 and P2 and return true if they are
790 vn_binary_op_eq (const void *p1, const void *p2)
792 const vn_binary_op_t vbo1 = (vn_binary_op_t) p1;
793 const vn_binary_op_t vbo2 = (vn_binary_op_t) p2;
794 return vbo1->opcode == vbo2->opcode
795 && vbo1->type == vbo2->type
796 && expressions_equal_p (vbo1->op0, vbo2->op0)
797 && expressions_equal_p (vbo1->op1, vbo2->op1);
800 /* Lookup OP in the current hash table, and return the resulting
801 value number if it exists in the hash table. Return NULL_TREE if
802 it does not exist in the hash table. */
805 vn_binary_op_lookup (tree op)
808 struct vn_binary_op_s vbo1;
810 vbo1.opcode = TREE_CODE (op);
811 vbo1.type = TREE_TYPE (op);
812 vbo1.op0 = TREE_OPERAND (op, 0);
813 vbo1.op1 = TREE_OPERAND (op, 1);
815 if (TREE_CODE (vbo1.op0) == SSA_NAME)
816 vbo1.op0 = SSA_VAL (vbo1.op0);
817 if (TREE_CODE (vbo1.op1) == SSA_NAME)
818 vbo1.op1 = SSA_VAL (vbo1.op1);
820 if (tree_swap_operands_p (vbo1.op0, vbo1.op1, false)
821 && commutative_tree_code (vbo1.opcode))
823 tree temp = vbo1.op0;
828 vbo1.hashcode = vn_binary_op_compute_hash (&vbo1);
829 slot = htab_find_slot_with_hash (current_info->binary, &vbo1, vbo1.hashcode,
833 return ((vn_binary_op_t)*slot)->result;
836 /* Insert OP into the current hash table with a value number of
840 vn_binary_op_insert (tree op, tree result)
844 vbo1 = (vn_binary_op_t) pool_alloc (current_info->binary_op_pool);
846 vbo1->opcode = TREE_CODE (op);
847 vbo1->type = TREE_TYPE (op);
848 vbo1->op0 = TREE_OPERAND (op, 0);
849 vbo1->op1 = TREE_OPERAND (op, 1);
850 vbo1->result = result;
852 if (TREE_CODE (vbo1->op0) == SSA_NAME)
853 vbo1->op0 = SSA_VAL (vbo1->op0);
854 if (TREE_CODE (vbo1->op1) == SSA_NAME)
855 vbo1->op1 = SSA_VAL (vbo1->op1);
857 if (tree_swap_operands_p (vbo1->op0, vbo1->op1, false)
858 && commutative_tree_code (vbo1->opcode))
860 tree temp = vbo1->op0;
861 vbo1->op0 = vbo1->op1;
864 vbo1->hashcode = vn_binary_op_compute_hash (vbo1);
865 slot = htab_find_slot_with_hash (current_info->binary, vbo1, vbo1->hashcode,
872 /* Compute a hashcode for PHI operation VP1 and return it. */
874 static inline hashval_t
875 vn_phi_compute_hash (vn_phi_t vp1)
877 hashval_t result = 0;
881 result = vp1->block->index;
883 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
885 if (phi1op == VN_TOP)
887 result += iterative_hash_expr (phi1op, result);
893 /* Return the computed hashcode for phi operation P1. */
896 vn_phi_hash (const void *p1)
898 const vn_phi_t vp1 = (vn_phi_t) p1;
899 return vp1->hashcode;
902 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
905 vn_phi_eq (const void *p1, const void *p2)
907 const vn_phi_t vp1 = (vn_phi_t) p1;
908 const vn_phi_t vp2 = (vn_phi_t) p2;
910 if (vp1->block == vp2->block)
915 /* Any phi in the same block will have it's arguments in the
916 same edge order, because of how we store phi nodes. */
917 for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
919 tree phi2op = VEC_index (tree, vp2->phiargs, i);
920 if (phi1op == VN_TOP || phi2op == VN_TOP)
922 if (!expressions_equal_p (phi1op, phi2op))
930 static VEC(tree, heap) *shared_lookup_phiargs;
932 /* Lookup PHI in the current hash table, and return the resulting
933 value number if it exists in the hash table. Return NULL_TREE if
934 it does not exist in the hash table. */
937 vn_phi_lookup (tree phi)
943 VEC_truncate (tree, shared_lookup_phiargs, 0);
945 /* Canonicalize the SSA_NAME's to their value number. */
946 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
948 tree def = PHI_ARG_DEF (phi, i);
949 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
950 VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
952 vp1.phiargs = shared_lookup_phiargs;
953 vp1.block = bb_for_stmt (phi);
954 vp1.hashcode = vn_phi_compute_hash (&vp1);
955 slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
959 return ((vn_phi_t)*slot)->result;
962 /* Insert PHI into the current hash table with a value number of
966 vn_phi_insert (tree phi, tree result)
969 vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
971 VEC (tree, heap) *args = NULL;
973 /* Canonicalize the SSA_NAME's to their value number. */
974 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
976 tree def = PHI_ARG_DEF (phi, i);
977 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
978 VEC_safe_push (tree, heap, args, def);
981 vp1->block = bb_for_stmt (phi);
982 vp1->result = result;
983 vp1->hashcode = vn_phi_compute_hash (vp1);
985 slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
988 /* Because we iterate over phi operations more than once, it's
989 possible the slot might already exist here, hence no assert.*/
994 /* Print set of components in strongly connected component SCC to OUT. */
997 print_scc (FILE *out, VEC (tree, heap) *scc)
1002 fprintf (out, "SCC consists of: ");
1003 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1005 print_generic_expr (out, var, 0);
1008 fprintf (out, "\n");
1011 /* Set the value number of FROM to TO, return true if it has changed
1015 set_ssa_val_to (tree from, tree to)
1017 gcc_assert (to != NULL);
1019 /* Make sure we don't create chains of copies, so that we get the
1020 best value numbering. visit_copy has code to make sure this doesn't
1021 happen, we are doing this here to assert that nothing else breaks
1023 gcc_assert (TREE_CODE (to) != SSA_NAME
1024 || TREE_CODE (SSA_VAL (to)) != SSA_NAME
1025 || SSA_VAL (to) == to
1027 /* The only thing we allow as value numbers are ssa_names and
1028 invariants. So assert that here. */
1029 gcc_assert (TREE_CODE (to) == SSA_NAME || is_gimple_min_invariant (to));
1031 if (dump_file && (dump_flags & TDF_DETAILS))
1033 fprintf (dump_file, "Setting value number of ");
1034 print_generic_expr (dump_file, from, 0);
1035 fprintf (dump_file, " to ");
1036 print_generic_expr (dump_file, to, 0);
1037 fprintf (dump_file, "\n");
1040 if (SSA_VAL (from) != to)
1042 SSA_VAL (from) = to;
1048 /* Set all definitions in STMT to value number to themselves.
1049 Return true if a value number changed. */
1052 defs_to_varying (tree stmt)
1054 bool changed = false;
1058 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1060 tree def = DEF_FROM_PTR (defp);
1062 VN_INFO (def)->use_processed = true;
1063 changed |= set_ssa_val_to (def, def);
1068 /* Visit a copy between LHS and RHS, return true if the value number
1072 visit_copy (tree lhs, tree rhs)
1075 /* Follow chains of copies to their destination. */
1076 while (SSA_VAL (rhs) != rhs && TREE_CODE (SSA_VAL (rhs)) == SSA_NAME)
1077 rhs = SSA_VAL (rhs);
1079 /* The copy may have a more interesting constant filled expression
1080 (we don't, since we know our RHS is just an SSA name). */
1081 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1082 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1084 return set_ssa_val_to (lhs, rhs);
1087 /* Visit a unary operator RHS, value number it, and return true if the
1088 value number of LHS has changed as a result. */
1091 visit_unary_op (tree lhs, tree op)
1093 bool changed = false;
1094 tree result = vn_unary_op_lookup (op);
1098 changed = set_ssa_val_to (lhs, result);
1102 changed = set_ssa_val_to (lhs, lhs);
1103 vn_unary_op_insert (op, lhs);
1109 /* Visit a binary operator RHS, value number it, and return true if the
1110 value number of LHS has changed as a result. */
1113 visit_binary_op (tree lhs, tree op)
1115 bool changed = false;
1116 tree result = vn_binary_op_lookup (op);
1120 changed = set_ssa_val_to (lhs, result);
1124 changed = set_ssa_val_to (lhs, lhs);
1125 vn_binary_op_insert (op, lhs);
1131 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1132 and return true if the value number of the LHS has changed as a result. */
1135 visit_reference_op_load (tree lhs, tree op, tree stmt)
1137 bool changed = false;
1138 tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt));
1142 changed = set_ssa_val_to (lhs, result);
1146 changed = set_ssa_val_to (lhs, lhs);
1147 vn_reference_insert (op, lhs, copy_vuses_from_stmt (stmt));
1154 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1155 and return true if the value number of the LHS has changed as a result. */
1158 visit_reference_op_store (tree lhs, tree op, tree stmt)
1160 bool changed = false;
1162 bool resultsame = false;
1164 /* First we want to lookup using the *vuses* from the store and see
1165 if there the last store to this location with the same address
1168 The vuses represent the memory state before the store. If the
1169 memory state, address, and value of the store is the same as the
1170 last store to this location, then this store will produce the
1171 same memory state as that store.
1173 In this case the vdef versions for this store are value numbered to those
1174 vuse versions, since they represent the same memory state after
1177 Otherwise, the vdefs for the store are used when inserting into
1178 the table, since the store generates a new memory state. */
1180 result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt));
1184 if (TREE_CODE (result) == SSA_NAME)
1185 result = SSA_VAL (result);
1186 resultsame = expressions_equal_p (result, op);
1189 if (!result || !resultsame)
1191 VEC(tree, gc) *vdefs = copy_vdefs_from_stmt (stmt);
1195 if (dump_file && (dump_flags & TDF_DETAILS))
1197 fprintf (dump_file, "No store match\n");
1198 fprintf (dump_file, "Value numbering store ");
1199 print_generic_expr (dump_file, lhs, 0);
1200 fprintf (dump_file, " to ");
1201 print_generic_expr (dump_file, op, 0);
1202 fprintf (dump_file, "\n");
1204 /* Have to set value numbers before insert, since insert is
1205 going to valueize the references in-place. */
1206 for (i = 0; VEC_iterate (tree, vdefs, i, vdef); i++)
1208 VN_INFO (vdef)->use_processed = true;
1209 changed |= set_ssa_val_to (vdef, vdef);
1212 vn_reference_insert (lhs, op, vdefs);
1216 /* We had a match, so value number the vdefs to have the value
1217 number of the vuses they came from. */
1218 ssa_op_iter op_iter;
1222 if (dump_file && (dump_flags & TDF_DETAILS))
1223 fprintf (dump_file, "Store matched earlier value,"
1224 "value numbering store vdefs to matching vuses.\n");
1226 FOR_EACH_SSA_VDEF_OPERAND (var, vv, stmt, op_iter)
1228 tree def = DEF_FROM_PTR (var);
1231 /* Uh, if the vuse is a multiuse, we can't really do much
1232 here, sadly, since we don't know which value number of
1233 which vuse to use. */
1234 if (VUSE_VECT_NUM_ELEM (*vv) != 1)
1237 use = VUSE_ELEMENT_VAR (*vv, 0);
1239 VN_INFO (def)->use_processed = true;
1240 changed |= set_ssa_val_to (def, SSA_VAL (use));
1247 /* Visit and value number PHI, return true if the value number
1251 visit_phi (tree phi)
1253 bool changed = false;
1255 tree sameval = VN_TOP;
1256 bool allsame = true;
1259 /* See if all non-TOP arguments have the same value. TOP is
1260 equivalent to everything, so we can ignore it. */
1261 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1263 tree def = PHI_ARG_DEF (phi, i);
1265 if (TREE_CODE (def) == SSA_NAME)
1266 def = SSA_VAL (def);
1269 if (sameval == VN_TOP)
1275 if (!expressions_equal_p (def, sameval))
1283 /* If all value numbered to the same value, the phi node has that
1287 if (is_gimple_min_invariant (sameval))
1289 VN_INFO (PHI_RESULT (phi))->has_constants = true;
1290 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1294 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1295 VN_INFO (PHI_RESULT (phi))->expr = sameval;
1298 if (TREE_CODE (sameval) == SSA_NAME)
1299 return visit_copy (PHI_RESULT (phi), sameval);
1301 return set_ssa_val_to (PHI_RESULT (phi), sameval);
1304 /* Otherwise, see if it is equivalent to a phi node in this block. */
1305 result = vn_phi_lookup (phi);
1308 if (TREE_CODE (result) == SSA_NAME)
1309 changed = visit_copy (PHI_RESULT (phi), result);
1311 changed = set_ssa_val_to (PHI_RESULT (phi), result);
1315 vn_phi_insert (phi, PHI_RESULT (phi));
1316 VN_INFO (PHI_RESULT (phi))->has_constants = false;
1317 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1318 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1324 /* Return true if EXPR contains constants. */
1327 expr_has_constants (tree expr)
1329 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1332 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1335 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1336 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1337 /* Constants inside reference ops are rarely interesting, but
1338 it can take a lot of looking to find them. */
1342 return is_gimple_min_invariant (expr);
1347 /* Replace SSA_NAMES in expr with their value numbers, and return the
1349 This is performed in place. */
1352 valueize_expr (tree expr)
1354 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1357 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1358 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1359 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1362 if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1363 && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1364 TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1365 if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
1366 && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
1367 TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
1375 /* Simplify the binary expression RHS, and return the result if
1379 simplify_binary_expression (tree rhs)
1381 tree result = NULL_TREE;
1382 tree op0 = TREE_OPERAND (rhs, 0);
1383 tree op1 = TREE_OPERAND (rhs, 1);
1385 /* This will not catch every single case we could combine, but will
1386 catch those with constants. The goal here is to simultaneously
1387 combine constants between expressions, but avoid infinite
1388 expansion of expressions during simplification. */
1389 if (TREE_CODE (op0) == SSA_NAME)
1391 if (VN_INFO (op0)->has_constants)
1392 op0 = valueize_expr (VN_INFO (op0)->expr);
1393 else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
1394 op0 = VN_INFO (op0)->valnum;
1397 if (TREE_CODE (op1) == SSA_NAME)
1399 if (VN_INFO (op1)->has_constants)
1400 op1 = valueize_expr (VN_INFO (op1)->expr);
1401 else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
1402 op1 = VN_INFO (op1)->valnum;
1404 result = fold_binary (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);
1406 /* Make sure result is not a complex expression consiting
1407 of operators of operators (IE (a + b) + (a + c))
1408 Otherwise, we will end up with unbounded expressions if
1409 fold does anything at all. */
1412 if (is_gimple_min_invariant (result))
1414 else if (SSA_VAR_P (result))
1416 else if (EXPR_P (result))
1418 switch (TREE_CODE_CLASS (TREE_CODE (result)))
1422 tree op0 = TREE_OPERAND (result, 0);
1429 tree op0 = TREE_OPERAND (result, 0);
1430 tree op1 = TREE_OPERAND (result, 1);
1431 if (!EXPR_P (op0) && !EXPR_P (op1))
1443 /* Try to simplify RHS using equivalences and constant folding. */
1446 try_to_simplify (tree stmt, tree rhs)
1448 if (TREE_CODE (rhs) == SSA_NAME)
1450 if (is_gimple_min_invariant (SSA_VAL (rhs)))
1451 return SSA_VAL (rhs);
1452 else if (VN_INFO (rhs)->has_constants)
1453 return VN_INFO (rhs)->expr;
1457 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1459 /* For references, see if we find a result for the lookup,
1460 and use it if we do. */
1464 tree result = vn_reference_lookup (rhs,
1465 shared_vuses_from_stmt (stmt));
1470 /* We could do a little more with unary ops, if they expand
1471 into binary ops, but it's debatable whether it is worth it. */
1474 tree result = NULL_TREE;
1475 tree op0 = TREE_OPERAND (rhs, 0);
1476 if (TREE_CODE (op0) == SSA_NAME && VN_INFO (op0)->has_constants)
1477 op0 = VN_INFO (op0)->expr;
1478 else if (TREE_CODE (op0) == SSA_NAME && SSA_VAL (op0) != op0)
1479 op0 = SSA_VAL (op0);
1480 result = fold_unary (TREE_CODE (rhs), TREE_TYPE (rhs), op0);
1485 case tcc_comparison:
1487 return simplify_binary_expression (rhs);
1496 /* Visit and value number USE, return true if the value number
1500 visit_use (tree use)
1502 bool changed = false;
1503 tree stmt = SSA_NAME_DEF_STMT (use);
1506 VN_INFO (use)->use_processed = true;
1508 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
1509 if (dump_file && (dump_flags & TDF_DETAILS))
1511 fprintf (dump_file, "Value numbering ");
1512 print_generic_expr (dump_file, use, 0);
1513 fprintf (dump_file, " stmt = ");
1514 print_generic_stmt (dump_file, stmt, 0);
1517 /* RETURN_EXPR may have an embedded MODIFY_STMT. */
1518 if (TREE_CODE (stmt) == RETURN_EXPR
1519 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1520 stmt = TREE_OPERAND (stmt, 0);
1522 ann = stmt_ann (stmt);
1524 /* Handle uninitialized uses. */
1525 if (IS_EMPTY_STMT (stmt))
1527 changed = set_ssa_val_to (use, use);
1531 if (TREE_CODE (stmt) == PHI_NODE)
1533 changed = visit_phi (stmt);
1535 else if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
1536 || (ann && ann->has_volatile_ops))
1538 changed = defs_to_varying (stmt);
1542 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1543 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1546 STRIP_USELESS_TYPE_CONVERSION (rhs);
1548 /* Shortcut for copies. Simplifying copies is pointless,
1549 since we copy the expression and value they represent. */
1550 if (TREE_CODE (rhs) == SSA_NAME && TREE_CODE (lhs) == SSA_NAME)
1552 changed = visit_copy (lhs, rhs);
1555 simplified = try_to_simplify (stmt, rhs);
1556 if (simplified && simplified != rhs)
1558 if (dump_file && (dump_flags & TDF_DETAILS))
1560 fprintf (dump_file, "RHS ");
1561 print_generic_expr (dump_file, rhs, 0);
1562 fprintf (dump_file, " simplified to ");
1563 print_generic_expr (dump_file, simplified, 0);
1564 if (TREE_CODE (lhs) == SSA_NAME)
1565 fprintf (dump_file, " has constants %d\n",
1566 VN_INFO (lhs)->has_constants);
1568 fprintf (dump_file, "\n");
1572 /* Setting value numbers to constants will occasionally
1573 screw up phi congruence because constants are not
1574 uniquely associated with a single ssa name that can be
1576 if (simplified && is_gimple_min_invariant (simplified)
1577 && TREE_CODE (lhs) == SSA_NAME
1578 && simplified != rhs)
1580 VN_INFO (lhs)->expr = simplified;
1581 VN_INFO (lhs)->has_constants = true;
1582 changed = set_ssa_val_to (lhs, simplified);
1585 else if (simplified && TREE_CODE (simplified) == SSA_NAME
1586 && TREE_CODE (lhs) == SSA_NAME)
1588 changed = visit_copy (lhs, simplified);
1591 else if (simplified)
1593 if (TREE_CODE (lhs) == SSA_NAME)
1595 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
1596 /* We have to unshare the expression or else
1597 valuizing may change the IL stream. */
1598 VN_INFO (lhs)->expr = unshare_expr (simplified);
1602 else if (expr_has_constants (rhs) && TREE_CODE (lhs) == SSA_NAME)
1604 VN_INFO (lhs)->has_constants = true;
1605 VN_INFO (lhs)->expr = unshare_expr (rhs);
1607 else if (TREE_CODE (lhs) == SSA_NAME)
1609 /* We reset expr and constantness here because we may
1610 have been value numbering optimistically, and
1611 iterating. They may become non-constant in this case,
1612 even if they were optimistically constant. */
1614 VN_INFO (lhs)->has_constants = false;
1615 VN_INFO (lhs)->expr = lhs;
1618 if (TREE_CODE (lhs) == SSA_NAME
1619 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1620 changed = defs_to_varying (stmt);
1621 else if (REFERENCE_CLASS_P (lhs))
1623 changed = visit_reference_op_store (lhs, rhs, stmt);
1625 else if (TREE_CODE (lhs) == SSA_NAME)
1627 if (is_gimple_min_invariant (rhs))
1629 VN_INFO (lhs)->has_constants = true;
1630 VN_INFO (lhs)->expr = rhs;
1631 changed = set_ssa_val_to (lhs, rhs);
1635 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1638 changed = visit_unary_op (lhs, rhs);
1641 changed = visit_binary_op (lhs, rhs);
1643 /* If tcc_vl_expr ever encompasses more than
1644 CALL_EXPR, this will need to be changed. */
1646 if (call_expr_flags (rhs) & (ECF_PURE | ECF_CONST))
1647 changed = visit_reference_op_load (lhs, rhs, stmt);
1649 changed = defs_to_varying (stmt);
1651 case tcc_declaration:
1653 changed = visit_reference_op_load (lhs, rhs, stmt);
1655 case tcc_expression:
1656 if (TREE_CODE (rhs) == ADDR_EXPR)
1658 changed = visit_unary_op (lhs, rhs);
1663 changed = defs_to_varying (stmt);
1669 changed = defs_to_varying (stmt);
1676 /* Compare two operands by reverse postorder index */
1679 compare_ops (const void *pa, const void *pb)
1681 const tree opa = *((const tree *)pa);
1682 const tree opb = *((const tree *)pb);
1683 tree opstmta = SSA_NAME_DEF_STMT (opa);
1684 tree opstmtb = SSA_NAME_DEF_STMT (opb);
1688 if (IS_EMPTY_STMT (opstmta) && IS_EMPTY_STMT (opstmtb))
1690 else if (IS_EMPTY_STMT (opstmta))
1692 else if (IS_EMPTY_STMT (opstmtb))
1695 bba = bb_for_stmt (opstmta);
1696 bbb = bb_for_stmt (opstmtb);
1707 if (TREE_CODE (opstmta) == PHI_NODE && TREE_CODE (opstmtb) == PHI_NODE)
1709 else if (TREE_CODE (opstmta) == PHI_NODE)
1711 else if (TREE_CODE (opstmtb) == PHI_NODE)
1713 return stmt_ann (opstmta)->uid - stmt_ann (opstmtb)->uid;
1715 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
1718 /* Sort an array containing members of a strongly connected component
1719 SCC so that the members are ordered by RPO number.
1720 This means that when the sort is complete, iterating through the
1721 array will give you the members in RPO order. */
1724 sort_scc (VEC (tree, heap) *scc)
1726 qsort (VEC_address (tree, scc),
1727 VEC_length (tree, scc),
1732 /* Process a strongly connected component in the SSA graph. */
1735 process_scc (VEC (tree, heap) *scc)
1737 /* If the SCC has a single member, just visit it. */
1739 if (VEC_length (tree, scc) == 1)
1741 tree use = VEC_index (tree, scc, 0);
1742 if (!VN_INFO (use)->use_processed)
1749 unsigned int iterations = 0;
1750 bool changed = true;
1752 /* Iterate over the SCC with the optimistic table until it stops
1754 current_info = optimistic_info;
1759 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1760 changed |= visit_use (var);
1763 if (dump_file && (dump_flags & TDF_STATS))
1764 fprintf (dump_file, "Processing SCC required %d iterations\n",
1767 /* Finally, visit the SCC once using the valid table. */
1768 current_info = valid_info;
1769 for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1774 /* Depth first search on NAME to discover and process SCC's in the SSA
1776 Execution of this algorithm relies on the fact that the SCC's are
1777 popped off the stack in topological order. */
1787 VN_INFO (name)->dfsnum = next_dfs_num++;
1788 VN_INFO (name)->visited = true;
1789 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
1791 VEC_safe_push (tree, heap, sccstack, name);
1792 VN_INFO (name)->on_sccstack = true;
1793 defstmt = SSA_NAME_DEF_STMT (name);
1795 /* Recursively DFS on our operands, looking for SCC's. */
1796 if (!IS_EMPTY_STMT (defstmt))
1798 FOR_EACH_PHI_OR_STMT_USE (usep, SSA_NAME_DEF_STMT (name), iter,
1801 tree use = USE_FROM_PTR (usep);
1803 /* Since we handle phi nodes, we will sometimes get
1804 invariants in the use expression. */
1805 if (TREE_CODE (use) != SSA_NAME)
1808 if (! (VN_INFO (use)->visited))
1811 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
1812 VN_INFO (use)->low);
1814 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
1815 && VN_INFO (use)->on_sccstack)
1817 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
1818 VN_INFO (name)->low);
1823 /* See if we found an SCC. */
1824 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
1826 VEC (tree, heap) *scc = NULL;
1829 /* Found an SCC, pop the components off the SCC stack and
1833 x = VEC_pop (tree, sccstack);
1835 VN_INFO (x)->on_sccstack = false;
1836 VEC_safe_push (tree, heap, scc, x);
1837 } while (x != name);
1839 if (VEC_length (tree, scc) > 1)
1842 if (dump_file && (dump_flags & TDF_DETAILS))
1843 print_scc (dump_file, scc);
1847 VEC_free (tree, heap, scc);
1855 VEC_free (tree, heap, phi->phiargs);
1859 /* Free a reference operation structure VP. */
1862 free_reference (void *vp)
1864 vn_reference_t vr = vp;
1865 VEC_free (vn_reference_op_s, heap, vr->operands);
1868 /* Allocate a value number table. */
1871 allocate_vn_table (vn_tables_t table)
1873 table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
1874 table->unary = htab_create (23, vn_unary_op_hash, vn_unary_op_eq, NULL);
1875 table->binary = htab_create (23, vn_binary_op_hash, vn_binary_op_eq, NULL);
1876 table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
1879 table->unary_op_pool = create_alloc_pool ("VN unary operations",
1880 sizeof (struct vn_unary_op_s),
1882 table->binary_op_pool = create_alloc_pool ("VN binary operations",
1883 sizeof (struct vn_binary_op_s),
1885 table->phis_pool = create_alloc_pool ("VN phis",
1886 sizeof (struct vn_phi_s),
1888 table->references_pool = create_alloc_pool ("VN references",
1889 sizeof (struct vn_reference_s),
1893 /* Free a value number table. */
1896 free_vn_table (vn_tables_t table)
1898 htab_delete (table->phis);
1899 htab_delete (table->unary);
1900 htab_delete (table->binary);
1901 htab_delete (table->references);
1902 free_alloc_pool (table->unary_op_pool);
1903 free_alloc_pool (table->binary_op_pool);
1904 free_alloc_pool (table->phis_pool);
1905 free_alloc_pool (table->references_pool);
1913 int *rpo_numbers_temp;
1917 calculate_dominance_info (CDI_DOMINATORS);
1921 vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
1922 /* VEC_alloc doesn't actually grow it to the right size, it just
1923 preallocates the space to do so. */
1924 VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
1925 shared_lookup_phiargs = NULL;
1926 shared_lookup_vops = NULL;
1927 shared_lookup_references = NULL;
1928 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
1929 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
1930 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
1932 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
1933 the i'th block in RPO order is bb. We want to map bb's to RPO
1934 numbers, so we need to rearrange this array. */
1935 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
1936 rpo_numbers[rpo_numbers_temp[j]] = j;
1938 free (rpo_numbers_temp);
1940 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
1942 /* Create the VN_INFO structures, and initialize value numbers to
1944 for (i = 0; i < num_ssa_names; i++)
1946 tree name = ssa_name (i);
1949 VN_INFO_GET (name)->valnum = VN_TOP;
1950 VN_INFO (name)->expr = name;
1956 block_stmt_iterator bsi;
1957 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1959 tree stmt = bsi_stmt (bsi);
1960 stmt_ann (stmt)->uid = id++;
1964 /* Create the valid and optimistic value numbering tables. */
1965 valid_info = XCNEW (struct vn_tables_s);
1966 allocate_vn_table (valid_info);
1967 optimistic_info = XCNEW (struct vn_tables_s);
1968 allocate_vn_table (optimistic_info);
1973 switch_to_PRE_table (void)
1975 pre_info = XCNEW (struct vn_tables_s);
1976 allocate_vn_table (pre_info);
1977 current_info = pre_info;
1985 VEC_free (tree, heap, shared_lookup_phiargs);
1986 VEC_free (tree, gc, shared_lookup_vops);
1987 VEC_free (vn_reference_op_s, heap, shared_lookup_references);
1988 XDELETEVEC (rpo_numbers);
1989 for (i = 0; i < num_ssa_names; i++)
1991 tree name = ssa_name (i);
1994 XDELETE (VN_INFO (name));
1995 if (SSA_NAME_VALUE (name) &&
1996 TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
1997 SSA_NAME_VALUE (name) = NULL;
2001 VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
2002 VEC_free (tree, heap, sccstack);
2003 free_vn_table (valid_info);
2004 XDELETE (valid_info);
2005 free_vn_table (optimistic_info);
2006 XDELETE (optimistic_info);
2009 free_vn_table (pre_info);
2021 current_info = valid_info;
2023 for (param = DECL_ARGUMENTS (current_function_decl);
2025 param = TREE_CHAIN (param))
2027 if (gimple_default_def (cfun, param) != NULL)
2029 tree def = gimple_default_def (cfun, param);
2030 SSA_VAL (def) = def;
2034 for (i = num_ssa_names - 1; i > 0; i--)
2036 tree name = ssa_name (i);
2038 && VN_INFO (name)->visited == false
2039 && !has_zero_uses (name))
2043 if (dump_file && (dump_flags & TDF_DETAILS))
2045 fprintf (dump_file, "Value numbers:\n");
2046 for (i = 0; i < num_ssa_names; i++)
2048 tree name = ssa_name (i);
2049 if (name && VN_INFO (name)->visited
2050 && (SSA_VAL (name) != name
2051 || is_gimple_min_invariant (VN_INFO (name)->expr)))
2053 print_generic_expr (dump_file, name, 0);
2054 fprintf (dump_file, " = ");
2055 if (is_gimple_min_invariant (VN_INFO (name)->expr))
2056 print_generic_expr (dump_file, VN_INFO (name)->expr, 0);
2058 print_generic_expr (dump_file, SSA_VAL (name), 0);
2059 fprintf (dump_file, "\n");