|
0
|
1 /* Tree SCC value numbering
|
|
|
2 Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
|
|
|
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify
|
|
|
8 under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 3 of the License, or
|
|
|
10 (at your option) any later version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful,
|
|
|
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
15 GNU General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #ifndef TREE_SSA_SCCVN_H
|
|
|
22 #define TREE_SSA_SCCVN_H
|
|
|
23
|
|
|
24 /* TOP of the VN lattice. */
|
|
|
25 extern tree VN_TOP;
|
|
|
26
|
|
|
27 /* N-ary operations in the hashtable consist of length operands, an
|
|
|
28 opcode, and a type. Result is the value number of the operation,
|
|
|
29 and hashcode is stored to avoid having to calculate it
|
|
|
30 repeatedly. */
|
|
|
31
|
|
|
32 typedef struct vn_nary_op_s
|
|
|
33 {
|
|
|
34 /* Unique identify that all expressions with the same value have. */
|
|
|
35 unsigned int value_id;
|
|
|
36 ENUM_BITFIELD(tree_code) opcode : 16;
|
|
|
37 unsigned length : 16;
|
|
|
38 hashval_t hashcode;
|
|
|
39 tree result;
|
|
|
40 tree type;
|
|
|
41 tree op[4];
|
|
|
42 } *vn_nary_op_t;
|
|
|
43 typedef const struct vn_nary_op_s *const_vn_nary_op_t;
|
|
|
44
|
|
|
45 /* Phi nodes in the hashtable consist of their non-VN_TOP phi
|
|
|
46 arguments, and the basic block the phi is in. Result is the value
|
|
|
47 number of the operation, and hashcode is stored to avoid having to
|
|
|
48 calculate it repeatedly. Phi nodes not in the same block are never
|
|
|
49 considered equivalent. */
|
|
|
50
|
|
|
51 typedef struct vn_phi_s
|
|
|
52 {
|
|
|
53 /* Unique identifier that all expressions with the same value have. */
|
|
|
54 unsigned int value_id;
|
|
|
55 hashval_t hashcode;
|
|
|
56 VEC (tree, heap) *phiargs;
|
|
|
57 basic_block block;
|
|
|
58 tree result;
|
|
|
59 } *vn_phi_t;
|
|
|
60 typedef const struct vn_phi_s *const_vn_phi_t;
|
|
|
61
|
|
|
62 /* Reference operands only exist in reference operations structures.
|
|
|
63 They consist of an opcode, type, and some number of operands. For
|
|
|
64 a given opcode, some, all, or none of the operands may be used.
|
|
|
65 The operands are there to store the information that makes up the
|
|
|
66 portion of the addressing calculation that opcode performs. */
|
|
|
67
|
|
|
68 typedef struct vn_reference_op_struct
|
|
|
69 {
|
|
|
70 enum tree_code opcode;
|
|
|
71 tree type;
|
|
|
72 tree op0;
|
|
|
73 tree op1;
|
|
|
74 tree op2;
|
|
|
75 } vn_reference_op_s;
|
|
|
76 typedef vn_reference_op_s *vn_reference_op_t;
|
|
|
77 typedef const vn_reference_op_s *const_vn_reference_op_t;
|
|
|
78
|
|
|
79 DEF_VEC_O(vn_reference_op_s);
|
|
|
80 DEF_VEC_ALLOC_O(vn_reference_op_s, heap);
|
|
|
81
|
|
|
82 /* A reference operation in the hashtable is representation as a
|
|
|
83 collection of vuses, representing the memory state at the time of
|
|
|
84 the operation, and a collection of operands that make up the
|
|
|
85 addressing calculation. If two vn_reference_t's have the same set
|
|
|
86 of operands, they access the same memory location. We also store
|
|
|
87 the resulting value number, and the hashcode. The vuses are
|
|
|
88 always stored in order sorted by ssa name version. */
|
|
|
89
|
|
|
90 typedef struct vn_reference_s
|
|
|
91 {
|
|
|
92 /* Unique identifier that all expressions with the same value have. */
|
|
|
93 unsigned int value_id;
|
|
|
94 hashval_t hashcode;
|
|
|
95 VEC (tree, gc) *vuses;
|
|
|
96 VEC (vn_reference_op_s, heap) *operands;
|
|
|
97 tree result;
|
|
|
98 } *vn_reference_t;
|
|
|
99 typedef const struct vn_reference_s *const_vn_reference_t;
|
|
|
100
|
|
|
101 typedef struct vn_constant_s
|
|
|
102 {
|
|
|
103 unsigned int value_id;
|
|
|
104 hashval_t hashcode;
|
|
|
105 tree constant;
|
|
|
106 } *vn_constant_t;
|
|
|
107
|
|
|
108 /* Hash the constant CONSTANT with distinguishing type incompatible
|
|
|
109 constants in the types_compatible_p sense. */
|
|
|
110
|
|
|
111 static inline hashval_t
|
|
|
112 vn_hash_constant_with_type (tree constant)
|
|
|
113 {
|
|
|
114 tree type = TREE_TYPE (constant);
|
|
|
115 return (iterative_hash_expr (constant, 0)
|
|
|
116 + INTEGRAL_TYPE_P (type)
|
|
|
117 + (INTEGRAL_TYPE_P (type)
|
|
|
118 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
|
|
|
119 }
|
|
|
120
|
|
|
121 /* Compare the constants C1 and C2 with distinguishing type incompatible
|
|
|
122 constants in the types_compatible_p sense. */
|
|
|
123
|
|
|
124 static inline bool
|
|
|
125 vn_constant_eq_with_type (tree c1, tree c2)
|
|
|
126 {
|
|
|
127 return (expressions_equal_p (c1, c2)
|
|
|
128 && types_compatible_p (TREE_TYPE (c1), TREE_TYPE (c2)));
|
|
|
129 }
|
|
|
130
|
|
|
131 typedef struct vn_ssa_aux
|
|
|
132 {
|
|
|
133 /* Value number. This may be an SSA name or a constant. */
|
|
|
134 tree valnum;
|
|
|
135 /* Representative expression, if not a direct constant. */
|
|
|
136 tree expr;
|
|
|
137
|
|
|
138 /* Unique identifier that all expressions with the same value have. */
|
|
|
139 unsigned int value_id;
|
|
|
140
|
|
|
141 /* SCC information. */
|
|
|
142 unsigned int dfsnum;
|
|
|
143 unsigned int low;
|
|
|
144 unsigned visited : 1;
|
|
|
145 unsigned on_sccstack : 1;
|
|
|
146
|
|
|
147 /* Whether the representative expression contains constants. */
|
|
|
148 unsigned has_constants : 1;
|
|
|
149 /* Whether the SSA_NAME has been value numbered already. This is
|
|
|
150 only saying whether visit_use has been called on it at least
|
|
|
151 once. It cannot be used to avoid visitation for SSA_NAME's
|
|
|
152 involved in non-singleton SCC's. */
|
|
|
153 unsigned use_processed : 1;
|
|
|
154
|
|
|
155 /* Whether the SSA_NAME has no defining statement and thus an
|
|
|
156 insertion of such with EXPR as definition is required before
|
|
|
157 a use can be created of it. */
|
|
|
158 unsigned needs_insertion : 1;
|
|
|
159 } *vn_ssa_aux_t;
|
|
|
160
|
|
|
161 /* Return the value numbering info for an SSA_NAME. */
|
|
|
162 extern vn_ssa_aux_t VN_INFO (tree);
|
|
|
163 extern vn_ssa_aux_t VN_INFO_GET (tree);
|
|
|
164 tree vn_get_expr_for (tree);
|
|
|
165 bool run_scc_vn (bool);
|
|
|
166 void free_scc_vn (void);
|
|
|
167 tree vn_nary_op_lookup (tree, vn_nary_op_t *);
|
|
|
168 tree vn_nary_op_lookup_stmt (gimple, vn_nary_op_t *);
|
|
|
169 tree vn_nary_op_lookup_pieces (unsigned int, enum tree_code,
|
|
|
170 tree, tree, tree, tree, tree,
|
|
|
171 vn_nary_op_t *);
|
|
|
172 vn_nary_op_t vn_nary_op_insert (tree, tree);
|
|
|
173 vn_nary_op_t vn_nary_op_insert_stmt (gimple, tree);
|
|
|
174 vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code,
|
|
|
175 tree, tree, tree, tree,
|
|
|
176 tree, tree, unsigned int);
|
|
|
177 void copy_reference_ops_from_ref (tree, VEC(vn_reference_op_s, heap) **);
|
|
|
178 void copy_reference_ops_from_call (gimple, VEC(vn_reference_op_s, heap) **);
|
|
|
179 tree vn_reference_lookup_pieces (VEC (tree, gc) *,
|
|
|
180 VEC (vn_reference_op_s, heap) *,
|
|
|
181 vn_reference_t *, bool);
|
|
|
182 tree vn_reference_lookup (tree, VEC (tree, gc) *, bool, vn_reference_t *);
|
|
|
183 vn_reference_t vn_reference_insert (tree, tree, VEC (tree, gc) *);
|
|
|
184 vn_reference_t vn_reference_insert_pieces (VEC (tree, gc) *,
|
|
|
185 VEC (vn_reference_op_s, heap) *,
|
|
|
186 tree, unsigned int);
|
|
|
187
|
|
|
188 hashval_t vn_nary_op_compute_hash (const vn_nary_op_t);
|
|
|
189 int vn_nary_op_eq (const void *, const void *);
|
|
|
190 bool vn_nary_may_trap (vn_nary_op_t);
|
|
|
191 hashval_t vn_reference_compute_hash (const vn_reference_t);
|
|
|
192 int vn_reference_eq (const void *, const void *);
|
|
|
193 unsigned int get_max_value_id (void);
|
|
|
194 unsigned int get_next_value_id (void);
|
|
|
195 unsigned int get_constant_value_id (tree);
|
|
|
196 unsigned int get_or_alloc_constant_value_id (tree);
|
|
|
197 bool value_id_constant_p (unsigned int);
|
|
|
198 VEC (tree, gc) *shared_vuses_from_stmt (gimple);
|
|
|
199 #endif /* TREE_SSA_SCCVN_H */
|
