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
;
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
;
148 /* Phi nodes in the hashtable consist of their non-VN_TOP phi
149 arguments, and the basic block the phi is in. Result is the value
150 number of the operation, and hashcode is stored to avoid having to
151 calculate it repeatedly. Phi nodes not in the same block are never
152 considered equivalent. */
154 typedef struct vn_phi_s
156 VEC(tree
, heap
) *phiargs
;
162 /* Reference operands only exist in reference operations structures.
163 They consist of an opcode, type, and some number of operands. For
164 a given opcode, some, all, or none of the operands may be used.
165 The operands are there to store the information that makes up the
166 portion of the addressing calculation that opcode performs. */
168 typedef struct vn_reference_op_struct
170 enum tree_code opcode
;
176 typedef vn_reference_op_s
*vn_reference_op_t
;
178 DEF_VEC_O(vn_reference_op_s
);
179 DEF_VEC_ALLOC_O(vn_reference_op_s
, heap
);
181 /* A reference operation in the hashtable is representation as a
182 collection of vuses, representing the memory state at the time of
183 the operation, and a collection of operands that make up the
184 addressing calculation. If two vn_reference_t's have the same set
185 of operands, they access the same memory location. We also store
186 the resulting value number, and the hashcode. The vuses are
187 always stored in order sorted by ssa name version. */
189 typedef struct vn_reference_s
191 VEC(tree
, heap
) *vuses
;
192 VEC(vn_reference_op_s
, heap
) *operands
;
197 /* Valid hashtables storing information we have proven to be
200 static vn_tables_t valid_info
;
202 /* Optimistic hashtables storing information we are making assumptions about
203 during iterations. */
205 static vn_tables_t optimistic_info
;
207 /* Pointer to the set of hashtables that is currently being used.
208 Should always point to either the optimistic_info, or the
211 static vn_tables_t current_info
;
214 /* Reverse post order index for each basic block. */
216 static int *rpo_numbers
;
218 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
220 /* This represents the top of the VN lattice, which is the universal
225 /* Next DFS number and the stack for strongly connected component
228 static unsigned int next_dfs_num
;
229 static VEC (tree
, heap
) *sccstack
;
231 DEF_VEC_P(vn_ssa_aux_t
);
232 DEF_VEC_ALLOC_P(vn_ssa_aux_t
, heap
);
234 /* Table of vn_ssa_aux_t's, one per ssa_name. */
236 static VEC (vn_ssa_aux_t
, heap
) *vn_ssa_aux_table
;
238 /* Return the value numbering information for a given SSA name. */
243 return VEC_index (vn_ssa_aux_t
, vn_ssa_aux_table
,
244 SSA_NAME_VERSION (name
));
247 /* Set the value numbering info for a given SSA name to a given
251 VN_INFO_SET (tree name
, vn_ssa_aux_t value
)
253 VEC_replace (vn_ssa_aux_t
, vn_ssa_aux_table
,
254 SSA_NAME_VERSION (name
), value
);
257 /* Compare two reference operands P1 and P2 for equality. return true if
258 they are equal, and false otherwise. */
261 vn_reference_op_eq (const void *p1
, const void *p2
)
263 const vn_reference_op_t vro1
= (vn_reference_op_t
) p1
;
264 const vn_reference_op_t vro2
= (vn_reference_op_t
) p2
;
265 return vro1
->opcode
== vro2
->opcode
266 && vro1
->type
== vro2
->type
267 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
268 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
269 && expressions_equal_p (vro1
->op2
, vro2
->op2
);
272 /* Compute the hash for a reference operand VRO1 */
275 vn_reference_op_compute_hash (const vn_reference_op_t vro1
)
277 return iterative_hash_expr (vro1
->op0
, vro1
->opcode
)
278 + iterative_hash_expr (vro1
->op1
, vro1
->opcode
)
279 + iterative_hash_expr (vro1
->op2
, vro1
->opcode
);
282 /* Return the hashcode for a given reference operation P1. */
285 vn_reference_hash (const void *p1
)
287 const vn_reference_t vr1
= (vn_reference_t
) p1
;
288 return vr1
->hashcode
;
291 /* Compute a hash for the reference operation VR1 and return it. */
293 static inline hashval_t
294 vn_reference_compute_hash (const vn_reference_t vr1
)
296 hashval_t result
= 0;
299 vn_reference_op_t vro
;
301 for (i
= 0; VEC_iterate (tree
, vr1
->vuses
, i
, v
); i
++)
302 result
+= iterative_hash_expr (v
, 0);
303 for (i
= 0; VEC_iterate (vn_reference_op_s
, vr1
->operands
, i
, vro
); i
++)
304 result
+= vn_reference_op_compute_hash (vro
);
309 /* Return true if reference operations P1 and P2 are equivalent. This
310 means they have the same set of operands and vuses. */
313 vn_reference_eq (const void *p1
, const void *p2
)
317 vn_reference_op_t vro
;
319 const vn_reference_t vr1
= (vn_reference_t
) p1
;
320 const vn_reference_t vr2
= (vn_reference_t
) p2
;
322 if (vr1
->vuses
== vr2
->vuses
323 && vr1
->operands
== vr2
->operands
)
326 /* Impossible for them to be equivalent if they have different
328 if (VEC_length (tree
, vr1
->vuses
) != VEC_length (tree
, vr2
->vuses
))
331 /* We require that address operands be canonicalized in a way that
332 two memory references will have the same operands if they are
334 if (VEC_length (vn_reference_op_s
, vr1
->operands
)
335 != VEC_length (vn_reference_op_s
, vr2
->operands
))
338 /* The memory state is more often different than the address of the
339 store/load, so check it first. */
340 for (i
= 0; VEC_iterate (tree
, vr1
->vuses
, i
, v
); i
++)
342 if (VEC_index (tree
, vr2
->vuses
, i
) != v
)
346 for (i
= 0; VEC_iterate (vn_reference_op_s
, vr1
->operands
, i
, vro
); i
++)
348 if (!vn_reference_op_eq (VEC_index (vn_reference_op_s
, vr2
->operands
, i
),
355 /* Place the vuses from STMT into *result */
358 vuses_to_vec (tree stmt
, VEC (tree
, heap
) **result
)
366 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
367 VEC_safe_push (tree
, heap
, *result
, vuse
);
369 if (VEC_length (tree
, *result
) > 1)
370 sort_vuses_heap (*result
);
374 /* Copy the VUSE names in STMT into a vector, and return
377 static VEC (tree
, heap
) *
378 copy_vuses_from_stmt (tree stmt
)
380 VEC (tree
, heap
) *vuses
= NULL
;
382 vuses_to_vec (stmt
, &vuses
);
387 /* Place the vdefs from STMT into *result */
390 vdefs_to_vec (tree stmt
, VEC (tree
, heap
) **result
)
398 FOR_EACH_SSA_TREE_OPERAND (vdef
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
399 VEC_safe_push (tree
, heap
, *result
, vdef
);
401 if (VEC_length (tree
, *result
) > 1)
402 sort_vuses_heap (*result
);
405 /* Copy the names of vdef results in STMT into a vector, and return
408 static VEC (tree
, heap
) *
409 copy_vdefs_from_stmt (tree stmt
)
411 VEC (tree
, heap
) *vdefs
= NULL
;
413 vdefs_to_vec (stmt
, &vdefs
);
418 /* Place for shared_v{uses/defs}_from_stmt to shove vuses/vdefs. */
419 static VEC (tree
, heap
) *shared_lookup_vops
;
421 /* Copy the virtual uses from STMT into SHARED_LOOKUP_VOPS.
422 This function will overwrite the current SHARED_LOOKUP_VOPS
425 static VEC (tree
, heap
) *
426 shared_vuses_from_stmt (tree stmt
)
428 VEC_truncate (tree
, shared_lookup_vops
, 0);
429 vuses_to_vec (stmt
, &shared_lookup_vops
);
431 return shared_lookup_vops
;
434 /* Copy the operations present in load/store/call REF into RESULT, a vector of
435 vn_reference_op_s's. */
438 copy_reference_ops_from_ref (tree ref
, VEC(vn_reference_op_s
, heap
) **result
)
440 /* Calls are different from all other reference operations. */
441 if (TREE_CODE (ref
) == CALL_EXPR
)
443 vn_reference_op_s temp
;
445 call_expr_arg_iterator iter
;
448 /* Copy the call_expr opcode, type, function being called, and
450 memset (&temp
, 0, sizeof (temp
));
451 temp
.type
= TREE_TYPE (ref
);
452 temp
.opcode
= CALL_EXPR
;
453 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
455 callfn
= get_callee_fndecl (ref
);
457 callfn
= CALL_EXPR_FN (ref
);
458 temp
.type
= TREE_TYPE (callfn
);
459 temp
.opcode
= TREE_CODE (callfn
);
461 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
463 FOR_EACH_CALL_EXPR_ARG (callarg
, iter
, ref
)
465 memset (&temp
, 0, sizeof (temp
));
466 temp
.type
= TREE_TYPE (callarg
);
467 temp
.opcode
= TREE_CODE (callarg
);
469 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
474 /* For non-calls, store the information that makes up the address. */
478 vn_reference_op_s temp
;
479 memset (&temp
, 0, sizeof (temp
));
480 temp
.type
= TREE_TYPE (ref
);
481 temp
.opcode
= TREE_CODE (ref
);
486 /* The only operand is the address, which gets its own
487 vn_reference_op_s structure. */
490 /* Record bits and position. */
491 temp
.op0
= TREE_OPERAND (ref
, 1);
492 temp
.op1
= TREE_OPERAND (ref
, 2);
495 /* Record field as operand. */
496 temp
.op0
= TREE_OPERAND (ref
, 1);
499 /* Record index as operand. */
500 temp
.op0
= TREE_OPERAND (ref
, 1);
501 temp
.op1
= TREE_OPERAND (ref
, 3);
513 VEC_safe_push (vn_reference_op_s
, heap
, *result
, &temp
);
515 if (REFERENCE_CLASS_P (ref
))
516 ref
= TREE_OPERAND (ref
, 0);
522 /* Create a vector of vn_reference_op_s structures from REF, a
523 REFERENCE_CLASS_P tree. The vector is not shared. */
525 static VEC(vn_reference_op_s
, heap
) *
526 create_reference_ops_from_ref (tree ref
)
528 VEC (vn_reference_op_s
, heap
) *result
= NULL
;
530 copy_reference_ops_from_ref (ref
, &result
);
534 static VEC(vn_reference_op_s
, heap
) *shared_lookup_references
;
536 /* Create a vector of vn_reference_op_s structures from REF, a
537 REFERENCE_CLASS_P tree. The vector is shared among all callers of
540 static VEC(vn_reference_op_s
, heap
) *
541 shared_reference_ops_from_ref (tree ref
)
545 VEC_truncate (vn_reference_op_s
, shared_lookup_references
, 0);
546 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
547 return shared_lookup_references
;
551 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
552 structures into their value numbers. This is done in-place, and
553 the vector passed in is returned. */
555 static VEC (vn_reference_op_s
, heap
) *
556 valueize_refs (VEC (vn_reference_op_s
, heap
) *orig
)
558 vn_reference_op_t vro
;
561 for (i
= 0; VEC_iterate (vn_reference_op_s
, orig
, i
, vro
); i
++)
563 if (vro
->opcode
== SSA_NAME
564 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
565 vro
->op0
= SSA_VAL (vro
->op0
);
571 /* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
572 their value numbers. This is done in-place, and the vector passed
575 static VEC (tree
, heap
) *
576 valueize_vuses (VEC (tree
, heap
) *orig
)
581 for (i
= 0; VEC_iterate (tree
, orig
, i
, vuse
); i
++)
582 VEC_replace (tree
, orig
, i
, SSA_VAL (vuse
));
588 /* Lookup OP in the current hash table, and return the resulting
589 value number if it exists in the hash table. Return NULL_TREE if
590 it does not exist in the hash table. */
593 vn_reference_lookup (tree op
, VEC (tree
, heap
) *vuses
)
596 struct vn_reference_s vr1
;
598 vr1
.vuses
= valueize_vuses (vuses
);
599 vr1
.operands
= valueize_refs (shared_reference_ops_from_ref (op
));
600 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
601 slot
= htab_find_slot_with_hash (current_info
->references
, &vr1
, vr1
.hashcode
,
606 return ((vn_reference_t
)*slot
)->result
;
609 /* Insert OP into the current hash table with a value number of
613 vn_reference_insert (tree op
, tree result
, VEC(tree
, heap
) *vuses
)
618 vr1
= (vn_reference_t
) pool_alloc (current_info
->references_pool
);
620 vr1
->vuses
= valueize_vuses (vuses
);
621 vr1
->operands
= valueize_refs (create_reference_ops_from_ref (op
));
622 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
623 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
625 slot
= htab_find_slot_with_hash (current_info
->references
, vr1
, vr1
->hashcode
,
628 /* Because we lookup stores using vuses, and value number failures
629 using the vdefs (see visit_reference_op_store for how and why),
630 it's possible that on failure we may try to insert an already
631 inserted store. This is not wrong, there is no ssa name for a
632 store that we could use as a differentiator anyway. Thus, unlike
633 the other lookup functions, you cannot gcc_assert (!*slot)
641 /* Return the stored hashcode for a unary operation. */
644 vn_unary_op_hash (const void *p1
)
646 const vn_unary_op_t vuo1
= (vn_unary_op_t
) p1
;
647 return vuo1
->hashcode
;
650 /* Hash a unary operation P1 and return the result. */
652 static inline hashval_t
653 vn_unary_op_compute_hash (const vn_unary_op_t vuo1
)
655 return iterative_hash_expr (vuo1
->op0
, vuo1
->opcode
);
658 /* Return true if P1 and P2, two unary operations, are equivalent. */
661 vn_unary_op_eq (const void *p1
, const void *p2
)
663 const vn_unary_op_t vuo1
= (vn_unary_op_t
) p1
;
664 const vn_unary_op_t vuo2
= (vn_unary_op_t
) p2
;
665 return vuo1
->opcode
== vuo2
->opcode
666 && vuo1
->type
== vuo2
->type
667 && expressions_equal_p (vuo1
->op0
, vuo2
->op0
);
670 /* Lookup OP in the current hash table, and return the resulting
671 value number if it exists in the hash table. Return NULL_TREE if
672 it does not exist in the hash table. */
675 vn_unary_op_lookup (tree op
)
678 struct vn_unary_op_s vuo1
;
680 vuo1
.opcode
= TREE_CODE (op
);
681 vuo1
.type
= TREE_TYPE (op
);
682 vuo1
.op0
= TREE_OPERAND (op
, 0);
684 if (TREE_CODE (vuo1
.op0
) == SSA_NAME
)
685 vuo1
.op0
= SSA_VAL (vuo1
.op0
);
687 vuo1
.hashcode
= vn_unary_op_compute_hash (&vuo1
);
688 slot
= htab_find_slot_with_hash (current_info
->unary
, &vuo1
, vuo1
.hashcode
,
692 return ((vn_unary_op_t
)*slot
)->result
;
695 /* Insert OP into the current hash table with a value number of
699 vn_unary_op_insert (tree op
, tree result
)
702 vn_unary_op_t vuo1
= (vn_unary_op_t
) pool_alloc (current_info
->unary_op_pool
);
704 vuo1
->opcode
= TREE_CODE (op
);
705 vuo1
->type
= TREE_TYPE (op
);
706 vuo1
->op0
= TREE_OPERAND (op
, 0);
707 vuo1
->result
= result
;
709 if (TREE_CODE (vuo1
->op0
) == SSA_NAME
)
710 vuo1
->op0
= SSA_VAL (vuo1
->op0
);
712 vuo1
->hashcode
= vn_unary_op_compute_hash (vuo1
);
713 slot
= htab_find_slot_with_hash (current_info
->unary
, vuo1
, vuo1
->hashcode
,
719 /* Compute and return the hash value for binary operation VBO1. */
721 static inline hashval_t
722 vn_binary_op_compute_hash (const vn_binary_op_t vbo1
)
724 return iterative_hash_expr (vbo1
->op0
, vbo1
->opcode
)
725 + iterative_hash_expr (vbo1
->op1
, vbo1
->opcode
);
728 /* Return the computed hashcode for binary operation P1. */
731 vn_binary_op_hash (const void *p1
)
733 const vn_binary_op_t vbo1
= (vn_binary_op_t
) p1
;
734 return vbo1
->hashcode
;
737 /* Compare binary operations P1 and P2 and return true if they are
741 vn_binary_op_eq (const void *p1
, const void *p2
)
743 const vn_binary_op_t vbo1
= (vn_binary_op_t
) p1
;
744 const vn_binary_op_t vbo2
= (vn_binary_op_t
) p2
;
745 return vbo1
->opcode
== vbo2
->opcode
746 && vbo1
->type
== vbo2
->type
747 && expressions_equal_p (vbo1
->op0
, vbo2
->op0
)
748 && expressions_equal_p (vbo1
->op1
, vbo2
->op1
);
751 /* Lookup OP in the current hash table, and return the resulting
752 value number if it exists in the hash table. Return NULL_TREE if
753 it does not exist in the hash table. */
756 vn_binary_op_lookup (tree op
)
759 struct vn_binary_op_s vbo1
;
761 vbo1
.opcode
= TREE_CODE (op
);
762 vbo1
.type
= TREE_TYPE (op
);
763 vbo1
.op0
= TREE_OPERAND (op
, 0);
764 vbo1
.op1
= TREE_OPERAND (op
, 1);
766 if (TREE_CODE (vbo1
.op0
) == SSA_NAME
)
767 vbo1
.op0
= SSA_VAL (vbo1
.op0
);
768 if (TREE_CODE (vbo1
.op1
) == SSA_NAME
)
769 vbo1
.op1
= SSA_VAL (vbo1
.op1
);
771 if (tree_swap_operands_p (vbo1
.op0
, vbo1
.op1
, false)
772 && commutative_tree_code (vbo1
.opcode
))
774 tree temp
= vbo1
.op0
;
779 vbo1
.hashcode
= vn_binary_op_compute_hash (&vbo1
);
780 slot
= htab_find_slot_with_hash (current_info
->binary
, &vbo1
, vbo1
.hashcode
,
784 return ((vn_binary_op_t
)*slot
)->result
;
787 /* Insert OP into the current hash table with a value number of
791 vn_binary_op_insert (tree op
, tree result
)
795 vbo1
= (vn_binary_op_t
) pool_alloc (current_info
->binary_op_pool
);
797 vbo1
->opcode
= TREE_CODE (op
);
798 vbo1
->type
= TREE_TYPE (op
);
799 vbo1
->op0
= TREE_OPERAND (op
, 0);
800 vbo1
->op1
= TREE_OPERAND (op
, 1);
801 vbo1
->result
= result
;
803 if (TREE_CODE (vbo1
->op0
) == SSA_NAME
)
804 vbo1
->op0
= SSA_VAL (vbo1
->op0
);
805 if (TREE_CODE (vbo1
->op1
) == SSA_NAME
)
806 vbo1
->op1
= SSA_VAL (vbo1
->op1
);
808 if (tree_swap_operands_p (vbo1
->op0
, vbo1
->op1
, false)
809 && commutative_tree_code (vbo1
->opcode
))
811 tree temp
= vbo1
->op0
;
812 vbo1
->op0
= vbo1
->op1
;
815 vbo1
->hashcode
= vn_binary_op_compute_hash (vbo1
);
816 slot
= htab_find_slot_with_hash (current_info
->binary
, vbo1
, vbo1
->hashcode
,
823 /* Compute a hashcode for PHI operation VP1 and return it. */
825 static inline hashval_t
826 vn_phi_compute_hash (vn_phi_t vp1
)
828 hashval_t result
= 0;
832 result
= vp1
->block
->index
;
834 for (i
= 0; VEC_iterate (tree
, vp1
->phiargs
, i
, phi1op
); i
++)
836 if (phi1op
== VN_TOP
)
838 result
+= iterative_hash_expr (phi1op
, result
);
844 /* Return the computed hashcode for phi operation P1. */
847 vn_phi_hash (const void *p1
)
849 const vn_phi_t vp1
= (vn_phi_t
) p1
;
850 return vp1
->hashcode
;
853 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
856 vn_phi_eq (const void *p1
, const void *p2
)
858 const vn_phi_t vp1
= (vn_phi_t
) p1
;
859 const vn_phi_t vp2
= (vn_phi_t
) p2
;
861 if (vp1
->block
== vp2
->block
)
866 /* Any phi in the same block will have it's arguments in the
867 same edge order, because of how we store phi nodes. */
868 for (i
= 0; VEC_iterate (tree
, vp1
->phiargs
, i
, phi1op
); i
++)
870 tree phi2op
= VEC_index (tree
, vp2
->phiargs
, i
);
871 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
873 if (!expressions_equal_p (phi1op
, phi2op
))
881 static VEC(tree
, heap
) *shared_lookup_phiargs
;
883 /* Lookup PHI in the current hash table, and return the resulting
884 value number if it exists in the hash table. Return NULL_TREE if
885 it does not exist in the hash table. */
888 vn_phi_lookup (tree phi
)
894 VEC_truncate (tree
, shared_lookup_phiargs
, 0);
896 /* Canonicalize the SSA_NAME's to their value number. */
897 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
899 tree def
= PHI_ARG_DEF (phi
, i
);
900 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
901 VEC_safe_push (tree
, heap
, shared_lookup_phiargs
, def
);
903 vp1
.phiargs
= shared_lookup_phiargs
;
904 vp1
.block
= bb_for_stmt (phi
);
905 vp1
.hashcode
= vn_phi_compute_hash (&vp1
);
906 slot
= htab_find_slot_with_hash (current_info
->phis
, &vp1
, vp1
.hashcode
,
910 return ((vn_phi_t
)*slot
)->result
;
913 /* Insert PHI into the current hash table with a value number of
917 vn_phi_insert (tree phi
, tree result
)
920 vn_phi_t vp1
= (vn_phi_t
) pool_alloc (current_info
->phis_pool
);
922 VEC (tree
, heap
) *args
= NULL
;
924 /* Canonicalize the SSA_NAME's to their value number. */
925 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
927 tree def
= PHI_ARG_DEF (phi
, i
);
928 def
= TREE_CODE (def
) == SSA_NAME
? SSA_VAL (def
) : def
;
929 VEC_safe_push (tree
, heap
, args
, def
);
932 vp1
->block
= bb_for_stmt (phi
);
933 vp1
->result
= result
;
934 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
936 slot
= htab_find_slot_with_hash (current_info
->phis
, vp1
, vp1
->hashcode
,
939 /* Because we iterate over phi operations more than once, it's
940 possible the slot might already exist here, hence no assert.*/
945 /* Print set of components in strongly connected component SCC to OUT. */
948 print_scc (FILE *out
, VEC (tree
, heap
) *scc
)
953 fprintf (out
, "SCC consists of: ");
954 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
956 print_generic_expr (out
, var
, 0);
962 /* Set the value number of FROM to TO, return true if it has changed
966 set_ssa_val_to (tree from
, tree to
)
968 gcc_assert (to
!= NULL
);
970 /* Make sure we don't create chains of copies, so that we get the
971 best value numbering. visit_copy has code to make sure this doesn't
972 happen, we are doing this here to assert that nothing else breaks
974 gcc_assert (TREE_CODE (to
) != SSA_NAME
975 || TREE_CODE (SSA_VAL (to
)) != SSA_NAME
976 || SSA_VAL (to
) == to
978 /* The only thing we allow as value numbers are ssa_names and
979 invariants. So assert that here. */
980 gcc_assert (TREE_CODE (to
) == SSA_NAME
|| is_gimple_min_invariant (to
));
982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
984 fprintf (dump_file
, "Setting value number of ");
985 print_generic_expr (dump_file
, from
, 0);
986 fprintf (dump_file
, " to ");
987 print_generic_expr (dump_file
, to
, 0);
988 fprintf (dump_file
, "\n");
991 if (SSA_VAL (from
) != to
)
999 /* Set all definitions in STMT to value number to themselves.
1000 Return true if a value number changed. */
1003 defs_to_varying (tree stmt
)
1005 bool changed
= false;
1009 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1011 tree def
= DEF_FROM_PTR (defp
);
1013 VN_INFO (def
)->use_processed
= true;
1014 changed
|= set_ssa_val_to (def
, def
);
1019 /* Visit a copy between LHS and RHS, return true if the value number
1023 visit_copy (tree lhs
, tree rhs
)
1026 /* Follow chains of copies to their destination. */
1027 while (SSA_VAL (rhs
) != rhs
&& TREE_CODE (SSA_VAL (rhs
)) == SSA_NAME
)
1028 rhs
= SSA_VAL (rhs
);
1030 /* The copy may have a more interesting constant filled expression
1031 (we don't, since we know our RHS is just an SSA name). */
1032 VN_INFO (lhs
)->has_constants
= VN_INFO (rhs
)->has_constants
;
1033 VN_INFO (lhs
)->expr
= VN_INFO (rhs
)->expr
;
1035 return set_ssa_val_to (lhs
, rhs
);
1038 /* Visit a unary operator RHS, value number it, and return true if the
1039 value number of LHS has changed as a result. */
1042 visit_unary_op (tree lhs
, tree op
)
1044 bool changed
= false;
1045 tree result
= vn_unary_op_lookup (op
);
1049 changed
= set_ssa_val_to (lhs
, result
);
1053 changed
= set_ssa_val_to (lhs
, lhs
);
1054 vn_unary_op_insert (op
, lhs
);
1060 /* Visit a binary operator RHS, value number it, and return true if the
1061 value number of LHS has changed as a result. */
1064 visit_binary_op (tree lhs
, tree op
)
1066 bool changed
= false;
1067 tree result
= vn_binary_op_lookup (op
);
1071 changed
= set_ssa_val_to (lhs
, result
);
1075 changed
= set_ssa_val_to (lhs
, lhs
);
1076 vn_binary_op_insert (op
, lhs
);
1082 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1083 and return true if the value number of the LHS has changed as a result. */
1086 visit_reference_op_load (tree lhs
, tree op
, tree stmt
)
1088 bool changed
= false;
1089 tree result
= vn_reference_lookup (op
, shared_vuses_from_stmt (stmt
));
1093 changed
= set_ssa_val_to (lhs
, result
);
1097 changed
= set_ssa_val_to (lhs
, lhs
);
1098 vn_reference_insert (op
, lhs
, copy_vuses_from_stmt (stmt
));
1105 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1106 and return true if the value number of the LHS has changed as a result. */
1109 visit_reference_op_store (tree lhs
, tree op
, tree stmt
)
1111 bool changed
= false;
1113 bool resultsame
= false;
1115 /* First we want to lookup using the *vuses* from the store and see
1116 if there the last store to this location with the same address
1119 The vuses represent the memory state before the store. If the
1120 memory state, address, and value of the store is the same as the
1121 last store to this location, then this store will produce the
1122 same memory state as that store.
1124 In this case the vdef versions for this store are value numbered to those
1125 vuse versions, since they represent the same memory state after
1128 Otherwise, the vdefs for the store are used when inserting into
1129 the table, since the store generates a new memory state. */
1131 result
= vn_reference_lookup (lhs
, shared_vuses_from_stmt (stmt
));
1135 if (TREE_CODE (result
) == SSA_NAME
)
1136 result
= SSA_VAL (result
);
1137 resultsame
= expressions_equal_p (result
, op
);
1140 if (!result
|| !resultsame
)
1142 VEC(tree
, heap
) *vdefs
= copy_vdefs_from_stmt (stmt
);
1146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1148 fprintf (dump_file
, "No store match\n");
1149 fprintf (dump_file
, "Value numbering store ");
1150 print_generic_expr (dump_file
, lhs
, 0);
1151 fprintf (dump_file
, " to ");
1152 print_generic_expr (dump_file
, op
, 0);
1153 fprintf (dump_file
, "\n");
1155 /* Have to set value numbers before insert, since insert is
1156 going to valueize the references in-place. */
1157 for (i
= 0; VEC_iterate (tree
, vdefs
, i
, vdef
); i
++)
1159 VN_INFO (vdef
)->use_processed
= true;
1160 changed
|= set_ssa_val_to (vdef
, vdef
);
1163 vn_reference_insert (lhs
, op
, vdefs
);
1167 /* We had a match, so value number the vdefs to have the value
1168 number of the vuses they came from. */
1169 ssa_op_iter op_iter
;
1173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1174 fprintf (dump_file
, "Store matched earlier value,"
1175 "value numbering store vdefs to matching vuses.\n");
1177 FOR_EACH_SSA_VDEF_OPERAND (var
, vv
, stmt
, op_iter
)
1179 tree def
= DEF_FROM_PTR (var
);
1182 /* Uh, if the vuse is a multiuse, we can't really do much
1183 here, sadly, since we don't know which value number of
1184 which vuse to use. */
1185 if (VUSE_VECT_NUM_ELEM (*vv
) != 1)
1188 use
= VUSE_ELEMENT_VAR (*vv
, 0);
1190 VN_INFO (def
)->use_processed
= true;
1191 changed
|= set_ssa_val_to (def
, SSA_VAL (use
));
1198 /* Visit and value number PHI, return true if the value number
1202 visit_phi (tree phi
)
1204 bool changed
= false;
1206 tree sameval
= VN_TOP
;
1207 bool allsame
= true;
1210 /* See if all non-TOP arguments have the same value. TOP is
1211 equivalent to everything, so we can ignore it. */
1212 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1214 tree def
= PHI_ARG_DEF (phi
, i
);
1216 if (TREE_CODE (def
) == SSA_NAME
)
1217 def
= SSA_VAL (def
);
1220 if (sameval
== VN_TOP
)
1226 if (!expressions_equal_p (def
, sameval
))
1234 /* If all value numbered to the same value, the phi node has that
1238 if (is_gimple_min_invariant (sameval
))
1240 VN_INFO (PHI_RESULT (phi
))->has_constants
= true;
1241 VN_INFO (PHI_RESULT (phi
))->expr
= sameval
;
1243 if (TREE_CODE (sameval
) == SSA_NAME
)
1244 return visit_copy (PHI_RESULT (phi
), sameval
);
1246 return set_ssa_val_to (PHI_RESULT (phi
), sameval
);
1249 /* Otherwise, see if it is equivalent to a phi node in this block. */
1250 result
= vn_phi_lookup (phi
);
1252 changed
= set_ssa_val_to (PHI_RESULT (phi
), result
);
1255 vn_phi_insert (phi
, PHI_RESULT (phi
));
1256 VN_INFO (PHI_RESULT (phi
))->has_constants
= false;
1257 VN_INFO (PHI_RESULT (phi
))->expr
= PHI_RESULT (phi
);
1258 changed
= set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
1264 /* Return true if EXPR contains constants. */
1267 expr_has_constants (tree expr
)
1269 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1272 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0));
1275 return is_gimple_min_invariant (TREE_OPERAND (expr
, 0))
1276 || is_gimple_min_invariant (TREE_OPERAND (expr
, 1));
1277 /* Constants inside reference ops are rarely interesting, but
1278 it can take a lot of looking to find them. */
1282 return is_gimple_min_invariant (expr
);
1287 /* Replace SSA_NAMES in expr with their value numbers, and return the
1289 This is performed in place. */
1292 valueize_expr (tree expr
)
1294 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1297 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
1298 && SSA_VAL (TREE_OPERAND (expr
, 0)) != VN_TOP
)
1299 TREE_OPERAND (expr
, 0) = SSA_VAL (TREE_OPERAND (expr
, 0));
1302 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
1303 && SSA_VAL (TREE_OPERAND (expr
, 0)) != VN_TOP
)
1304 TREE_OPERAND (expr
, 0) = SSA_VAL (TREE_OPERAND (expr
, 0));
1305 if (TREE_CODE (TREE_OPERAND (expr
, 1)) == SSA_NAME
1306 && SSA_VAL (TREE_OPERAND (expr
, 1)) != VN_TOP
)
1307 TREE_OPERAND (expr
, 1) = SSA_VAL (TREE_OPERAND (expr
, 1));
1315 /* Simplify the binary expression RHS, and return the result if
1319 simplify_binary_expression (tree rhs
)
1321 tree result
= NULL_TREE
;
1322 tree op0
= TREE_OPERAND (rhs
, 0);
1323 tree op1
= TREE_OPERAND (rhs
, 1);
1325 /* This will not catch every single case we could combine, but will
1326 catch those with constants. The goal here is to simultaneously
1327 combine constants between expressions, but avoid infinite
1328 expansion of expressions during simplification. */
1329 if (TREE_CODE (op0
) == SSA_NAME
)
1331 if (VN_INFO (op0
)->has_constants
)
1332 op0
= valueize_expr (VN_INFO (op0
)->expr
);
1333 else if (SSA_VAL (op0
) != VN_TOP
&& SSA_VAL (op0
) != op0
)
1334 op0
= VN_INFO (op0
)->valnum
;
1337 if (TREE_CODE (op1
) == SSA_NAME
)
1339 if (VN_INFO (op1
)->has_constants
)
1340 op1
= valueize_expr (VN_INFO (op1
)->expr
);
1341 else if (SSA_VAL (op1
) != VN_TOP
&& SSA_VAL (op1
) != op1
)
1342 op1
= VN_INFO (op1
)->valnum
;
1344 result
= fold_binary (TREE_CODE (rhs
), TREE_TYPE (rhs
), op0
, op1
);
1346 /* Make sure result is not a complex expression consiting
1347 of operators of operators (IE (a + b) + (a + c))
1348 Otherwise, we will end up with unbounded expressions if
1349 fold does anything at all. */
1352 if (is_gimple_min_invariant (result
))
1354 else if (SSA_VAR_P (result
))
1356 else if (EXPR_P (result
))
1358 switch (TREE_CODE_CLASS (TREE_CODE (result
)))
1362 tree op0
= TREE_OPERAND (result
, 0);
1369 tree op0
= TREE_OPERAND (result
, 0);
1370 tree op1
= TREE_OPERAND (result
, 1);
1371 if (!EXPR_P (op0
) && !EXPR_P (op1
))
1383 /* Try to simplify RHS using equivalences and constant folding. */
1386 try_to_simplify (tree stmt
, tree rhs
)
1388 if (TREE_CODE (rhs
) == SSA_NAME
)
1390 if (is_gimple_min_invariant (SSA_VAL (rhs
)))
1391 return SSA_VAL (rhs
);
1392 else if (VN_INFO (rhs
)->has_constants
)
1393 return VN_INFO (rhs
)->expr
;
1397 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1399 /* For references, see if we find a result for the lookup,
1400 and use it if we do. */
1404 tree result
= vn_reference_lookup (rhs
,
1405 shared_vuses_from_stmt (stmt
));
1410 /* We could do a little more with unary ops, if they expand
1411 into binary ops, but it's debatable whether it is worth it. */
1414 tree result
= NULL_TREE
;
1415 tree op0
= TREE_OPERAND (rhs
, 0);
1416 if (TREE_CODE (op0
) == SSA_NAME
&& VN_INFO (op0
)->has_constants
)
1417 op0
= VN_INFO (op0
)->expr
;
1418 else if (TREE_CODE (op0
) == SSA_NAME
&& SSA_VAL (op0
) != op0
)
1419 op0
= SSA_VAL (op0
);
1420 result
= fold_unary (TREE_CODE (rhs
), TREE_TYPE (rhs
), op0
);
1427 return simplify_binary_expression (rhs
);
1437 /* Visit and value number USE, return true if the value number
1441 visit_use (tree use
)
1443 bool changed
= false;
1444 tree stmt
= SSA_NAME_DEF_STMT (use
);
1447 VN_INFO (use
)->use_processed
= true;
1449 gcc_assert (!SSA_NAME_IN_FREE_LIST (use
));
1450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1452 fprintf (dump_file
, "Value numbering ");
1453 print_generic_expr (dump_file
, use
, 0);
1454 fprintf (dump_file
, " stmt = ");
1455 print_generic_stmt (dump_file
, stmt
, 0);
1458 /* RETURN_EXPR may have an embedded MODIFY_STMT. */
1459 if (TREE_CODE (stmt
) == RETURN_EXPR
1460 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
1461 stmt
= TREE_OPERAND (stmt
, 0);
1463 ann
= stmt_ann (stmt
);
1465 /* Handle uninitialized uses. */
1466 if (IS_EMPTY_STMT (stmt
))
1468 changed
= set_ssa_val_to (use
, use
);
1472 if (TREE_CODE (stmt
) == PHI_NODE
)
1474 changed
= visit_phi (stmt
);
1476 else if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
1477 || (ann
&& ann
->has_volatile_ops
))
1479 changed
= defs_to_varying (stmt
);
1483 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1484 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1487 STRIP_USELESS_TYPE_CONVERSION (rhs
);
1489 simplified
= try_to_simplify (stmt
, rhs
);
1490 if (simplified
&& simplified
!= rhs
)
1492 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1494 fprintf (dump_file
, "RHS ");
1495 print_generic_expr (dump_file
, rhs
, 0);
1496 fprintf (dump_file
, " simplified to ");
1497 print_generic_expr (dump_file
, simplified
, 0);
1498 if (TREE_CODE (lhs
) == SSA_NAME
)
1499 fprintf (dump_file
, " has constants %d\n",
1500 VN_INFO (lhs
)->has_constants
);
1502 fprintf (dump_file
, "\n");
1506 /* Setting value numbers to constants will screw up phi
1507 congruence because constants are not uniquely
1508 associated with a single ssa name that can be looked up.
1510 if (simplified
&& is_gimple_min_invariant (simplified
)
1511 && TREE_CODE (lhs
) == SSA_NAME
1512 && simplified
!= rhs
)
1514 VN_INFO (lhs
)->expr
= simplified
;
1515 VN_INFO (lhs
)->has_constants
= true;
1516 changed
= set_ssa_val_to (lhs
, simplified
);
1519 else if (simplified
&& TREE_CODE (simplified
) == SSA_NAME
1520 && TREE_CODE (lhs
) == SSA_NAME
)
1522 changed
= visit_copy (lhs
, simplified
);
1525 else if (simplified
)
1529 if (TREE_CODE (lhs
) == SSA_NAME
)
1531 VN_INFO (lhs
)->has_constants
= expr_has_constants (simplified
);
1532 /* We have to unshare the expression or else
1533 valuizing may change the IL stream. */
1534 VN_INFO (lhs
)->expr
= unshare_expr (simplified
);
1537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1539 fprintf (dump_file
, "RHS ");
1540 print_generic_expr (dump_file
, oldrhs
, 0);
1541 fprintf (dump_file
, " simplified to ");
1542 print_generic_expr (dump_file
, simplified
, 0);
1543 if (TREE_CODE (lhs
) == SSA_NAME
)
1544 fprintf (dump_file
, " has constants %d\n",
1545 VN_INFO (lhs
)->has_constants
);
1547 fprintf (dump_file
, "\n");
1551 else if (expr_has_constants (rhs
) && TREE_CODE (lhs
) == SSA_NAME
)
1553 VN_INFO (lhs
)->has_constants
= true;
1554 VN_INFO (lhs
)->expr
= unshare_expr (rhs
);
1556 else if (TREE_CODE (lhs
) == SSA_NAME
)
1558 /* We reset expr and constantness here because we may
1559 have been value numbering optimistically, and
1560 iterating. They may become non-constant in this case,
1561 even if they were optimistically constant. */
1563 VN_INFO (lhs
)->has_constants
= false;
1564 VN_INFO (lhs
)->expr
= lhs
;
1567 if (TREE_CODE (lhs
) == SSA_NAME
1568 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1569 changed
= defs_to_varying (stmt
);
1570 else if (REFERENCE_CLASS_P (lhs
))
1572 changed
= visit_reference_op_store (lhs
, rhs
, stmt
);
1574 else if (TREE_CODE (lhs
) == SSA_NAME
)
1576 if (is_gimple_min_invariant (rhs
))
1578 VN_INFO (lhs
)->has_constants
= true;
1579 VN_INFO (lhs
)->expr
= rhs
;
1580 changed
= set_ssa_val_to (lhs
, rhs
);
1582 else if (TREE_CODE (rhs
) == SSA_NAME
)
1583 changed
= visit_copy (lhs
, rhs
);
1586 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1589 changed
= visit_unary_op (lhs
, rhs
);
1592 changed
= visit_binary_op (lhs
, rhs
);
1594 /* If tcc_vl_expr ever encompasses more than
1595 CALL_EXPR, this will need to be changed. */
1597 if (call_expr_flags (rhs
) & (ECF_PURE
| ECF_CONST
))
1598 changed
= visit_reference_op_load (lhs
, rhs
, stmt
);
1600 changed
= defs_to_varying (stmt
);
1602 case tcc_declaration
:
1604 changed
= visit_reference_op_load (lhs
, rhs
, stmt
);
1606 case tcc_expression
:
1607 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1609 changed
= visit_unary_op (lhs
, rhs
);
1614 changed
= defs_to_varying (stmt
);
1620 changed
= defs_to_varying (stmt
);
1627 /* Compare two operands by reverse postorder index */
1630 compare_ops (const void *pa
, const void *pb
)
1632 const tree opa
= *((const tree
*)pa
);
1633 const tree opb
= *((const tree
*)pb
);
1634 tree opstmta
= SSA_NAME_DEF_STMT (opa
);
1635 tree opstmtb
= SSA_NAME_DEF_STMT (opb
);
1639 if (IS_EMPTY_STMT (opstmta
) && IS_EMPTY_STMT (opstmtb
))
1641 else if (IS_EMPTY_STMT (opstmta
))
1643 else if (IS_EMPTY_STMT (opstmtb
))
1646 bba
= bb_for_stmt (opstmta
);
1647 bbb
= bb_for_stmt (opstmtb
);
1658 if (TREE_CODE (opstmta
) == PHI_NODE
&& TREE_CODE (opstmtb
) == PHI_NODE
)
1660 else if (TREE_CODE (opstmta
) == PHI_NODE
)
1662 else if (TREE_CODE (opstmtb
) == PHI_NODE
)
1664 return stmt_ann (opstmta
)->uid
- stmt_ann (opstmtb
)->uid
;
1666 return rpo_numbers
[bba
->index
] - rpo_numbers
[bbb
->index
];
1669 /* Sort an array containing members of a strongly connected component
1670 SCC so that the members are ordered by RPO number.
1671 This means that when the sort is complete, iterating through the
1672 array will give you the members in RPO order. */
1675 sort_scc (VEC (tree
, heap
) *scc
)
1677 qsort (VEC_address (tree
, scc
),
1678 VEC_length (tree
, scc
),
1683 /* Process a strongly connected component in the SSA graph. */
1686 process_scc (VEC (tree
, heap
) *scc
)
1688 /* If the SCC has a single member, just visit it. */
1690 if (VEC_length (tree
, scc
) == 1)
1692 tree use
= VEC_index (tree
, scc
, 0);
1693 if (!VN_INFO (use
)->use_processed
)
1700 unsigned int iterations
= 0;
1701 bool changed
= true;
1703 /* Iterate over the SCC with the optimistic table until it stops
1705 current_info
= optimistic_info
;
1710 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
1711 changed
|= visit_use (var
);
1714 if (dump_file
&& (dump_flags
& TDF_STATS
))
1715 fprintf (dump_file
, "Processing SCC required %d iterations\n",
1718 /* Finally, visit the SCC once using the valid table. */
1719 current_info
= valid_info
;
1720 for (i
= 0; VEC_iterate (tree
, scc
, i
, var
); i
++)
1725 /* Depth first search on NAME to discover and process SCC's in the SSA
1727 Execution of this algorithm relies on the fact that the SCC's are
1728 popped off the stack in topological order. */
1738 VN_INFO (name
)->dfsnum
= next_dfs_num
++;
1739 VN_INFO (name
)->visited
= true;
1740 VN_INFO (name
)->low
= VN_INFO (name
)->dfsnum
;
1742 VEC_safe_push (tree
, heap
, sccstack
, name
);
1743 VN_INFO (name
)->on_sccstack
= true;
1744 defstmt
= SSA_NAME_DEF_STMT (name
);
1746 /* Recursively DFS on our operands, looking for SCC's. */
1747 if (!IS_EMPTY_STMT (defstmt
))
1749 FOR_EACH_PHI_OR_STMT_USE (usep
, SSA_NAME_DEF_STMT (name
), iter
,
1752 tree use
= USE_FROM_PTR (usep
);
1754 /* Since we handle phi nodes, we will sometimes get
1755 invariants in the use expression. */
1756 if (TREE_CODE (use
) != SSA_NAME
)
1759 if (! (VN_INFO (use
)->visited
))
1762 VN_INFO (name
)->low
= MIN (VN_INFO (name
)->low
,
1763 VN_INFO (use
)->low
);
1765 if (VN_INFO (use
)->dfsnum
< VN_INFO (name
)->dfsnum
1766 && VN_INFO (use
)->on_sccstack
)
1768 VN_INFO (name
)->low
= MIN (VN_INFO (use
)->dfsnum
,
1769 VN_INFO (name
)->low
);
1774 /* See if we found an SCC. */
1775 if (VN_INFO (name
)->low
== VN_INFO (name
)->dfsnum
)
1777 VEC (tree
, heap
) *scc
= NULL
;
1780 /* Found an SCC, pop the components off the SCC stack and
1784 x
= VEC_pop (tree
, sccstack
);
1786 VN_INFO (x
)->on_sccstack
= false;
1787 VEC_safe_push (tree
, heap
, scc
, x
);
1788 } while (x
!= name
);
1790 if (VEC_length (tree
, scc
) > 1)
1793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1794 print_scc (dump_file
, scc
);
1798 VEC_free (tree
, heap
, scc
);
1806 VEC_free (tree
, heap
, phi
->phiargs
);
1810 /* Free a reference operation structure VP. */
1813 free_reference (void *vp
)
1815 vn_reference_t vr
= vp
;
1816 VEC_free (tree
, heap
, vr
->vuses
);
1817 VEC_free (vn_reference_op_s
, heap
, vr
->operands
);
1820 /* Allocate a value number table. */
1823 allocate_vn_table (vn_tables_t table
)
1825 table
->phis
= htab_create (23, vn_phi_hash
, vn_phi_eq
, free_phi
);
1826 table
->unary
= htab_create (23, vn_unary_op_hash
, vn_unary_op_eq
, NULL
);
1827 table
->binary
= htab_create (23, vn_binary_op_hash
, vn_binary_op_eq
, NULL
);
1828 table
->references
= htab_create (23, vn_reference_hash
, vn_reference_eq
,
1831 table
->unary_op_pool
= create_alloc_pool ("VN unary operations",
1832 sizeof (struct vn_unary_op_s
),
1834 table
->binary_op_pool
= create_alloc_pool ("VN binary operations",
1835 sizeof (struct vn_binary_op_s
),
1837 table
->phis_pool
= create_alloc_pool ("VN phis",
1838 sizeof (struct vn_phi_s
),
1840 table
->references_pool
= create_alloc_pool ("VN references",
1841 sizeof (struct vn_reference_s
),
1845 /* Free a value number table. */
1848 free_vn_table (vn_tables_t table
)
1850 htab_delete (table
->phis
);
1851 htab_delete (table
->unary
);
1852 htab_delete (table
->binary
);
1853 htab_delete (table
->references
);
1854 free_alloc_pool (table
->unary_op_pool
);
1855 free_alloc_pool (table
->binary_op_pool
);
1856 free_alloc_pool (table
->phis_pool
);
1857 free_alloc_pool (table
->references_pool
);
1865 int *rpo_numbers_temp
;
1869 calculate_dominance_info (CDI_DOMINATORS
);
1873 vn_ssa_aux_table
= VEC_alloc (vn_ssa_aux_t
, heap
, num_ssa_names
+ 1);
1874 /* VEC_alloc doesn't actually grow it to the right size, it just
1875 preallocates the space to do so. */
1876 VEC_safe_grow (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
, num_ssa_names
+ 1);
1877 shared_lookup_phiargs
= NULL
;
1878 shared_lookup_vops
= NULL
;
1879 shared_lookup_references
= NULL
;
1880 rpo_numbers
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
1881 rpo_numbers_temp
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
1882 pre_and_rev_post_order_compute (NULL
, rpo_numbers_temp
, false);
1884 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
1885 the i'th block in RPO order is bb. We want to map bb's to RPO
1886 numbers, so we need to rearrange this array. */
1887 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
1888 rpo_numbers
[rpo_numbers_temp
[j
]] = j
;
1890 free (rpo_numbers_temp
);
1892 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
1894 /* Create the VN_INFO structures, and initialize value numbers to
1896 for (i
= 0; i
< num_ssa_names
; i
++)
1898 tree name
= ssa_name (i
);
1901 VN_INFO_SET (name
, XCNEW (struct vn_ssa_aux
));
1902 VN_INFO (name
)->valnum
= VN_TOP
;
1903 VN_INFO (name
)->expr
= name
;
1909 block_stmt_iterator bsi
;
1910 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1912 tree stmt
= bsi_stmt (bsi
);
1913 stmt_ann (stmt
)->uid
= id
++;
1917 /* Create the valid and optimistic value numbering tables. */
1918 valid_info
= XCNEW (struct vn_tables_s
);
1919 allocate_vn_table (valid_info
);
1920 optimistic_info
= XCNEW (struct vn_tables_s
);
1921 allocate_vn_table (optimistic_info
);
1929 VEC_free (tree
, heap
, shared_lookup_phiargs
);
1930 VEC_free (tree
, heap
, shared_lookup_vops
);
1931 VEC_free (vn_reference_op_s
, heap
, shared_lookup_references
);
1932 XDELETEVEC (rpo_numbers
);
1933 for (i
= 0; i
< num_ssa_names
; i
++)
1935 tree name
= ssa_name (i
);
1937 XDELETE (VN_INFO (name
));
1939 VEC_free (vn_ssa_aux_t
, heap
, vn_ssa_aux_table
);
1940 VEC_free (tree
, heap
, sccstack
);
1941 free_vn_table (valid_info
);
1942 XDELETE (valid_info
);
1943 free_vn_table (optimistic_info
);
1944 XDELETE (optimistic_info
);
1954 current_info
= valid_info
;
1956 for (param
= DECL_ARGUMENTS (current_function_decl
);
1958 param
= TREE_CHAIN (param
))
1960 if (gimple_default_def (cfun
, param
) != NULL
)
1962 tree def
= gimple_default_def (cfun
, param
);
1963 SSA_VAL (def
) = def
;
1967 for (i
= num_ssa_names
- 1; i
> 0; i
--)
1969 tree name
= ssa_name (i
);
1971 && VN_INFO (name
)->visited
== false
1972 && !has_zero_uses (name
))
1976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1978 fprintf (dump_file
, "Value numbers:\n");
1979 for (i
= 0; i
< num_ssa_names
; i
++)
1981 tree name
= ssa_name (i
);
1982 if (name
&& VN_INFO (name
)->visited
1983 && (SSA_VAL (name
) != name
1984 || is_gimple_min_invariant (VN_INFO (name
)->expr
)))
1986 print_generic_expr (dump_file
, name
, 0);
1987 fprintf (dump_file
, " = ");
1988 if (is_gimple_min_invariant (VN_INFO (name
)->expr
))
1989 print_generic_expr (dump_file
, VN_INFO (name
)->expr
, 0);
1991 print_generic_expr (dump_file
, SSA_VAL (name
), 0);
1992 fprintf (dump_file
, "\n");