]>
Commit | Line | Data |
---|---|---|
4a5e9d00 AH |
1 | /* Support routines for value ranges with equivalences. |
2 | Copyright (C) 2020 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 3, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING3. If not see | |
18 | <http://www.gnu.org/licenses/>. */ | |
19 | ||
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "backend.h" | |
24 | #include "tree.h" | |
25 | #include "gimple.h" | |
26 | #include "ssa.h" | |
27 | #include "tree-pretty-print.h" | |
28 | #include "value-range-equiv.h" | |
29 | ||
30 | value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv, | |
31 | value_range_kind kind) | |
32 | { | |
33 | m_equiv = NULL; | |
34 | set (min, max, equiv, kind); | |
35 | } | |
36 | ||
37 | value_range_equiv::value_range_equiv (const value_range &other) | |
38 | { | |
39 | m_equiv = NULL; | |
40 | set (other.min(), other.max (), NULL, other.kind ()); | |
41 | } | |
42 | ||
43 | void | |
44 | value_range_equiv::set (tree min, tree max, bitmap equiv, | |
45 | value_range_kind kind) | |
46 | { | |
47 | value_range::set (min, max, kind); | |
48 | set_equiv (equiv); | |
49 | if (flag_checking) | |
50 | check (); | |
51 | } | |
52 | ||
53 | void | |
54 | value_range_equiv::set (tree val) | |
55 | { | |
56 | gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val)); | |
57 | if (TREE_OVERFLOW_P (val)) | |
58 | val = drop_tree_overflow (val); | |
59 | set (val, val); | |
60 | } | |
61 | ||
62 | void | |
63 | value_range_equiv::set_undefined () | |
64 | { | |
65 | set (NULL, NULL, NULL, VR_UNDEFINED); | |
66 | } | |
67 | ||
68 | void | |
69 | value_range_equiv::set_varying (tree type) | |
70 | { | |
71 | value_range::set_varying (type); | |
72 | equiv_clear (); | |
73 | } | |
74 | ||
75 | /* Like set, but keep the equivalences in place. */ | |
76 | ||
77 | void | |
78 | value_range_equiv::update (tree min, tree max, value_range_kind kind) | |
79 | { | |
80 | set (min, max, | |
81 | (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL, kind); | |
82 | } | |
83 | ||
84 | /* Copy value_range in FROM into THIS while avoiding bitmap sharing. | |
85 | ||
86 | Note: The code that avoids the bitmap sharing looks at the existing | |
87 | this->m_equiv, so this function cannot be used to initalize an | |
88 | object. Use the constructors for initialization. */ | |
89 | ||
90 | void | |
91 | value_range_equiv::deep_copy (const value_range_equiv *from) | |
92 | { | |
93 | set (from->min (), from->max (), from->m_equiv, from->m_kind); | |
94 | } | |
95 | ||
96 | void | |
97 | value_range_equiv::move (value_range_equiv *from) | |
98 | { | |
99 | set (from->min (), from->max (), NULL, from->m_kind); | |
100 | m_equiv = from->m_equiv; | |
101 | from->m_equiv = NULL; | |
102 | } | |
103 | ||
104 | void | |
105 | value_range_equiv::set_equiv (bitmap equiv) | |
106 | { | |
107 | if (undefined_p () || varying_p ()) | |
108 | equiv = NULL; | |
109 | /* Since updating the equivalence set involves deep copying the | |
110 | bitmaps, only do it if absolutely necessary. | |
111 | ||
112 | All equivalence bitmaps are allocated from the same obstack. So | |
113 | we can use the obstack associated with EQUIV to allocate vr->equiv. */ | |
114 | if (m_equiv == NULL | |
115 | && equiv != NULL) | |
116 | m_equiv = BITMAP_ALLOC (equiv->obstack); | |
117 | ||
118 | if (equiv != m_equiv) | |
119 | { | |
120 | if (equiv && !bitmap_empty_p (equiv)) | |
121 | bitmap_copy (m_equiv, equiv); | |
122 | else | |
123 | bitmap_clear (m_equiv); | |
124 | } | |
125 | } | |
126 | ||
127 | void | |
128 | value_range_equiv::check () | |
129 | { | |
130 | value_range::check (); | |
131 | switch (m_kind) | |
132 | { | |
133 | case VR_UNDEFINED: | |
134 | case VR_VARYING: | |
135 | gcc_assert (!m_equiv || bitmap_empty_p (m_equiv)); | |
136 | default:; | |
137 | } | |
138 | } | |
139 | ||
140 | /* Return true if the bitmaps B1 and B2 are equal. */ | |
141 | ||
142 | static bool | |
143 | vr_bitmap_equal_p (const_bitmap b1, const_bitmap b2) | |
144 | { | |
145 | return (b1 == b2 | |
146 | || ((!b1 || bitmap_empty_p (b1)) | |
147 | && (!b2 || bitmap_empty_p (b2))) | |
148 | || (b1 && b2 | |
149 | && bitmap_equal_p (b1, b2))); | |
150 | } | |
151 | ||
152 | /* Returns TRUE if THIS == OTHER. Ignores the equivalence bitmap if | |
153 | IGNORE_EQUIVS is TRUE. */ | |
154 | ||
155 | bool | |
156 | value_range_equiv::equal_p (const value_range_equiv &other, | |
157 | bool ignore_equivs) const | |
158 | { | |
159 | return (value_range::equal_p (other) | |
160 | && (ignore_equivs || vr_bitmap_equal_p (m_equiv, other.m_equiv))); | |
161 | } | |
162 | ||
163 | void | |
164 | value_range_equiv::equiv_clear () | |
165 | { | |
166 | if (m_equiv) | |
167 | bitmap_clear (m_equiv); | |
168 | } | |
169 | ||
170 | /* Add VAR and VAR's equivalence set (VAR_VR) to the equivalence | |
171 | bitmap. If no equivalence table has been created, OBSTACK is the | |
172 | obstack to use (NULL for the default obstack). | |
173 | ||
174 | This is the central point where equivalence processing can be | |
175 | turned on/off. */ | |
176 | ||
177 | void | |
178 | value_range_equiv::equiv_add (const_tree var, | |
179 | const value_range_equiv *var_vr, | |
180 | bitmap_obstack *obstack) | |
181 | { | |
182 | if (!m_equiv) | |
183 | m_equiv = BITMAP_ALLOC (obstack); | |
184 | unsigned ver = SSA_NAME_VERSION (var); | |
185 | bitmap_set_bit (m_equiv, ver); | |
186 | if (var_vr && var_vr->m_equiv) | |
187 | bitmap_ior_into (m_equiv, var_vr->m_equiv); | |
188 | } | |
189 | ||
190 | void | |
191 | value_range_equiv::intersect (const value_range_equiv *other) | |
192 | { | |
193 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
194 | { | |
195 | fprintf (dump_file, "Intersecting\n "); | |
196 | dump_value_range (dump_file, this); | |
197 | fprintf (dump_file, "\nand\n "); | |
198 | dump_value_range (dump_file, other); | |
199 | fprintf (dump_file, "\n"); | |
200 | } | |
201 | ||
202 | /* If THIS is varying we want to pick up equivalences from OTHER. | |
203 | Just special-case this here rather than trying to fixup after the | |
204 | fact. */ | |
205 | if (this->varying_p ()) | |
206 | this->deep_copy (other); | |
207 | else | |
208 | { | |
209 | value_range tem = intersect_helper (this, other); | |
210 | this->update (tem.min (), tem.max (), tem.kind ()); | |
211 | ||
212 | /* If the result is VR_UNDEFINED there is no need to mess with | |
213 | equivalencies. */ | |
214 | if (!undefined_p ()) | |
215 | { | |
216 | /* The resulting set of equivalences for range intersection | |
217 | is the union of the two sets. */ | |
218 | if (m_equiv && other->m_equiv && m_equiv != other->m_equiv) | |
219 | bitmap_ior_into (m_equiv, other->m_equiv); | |
220 | else if (other->m_equiv && !m_equiv) | |
221 | { | |
222 | /* All equivalence bitmaps are allocated from the same | |
223 | obstack. So we can use the obstack associated with | |
224 | VR to allocate this->m_equiv. */ | |
225 | m_equiv = BITMAP_ALLOC (other->m_equiv->obstack); | |
226 | bitmap_copy (m_equiv, other->m_equiv); | |
227 | } | |
228 | } | |
229 | } | |
230 | ||
231 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
232 | { | |
233 | fprintf (dump_file, "to\n "); | |
234 | dump_value_range (dump_file, this); | |
235 | fprintf (dump_file, "\n"); | |
236 | } | |
237 | } | |
238 | ||
239 | void | |
240 | value_range_equiv::union_ (const value_range_equiv *other) | |
241 | { | |
242 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
243 | { | |
244 | fprintf (dump_file, "Meeting\n "); | |
245 | dump_value_range (dump_file, this); | |
246 | fprintf (dump_file, "\nand\n "); | |
247 | dump_value_range (dump_file, other); | |
248 | fprintf (dump_file, "\n"); | |
249 | } | |
250 | ||
251 | /* If THIS is undefined we want to pick up equivalences from OTHER. | |
252 | Just special-case this here rather than trying to fixup after the fact. */ | |
253 | if (this->undefined_p ()) | |
254 | this->deep_copy (other); | |
255 | else | |
256 | { | |
257 | value_range tem = union_helper (this, other); | |
258 | this->update (tem.min (), tem.max (), tem.kind ()); | |
259 | ||
260 | /* The resulting set of equivalences is always the intersection of | |
261 | the two sets. */ | |
262 | if (this->m_equiv && other->m_equiv && this->m_equiv != other->m_equiv) | |
263 | bitmap_and_into (this->m_equiv, other->m_equiv); | |
264 | else if (this->m_equiv && !other->m_equiv) | |
265 | bitmap_clear (this->m_equiv); | |
266 | } | |
267 | ||
268 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
269 | { | |
270 | fprintf (dump_file, "to\n "); | |
271 | dump_value_range (dump_file, this); | |
272 | fprintf (dump_file, "\n"); | |
273 | } | |
274 | } | |
275 | ||
276 | void | |
277 | value_range_equiv::dump (FILE *file) const | |
278 | { | |
279 | value_range::dump (file); | |
280 | if ((m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE) | |
281 | && m_equiv) | |
282 | { | |
283 | bitmap_iterator bi; | |
284 | unsigned i, c = 0; | |
285 | ||
286 | fprintf (file, " EQUIVALENCES: { "); | |
287 | EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi) | |
288 | { | |
289 | print_generic_expr (file, ssa_name (i)); | |
290 | fprintf (file, " "); | |
291 | c++; | |
292 | } | |
293 | fprintf (file, "} (%u elements)", c); | |
294 | } | |
295 | } | |
296 | ||
297 | void | |
298 | value_range_equiv::dump () const | |
299 | { | |
300 | dump (stderr); | |
301 | } | |
302 | ||
303 | void | |
304 | dump_value_range (FILE *file, const value_range_equiv *vr) | |
305 | { | |
306 | if (!vr) | |
307 | fprintf (file, "[]"); | |
308 | else | |
309 | vr->dump (file); | |
310 | } | |
311 | ||
312 | DEBUG_FUNCTION void | |
313 | debug (const value_range_equiv *vr) | |
314 | { | |
315 | dump_value_range (stderr, vr); | |
316 | } | |
317 | ||
318 | DEBUG_FUNCTION void | |
319 | debug (const value_range_equiv &vr) | |
320 | { | |
321 | dump_value_range (stderr, &vr); | |
322 | } |