Branch data Line data Source code
1 : : /* Support routines for vrange storage.
2 : : Copyright (C) 2022-2024 Free Software Foundation, Inc.
3 : : Contributed by Aldy Hernandez <aldyh@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify
8 : : it under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : 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 : : #include "config.h"
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "backend.h"
25 : : #include "tree.h"
26 : : #include "gimple.h"
27 : : #include "ssa.h"
28 : : #include "tree-pretty-print.h"
29 : : #include "fold-const.h"
30 : : #include "gimple-range.h"
31 : : #include "value-range-storage.h"
32 : :
33 : : // Generic memory allocator to share one interface between GC and
34 : : // obstack allocators.
35 : :
36 : : class vrange_internal_alloc
37 : : {
38 : : public:
39 : 120752658 : vrange_internal_alloc () { }
40 : 120752658 : virtual ~vrange_internal_alloc () { }
41 : : virtual void *alloc (size_t size) = 0;
42 : : virtual void free (void *) = 0;
43 : : private:
44 : : DISABLE_COPY_AND_ASSIGN (vrange_internal_alloc);
45 : : };
46 : :
47 : : class vrange_obstack_alloc final: public vrange_internal_alloc
48 : : {
49 : : public:
50 : 120471745 : vrange_obstack_alloc ()
51 : 120471745 : {
52 : 120471745 : obstack_init (&m_obstack);
53 : 120471745 : }
54 : 120471745 : virtual ~vrange_obstack_alloc () final override
55 : 120471745 : {
56 : 120471745 : obstack_free (&m_obstack, NULL);
57 : 120471745 : }
58 : 315516398 : virtual void *alloc (size_t size) final override
59 : : {
60 : 315516398 : return obstack_alloc (&m_obstack, size);
61 : : }
62 : 0 : virtual void free (void *) final override { }
63 : : private:
64 : : obstack m_obstack;
65 : : };
66 : :
67 : : class vrange_ggc_alloc final: public vrange_internal_alloc
68 : : {
69 : : public:
70 : 280913 : vrange_ggc_alloc () { }
71 : 280913 : virtual ~vrange_ggc_alloc () final override { }
72 : 14872453 : virtual void *alloc (size_t size) final override
73 : : {
74 : 14872453 : return ggc_internal_alloc (size);
75 : : }
76 : 0 : virtual void free (void *p) final override
77 : : {
78 : 0 : return ggc_free (p);
79 : : }
80 : : };
81 : :
82 : 120752658 : vrange_allocator::vrange_allocator (bool gc)
83 : : {
84 : 120752658 : if (gc)
85 : 280913 : m_alloc = new vrange_ggc_alloc;
86 : : else
87 : 120471745 : m_alloc = new vrange_obstack_alloc;
88 : 120752658 : }
89 : :
90 : 120752658 : vrange_allocator::~vrange_allocator ()
91 : : {
92 : 120752658 : delete m_alloc;
93 : 120752658 : }
94 : :
95 : : void *
96 : 42671463 : vrange_allocator::alloc (size_t size)
97 : : {
98 : 42671463 : return m_alloc->alloc (size);
99 : : }
100 : :
101 : : void
102 : 0 : vrange_allocator::free (void *p)
103 : : {
104 : 0 : m_alloc->free (p);
105 : 0 : }
106 : :
107 : : // Allocate a new vrange_storage object initialized to R and return
108 : : // it.
109 : :
110 : : vrange_storage *
111 : 245045925 : vrange_allocator::clone (const vrange &r)
112 : : {
113 : 245045925 : return vrange_storage::alloc (*m_alloc, r);
114 : : }
115 : :
116 : : vrange_storage *
117 : 21336702 : vrange_allocator::clone_varying (tree type)
118 : : {
119 : 21336702 : if (irange::supports_p (type))
120 : 20979871 : return irange_storage::alloc (*m_alloc, int_range <1> (type));
121 : 356831 : if (frange::supports_p (type))
122 : 356831 : return frange_storage::alloc (*m_alloc, frange (type));
123 : : return NULL;
124 : : }
125 : :
126 : : vrange_storage *
127 : 21334761 : vrange_allocator::clone_undefined (tree type)
128 : : {
129 : 21334761 : if (irange::supports_p (type))
130 : 20977930 : return irange_storage::alloc (*m_alloc, int_range<1> ());
131 : 356831 : if (frange::supports_p (type))
132 : 356831 : return frange_storage::alloc (*m_alloc, frange ());
133 : : return NULL;
134 : : }
135 : :
136 : : // Allocate a new vrange_storage object initialized to R and return
137 : : // it. Return NULL if R is unsupported.
138 : :
139 : : vrange_storage *
140 : 245045925 : vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r)
141 : : {
142 : 245045925 : if (is_a <irange> (r))
143 : 234504067 : return irange_storage::alloc (allocator, as_a <irange> (r));
144 : 10541858 : if (is_a <frange> (r))
145 : 10541858 : return frange_storage::alloc (allocator, as_a <frange> (r));
146 : : return NULL;
147 : : }
148 : :
149 : : // Set storage to R.
150 : :
151 : : void
152 : 17671488 : vrange_storage::set_vrange (const vrange &r)
153 : : {
154 : 17671488 : if (is_a <irange> (r))
155 : : {
156 : 17254562 : irange_storage *s = static_cast <irange_storage *> (this);
157 : 17254562 : gcc_checking_assert (s->fits_p (as_a <irange> (r)));
158 : 17254562 : s->set_irange (as_a <irange> (r));
159 : : }
160 : 416926 : else if (is_a <frange> (r))
161 : : {
162 : 416926 : frange_storage *s = static_cast <frange_storage *> (this);
163 : 416926 : gcc_checking_assert (s->fits_p (as_a <frange> (r)));
164 : 416926 : s->set_frange (as_a <frange> (r));
165 : : }
166 : : else
167 : 0 : gcc_unreachable ();
168 : 17671488 : }
169 : :
170 : : // Restore R from storage.
171 : :
172 : : void
173 : 1305481580 : vrange_storage::get_vrange (vrange &r, tree type) const
174 : : {
175 : 1305481580 : if (is_a <irange> (r))
176 : : {
177 : 1260812431 : const irange_storage *s = static_cast <const irange_storage *> (this);
178 : 1260812431 : s->get_irange (as_a <irange> (r), type);
179 : : }
180 : 44669149 : else if (is_a <frange> (r))
181 : : {
182 : 44669149 : const frange_storage *s = static_cast <const frange_storage *> (this);
183 : 44669149 : s->get_frange (as_a <frange> (r), type);
184 : : }
185 : : else
186 : 0 : gcc_unreachable ();
187 : 1305481580 : }
188 : :
189 : : // Return TRUE if storage can fit R.
190 : :
191 : : bool
192 : 20669930 : vrange_storage::fits_p (const vrange &r) const
193 : : {
194 : 20669930 : if (is_a <irange> (r))
195 : : {
196 : 20253004 : const irange_storage *s = static_cast <const irange_storage *> (this);
197 : 20253004 : return s->fits_p (as_a <irange> (r));
198 : : }
199 : 416926 : if (is_a <frange> (r))
200 : : {
201 : 416926 : const frange_storage *s = static_cast <const frange_storage *> (this);
202 : 416926 : return s->fits_p (as_a <frange> (r));
203 : : }
204 : 0 : gcc_unreachable ();
205 : : return false;
206 : : }
207 : :
208 : : // Return TRUE if the range in storage is equal to R. It is the
209 : : // caller's responsibility to verify that the type of the range in
210 : : // storage matches that of R.
211 : :
212 : : bool
213 : 7068395 : vrange_storage::equal_p (const vrange &r) const
214 : : {
215 : 7068395 : if (is_a <irange> (r))
216 : : {
217 : 7059697 : const irange_storage *s = static_cast <const irange_storage *> (this);
218 : 7059697 : return s->equal_p (as_a <irange> (r));
219 : : }
220 : 8698 : if (is_a <frange> (r))
221 : : {
222 : 8698 : const frange_storage *s = static_cast <const frange_storage *> (this);
223 : 8698 : return s->equal_p (as_a <frange> (r));
224 : : }
225 : 0 : gcc_unreachable ();
226 : : }
227 : :
228 : : //============================================================================
229 : : // irange_storage implementation
230 : : //============================================================================
231 : :
232 : : unsigned short *
233 : 1022848379 : irange_storage::write_lengths_address ()
234 : : {
235 : 1022848379 : return (unsigned short *)&m_val[(m_num_ranges * 2 + 2)
236 : 1022848379 : * WIDE_INT_MAX_HWIS (m_precision)];
237 : : }
238 : :
239 : : const unsigned short *
240 : 885193739 : irange_storage::lengths_address () const
241 : : {
242 : 885193739 : return const_cast <irange_storage *> (this)->write_lengths_address ();
243 : : }
244 : :
245 : : // Allocate a new irange_storage object initialized to R.
246 : :
247 : : irange_storage *
248 : 276461868 : irange_storage::alloc (vrange_internal_alloc &allocator, const irange &r)
249 : : {
250 : 276461868 : size_t size = irange_storage::size (r);
251 : 276461868 : irange_storage *p = static_cast <irange_storage *> (allocator.alloc (size));
252 : 276461868 : new (p) irange_storage (r);
253 : 276461868 : return p;
254 : : }
255 : :
256 : : // Initialize the storage with R.
257 : :
258 : 276461868 : irange_storage::irange_storage (const irange &r)
259 : 276461868 : : m_max_ranges (r.num_pairs ())
260 : : {
261 : 276461868 : m_num_ranges = m_max_ranges;
262 : 276461868 : set_irange (r);
263 : 276461868 : }
264 : :
265 : : static inline void
266 : 607661988 : write_wide_int (HOST_WIDE_INT *&val, unsigned short *&len, const wide_int &w)
267 : : {
268 : 607661988 : *len = w.get_len ();
269 : 1216126738 : for (unsigned i = 0; i < *len; ++i)
270 : 608464750 : *val++ = w.elt (i);
271 : 607661988 : ++len;
272 : 607661988 : }
273 : :
274 : : // Store R into the current storage.
275 : :
276 : : void
277 : 293716430 : irange_storage::set_irange (const irange &r)
278 : : {
279 : 293716430 : gcc_checking_assert (fits_p (r));
280 : :
281 : 293716430 : if (r.undefined_p ())
282 : : {
283 : 21306467 : m_kind = VR_UNDEFINED;
284 : 156061790 : return;
285 : : }
286 : 272409963 : if (r.varying_p ())
287 : : {
288 : 134755323 : m_kind = VR_VARYING;
289 : 134755323 : return;
290 : : }
291 : :
292 : 137654640 : m_precision = TYPE_PRECISION (r.type ());
293 : 137654640 : m_num_ranges = r.num_pairs ();
294 : 137654640 : m_kind = VR_RANGE;
295 : :
296 : 137654640 : HOST_WIDE_INT *val = &m_val[0];
297 : 137654640 : unsigned short *len = write_lengths_address ();
298 : :
299 : 303830994 : for (unsigned i = 0; i < r.num_pairs (); ++i)
300 : : {
301 : 166176354 : write_wide_int (val, len, r.lower_bound (i));
302 : 166178158 : write_wide_int (val, len, r.upper_bound (i));
303 : : }
304 : :
305 : : // TODO: We could avoid streaming out the value if the mask is -1.
306 : 137654640 : irange_bitmask bm = r.m_bitmask;
307 : 137654640 : write_wide_int (val, len, bm.value ());
308 : 137654640 : write_wide_int (val, len, bm.mask ());
309 : :
310 : 137654640 : if (flag_checking)
311 : : {
312 : 137654111 : int_range_max tmp;
313 : 137654111 : get_irange (tmp, r.type ());
314 : 137654111 : gcc_checking_assert (tmp == r);
315 : 137654111 : }
316 : 137654640 : }
317 : :
318 : : static inline void
319 : 3959553110 : read_wide_int (wide_int &w,
320 : : const HOST_WIDE_INT *val, unsigned short len, unsigned prec)
321 : : {
322 : 3959553110 : trailing_wide_int_storage stow (prec, &len,
323 : 973657632 : const_cast <HOST_WIDE_INT *> (val));
324 : 2985895478 : w = trailing_wide_int (stow);
325 : : }
326 : :
327 : : // Restore a range of TYPE from storage into R.
328 : :
329 : : void
330 : 1405260496 : irange_storage::get_irange (irange &r, tree type) const
331 : : {
332 : 1405260496 : if (m_kind == VR_UNDEFINED)
333 : : {
334 : 1620266 : r.set_undefined ();
335 : 521687023 : return;
336 : : }
337 : 1403640230 : if (m_kind == VR_VARYING)
338 : : {
339 : 518446491 : r.set_varying (type);
340 : 518446491 : return;
341 : : }
342 : :
343 : 885193739 : gcc_checking_assert (TYPE_PRECISION (type) == m_precision);
344 : 885193739 : const HOST_WIDE_INT *val = &m_val[0];
345 : 885193739 : const unsigned short *len = lengths_address ();
346 : :
347 : : // Handle the common case where R can fit the new range.
348 : 885193739 : if (r.m_max_ranges >= m_num_ranges)
349 : : {
350 : 868602722 : r.m_kind = VR_RANGE;
351 : 868602722 : r.m_num_ranges = m_num_ranges;
352 : 868602722 : r.m_type = type;
353 : 2880840568 : for (unsigned i = 0; i < m_num_ranges * 2; ++i)
354 : : {
355 : 2012237846 : read_wide_int (r.m_base[i], val, *len, m_precision);
356 : 2012237846 : val += *len++;
357 : : }
358 : : }
359 : : // Otherwise build the range piecewise.
360 : : else
361 : : {
362 : 16591017 : r.set_undefined ();
363 : 105054910 : for (unsigned i = 0; i < m_num_ranges; ++i)
364 : : {
365 : 88463893 : wide_int lb, ub;
366 : 88463893 : read_wide_int (lb, val, *len, m_precision);
367 : 88463893 : val += *len++;
368 : 88463893 : read_wide_int (ub, val, *len, m_precision);
369 : 88463893 : val += *len++;
370 : 88463893 : int_range<1> tmp (type, lb, ub);
371 : 88463893 : r.union_ (tmp);
372 : 88463893 : }
373 : : }
374 : :
375 : 885193739 : wide_int bits_value, bits_mask;
376 : 885193739 : read_wide_int (bits_value, val, *len, m_precision);
377 : 885193739 : val += *len++;
378 : 885193739 : read_wide_int (bits_mask, val, *len, m_precision);
379 : 885193739 : r.m_bitmask = irange_bitmask (bits_value, bits_mask);
380 : 885193739 : if (r.m_kind == VR_VARYING)
381 : 0 : r.m_kind = VR_RANGE;
382 : :
383 : 885193739 : if (flag_checking)
384 : 885190637 : r.verify_range ();
385 : 885200322 : }
386 : :
387 : : bool
388 : 7059697 : irange_storage::equal_p (const irange &r) const
389 : : {
390 : 7059697 : if (m_kind == VR_UNDEFINED || r.undefined_p ())
391 : 0 : return m_kind == r.m_kind;
392 : 7059697 : if (m_kind == VR_VARYING || r.varying_p ())
393 : 265743 : return m_kind == r.m_kind;
394 : :
395 : : // ?? We could make this faster by doing the comparison in place,
396 : : // without going through get_irange.
397 : 6793954 : int_range_max tmp;
398 : 6793954 : get_irange (tmp, r.type ());
399 : 6793954 : return tmp == r;
400 : 6793954 : }
401 : :
402 : : // Return the size in bytes to allocate storage that can hold R.
403 : :
404 : : size_t
405 : 276461868 : irange_storage::size (const irange &r)
406 : : {
407 : 276461868 : if (r.undefined_p ())
408 : : return sizeof (irange_storage);
409 : :
410 : 255247904 : unsigned prec = TYPE_PRECISION (r.type ());
411 : 255247904 : unsigned n = r.num_pairs () * 2 + 2;
412 : 255247904 : unsigned hwi_size = ((n * WIDE_INT_MAX_HWIS (prec) - 1)
413 : : * sizeof (HOST_WIDE_INT));
414 : 255247904 : unsigned len_size = n * sizeof (unsigned short);
415 : 255247904 : return sizeof (irange_storage) + hwi_size + len_size;
416 : : }
417 : :
418 : : // Return TRUE if R fits in the current storage.
419 : :
420 : : bool
421 : 331223996 : irange_storage::fits_p (const irange &r) const
422 : : {
423 : 331223996 : return m_max_ranges >= r.num_pairs ();
424 : : }
425 : :
426 : : void
427 : 0 : irange_storage::dump () const
428 : : {
429 : 0 : fprintf (stderr, "irange_storage (prec=%d, ranges=%d):\n",
430 : 0 : m_precision, m_num_ranges);
431 : :
432 : 0 : if (m_num_ranges == 0)
433 : : return;
434 : :
435 : 0 : const HOST_WIDE_INT *val = &m_val[0];
436 : 0 : const unsigned short *len = lengths_address ();
437 : 0 : int i, j;
438 : :
439 : 0 : fprintf (stderr, " lengths = [ ");
440 : 0 : for (i = 0; i < m_num_ranges * 2 + 2; ++i)
441 : 0 : fprintf (stderr, "%d ", len[i]);
442 : 0 : fprintf (stderr, "]\n");
443 : :
444 : 0 : for (i = 0; i < m_num_ranges; ++i)
445 : : {
446 : 0 : for (j = 0; j < *len; ++j)
447 : 0 : fprintf (stderr, " [PAIR %d] LB " HOST_WIDE_INT_PRINT_DEC "\n", i,
448 : 0 : *val++);
449 : 0 : ++len;
450 : 0 : for (j = 0; j < *len; ++j)
451 : 0 : fprintf (stderr, " [PAIR %d] UB " HOST_WIDE_INT_PRINT_DEC "\n", i,
452 : 0 : *val++);
453 : 0 : ++len;
454 : : }
455 : :
456 : : // Dump value/mask pair.
457 : 0 : for (j = 0; j < *len; ++j)
458 : 0 : fprintf (stderr, " [VALUE] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
459 : 0 : ++len;
460 : 0 : for (j = 0; j < *len; ++j)
461 : 0 : fprintf (stderr, " [MASK] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
462 : : }
463 : :
464 : : DEBUG_FUNCTION void
465 : 0 : debug (const irange_storage &storage)
466 : : {
467 : 0 : storage.dump ();
468 : 0 : fprintf (stderr, "\n");
469 : 0 : }
470 : :
471 : : //============================================================================
472 : : // frange_storage implementation
473 : : //============================================================================
474 : :
475 : : // Allocate a new frange_storage object initialized to R.
476 : :
477 : : frange_storage *
478 : 11255520 : frange_storage::alloc (vrange_internal_alloc &allocator, const frange &r)
479 : : {
480 : 11255520 : size_t size = sizeof (frange_storage);
481 : 11255520 : frange_storage *p = static_cast <frange_storage *> (allocator.alloc (size));
482 : 11255520 : new (p) frange_storage (r);
483 : 11255520 : return p;
484 : : }
485 : :
486 : : void
487 : 11672446 : frange_storage::set_frange (const frange &r)
488 : : {
489 : 11672446 : gcc_checking_assert (fits_p (r));
490 : :
491 : 11672446 : m_kind = r.m_kind;
492 : 11672446 : m_min = r.m_min;
493 : 11672446 : m_max = r.m_max;
494 : 11672446 : m_pos_nan = r.m_pos_nan;
495 : 11672446 : m_neg_nan = r.m_neg_nan;
496 : 11672446 : }
497 : :
498 : : void
499 : 44677847 : frange_storage::get_frange (frange &r, tree type) const
500 : : {
501 : 44677847 : gcc_checking_assert (r.supports_type_p (type));
502 : :
503 : : // Handle explicit NANs.
504 : 44677847 : if (m_kind == VR_NAN)
505 : : {
506 : 85063 : if (HONOR_NANS (type))
507 : : {
508 : 85063 : if (m_pos_nan && m_neg_nan)
509 : 80569 : r.set_nan (type);
510 : : else
511 : 4494 : r.set_nan (type, m_neg_nan);
512 : : }
513 : : else
514 : 0 : r.set_undefined ();
515 : 85063 : return;
516 : : }
517 : 44592784 : if (m_kind == VR_UNDEFINED)
518 : : {
519 : 62473 : r.set_undefined ();
520 : 62473 : return;
521 : : }
522 : :
523 : : // We use the constructor to create the new range instead of writing
524 : : // out the bits into the frange directly, because the global range
525 : : // being read may be being inlined into a function with different
526 : : // restrictions as when it was originally written. We want to make
527 : : // sure the resulting range is canonicalized correctly for the new
528 : : // consumer.
529 : 44530311 : r = frange (type, m_min, m_max, m_kind);
530 : :
531 : : // The constructor will set the NAN bits for HONOR_NANS, but we must
532 : : // make sure to set the NAN sign if known.
533 : 44530311 : if (HONOR_NANS (type) && (m_pos_nan ^ m_neg_nan) == 1)
534 : 1194843 : r.update_nan (m_neg_nan);
535 : 43335468 : else if (!m_pos_nan && !m_neg_nan)
536 : 5038580 : r.clear_nan ();
537 : : }
538 : :
539 : : bool
540 : 8698 : frange_storage::equal_p (const frange &r) const
541 : : {
542 : 8698 : if (r.undefined_p ())
543 : 0 : return m_kind == VR_UNDEFINED;
544 : :
545 : 8698 : frange tmp;
546 : 8698 : get_frange (tmp, r.type ());
547 : 8698 : return tmp == r;
548 : : }
549 : :
550 : : bool
551 : 12506298 : frange_storage::fits_p (const frange &) const
552 : : {
553 : 12506298 : return true;
554 : : }
555 : :
556 : : static vrange_allocator ggc_vrange_allocator (true);
557 : :
558 : 0 : vrange_storage *ggc_alloc_vrange_storage (tree type)
559 : : {
560 : 0 : return ggc_vrange_allocator.clone_varying (type);
561 : : }
562 : :
563 : 14872453 : vrange_storage *ggc_alloc_vrange_storage (const vrange &r)
564 : : {
565 : 14872453 : return ggc_vrange_allocator.clone (r);
566 : : }
|
