Line data Source code
1 : /* Support routines for vrange storage.
2 : Copyright (C) 2022-2026 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 "gimplify.h"
28 : #include "ssa.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 98111012 : vrange_internal_alloc () { }
40 98111000 : 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 97817595 : vrange_obstack_alloc ()
51 97817595 : {
52 97817595 : obstack_init (&m_obstack);
53 97817595 : }
54 97817583 : virtual ~vrange_obstack_alloc () final override
55 97817583 : {
56 97817583 : obstack_free (&m_obstack, NULL);
57 97817583 : }
58 408104517 : virtual void *alloc (size_t size) final override
59 : {
60 408104517 : 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 293417 : vrange_ggc_alloc () { }
71 293417 : virtual ~vrange_ggc_alloc () final override { }
72 20789801 : virtual void *alloc (size_t size) final override
73 : {
74 20789801 : 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 98111012 : vrange_allocator::vrange_allocator (bool gc)
83 : {
84 98111012 : if (gc)
85 293417 : m_alloc = new vrange_ggc_alloc;
86 : else
87 97817595 : m_alloc = new vrange_obstack_alloc;
88 98111012 : }
89 :
90 98111000 : vrange_allocator::~vrange_allocator ()
91 : {
92 98111000 : delete m_alloc;
93 98111000 : }
94 :
95 : void *
96 58037345 : vrange_allocator::alloc (size_t size)
97 : {
98 58037345 : 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 312829295 : vrange_allocator::clone (const vrange &r, bool shared_p)
112 : {
113 312829295 : return vrange_storage::alloc (*m_alloc, r, shared_p);
114 : }
115 :
116 : vrange_storage *
117 29066446 : vrange_allocator::clone_varying (tree type)
118 : {
119 29066446 : if (irange::supports_p (type))
120 18586923 : return irange_storage::alloc (*m_alloc, int_range <1> (type));
121 10479523 : if (prange::supports_p (type))
122 10000732 : return prange_storage::alloc (*m_alloc, prange (type));
123 478791 : if (frange::supports_p (type))
124 478791 : return frange_storage::alloc (*m_alloc, frange (type));
125 : return NULL;
126 : }
127 :
128 : vrange_storage *
129 28961232 : vrange_allocator::clone_undefined (tree type)
130 : {
131 28961232 : if (irange::supports_p (type))
132 18487398 : return irange_storage::alloc (*m_alloc, int_range<1> ());
133 10473834 : if (prange::supports_p (type))
134 9999215 : return prange_storage::alloc (*m_alloc, prange ());
135 474619 : if (frange::supports_p (type))
136 474619 : return frange_storage::alloc (*m_alloc, frange ());
137 : return NULL;
138 : }
139 :
140 : // Allocate a new vrange_storage object initialized to R and return
141 : // it. Return NULL if R is unsupported.
142 :
143 : vrange_storage *
144 312829295 : vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r,
145 : bool shared_p)
146 : {
147 312829295 : if (is_a <irange> (r))
148 220563621 : return irange_storage::alloc (allocator, as_a <irange> (r));
149 92265674 : if (is_a <prange> (r))
150 80401858 : return prange_storage::alloc (allocator, as_a <prange> (r), shared_p);
151 11863816 : if (is_a <frange> (r))
152 11863816 : return frange_storage::alloc (allocator, as_a <frange> (r));
153 : return NULL;
154 : }
155 :
156 : // Set storage to R.
157 :
158 : void
159 26625033 : vrange_storage::set_vrange (const vrange &r)
160 : {
161 26625033 : if (is_a <irange> (r))
162 : {
163 22538610 : irange_storage *s = static_cast <irange_storage *> (this);
164 22538610 : gcc_checking_assert (s->fits_p (as_a <irange> (r)));
165 22538610 : s->set_irange (as_a <irange> (r));
166 : }
167 4086423 : else if (is_a <prange> (r))
168 : {
169 3504557 : prange_storage *s = static_cast <prange_storage *> (this);
170 3504557 : gcc_checking_assert (s->fits_p (as_a <prange> (r)));
171 3504557 : s->set_prange (as_a <prange> (r));
172 : }
173 581866 : else if (is_a <frange> (r))
174 : {
175 581866 : frange_storage *s = static_cast <frange_storage *> (this);
176 581866 : gcc_checking_assert (s->fits_p (as_a <frange> (r)));
177 581866 : s->set_frange (as_a <frange> (r));
178 : }
179 : else
180 0 : gcc_unreachable ();
181 :
182 : // Verify that reading back from the cache didn't drop bits.
183 26625033 : if (flag_checking
184 : // FIXME: Avoid checking frange, as it currently pessimizes some ranges:
185 : //
186 : // gfortran.dg/pr49472.f90 pessimizes [0.0, 1.0] into [-0.0, 1.0].
187 26624967 : && !is_a <frange> (r)
188 52668134 : && !r.undefined_p ())
189 : {
190 25893614 : value_range tmp (r);
191 25893614 : get_vrange (tmp, r.type ());
192 25893614 : gcc_checking_assert (tmp == r);
193 25893614 : }
194 26625033 : }
195 :
196 : // Restore R from storage.
197 :
198 : void
199 1782457672 : vrange_storage::get_vrange (vrange &r, tree type) const
200 : {
201 1782457672 : if (is_a <irange> (r))
202 : {
203 1373336498 : const irange_storage *s = static_cast <const irange_storage *> (this);
204 1373336498 : s->get_irange (as_a <irange> (r), type);
205 : }
206 409121174 : else if (is_a <prange> (r))
207 : {
208 363735011 : const prange_storage *s = static_cast <const prange_storage *> (this);
209 363735011 : s->get_prange (as_a <prange> (r), type);
210 : }
211 45386163 : else if (is_a <frange> (r))
212 : {
213 45386163 : const frange_storage *s = static_cast <const frange_storage *> (this);
214 45386163 : s->get_frange (as_a <frange> (r), type);
215 : }
216 : else
217 0 : gcc_unreachable ();
218 1782457672 : }
219 :
220 : // Return TRUE if storage can fit R.
221 :
222 : bool
223 30859052 : vrange_storage::fits_p (const vrange &r) const
224 : {
225 30859052 : if (is_a <irange> (r))
226 : {
227 26700416 : const irange_storage *s = static_cast <const irange_storage *> (this);
228 26700416 : return s->fits_p (as_a <irange> (r));
229 : }
230 4158636 : if (is_a <prange> (r))
231 : {
232 3528378 : const prange_storage *s = static_cast <const prange_storage *> (this);
233 3528378 : return s->fits_p (as_a <prange> (r));
234 : }
235 630258 : if (is_a <frange> (r))
236 : {
237 630258 : const frange_storage *s = static_cast <const frange_storage *> (this);
238 630258 : return s->fits_p (as_a <frange> (r));
239 : }
240 0 : gcc_unreachable ();
241 : return false;
242 : }
243 :
244 : // Return TRUE if the range in storage is equal to R. It is the
245 : // caller's responsibility to verify that the type of the range in
246 : // storage matches that of R.
247 :
248 : bool
249 18663185 : vrange_storage::equal_p (const vrange &r) const
250 : {
251 18663185 : if (is_a <irange> (r))
252 : {
253 3799820 : const irange_storage *s = static_cast <const irange_storage *> (this);
254 3799820 : return s->equal_p (as_a <irange> (r));
255 : }
256 14863365 : if (is_a <prange> (r))
257 : {
258 14843018 : const prange_storage *s = static_cast <const prange_storage *> (this);
259 14843018 : return s->equal_p (as_a <prange> (r));
260 : }
261 20347 : if (is_a <frange> (r))
262 : {
263 20347 : const frange_storage *s = static_cast <const frange_storage *> (this);
264 20347 : return s->equal_p (as_a <frange> (r));
265 : }
266 0 : gcc_unreachable ();
267 : }
268 :
269 : //============================================================================
270 : // irange_storage implementation
271 : //============================================================================
272 :
273 : unsigned short *
274 1106469597 : irange_storage::write_lengths_address ()
275 : {
276 1106469597 : return (unsigned short *)&m_val[(m_num_ranges * 2 + 2)
277 1106469597 : * WIDE_INT_MAX_HWIS (m_precision)];
278 : }
279 :
280 : const unsigned short *
281 960741680 : irange_storage::lengths_address () const
282 : {
283 960741680 : return const_cast <irange_storage *> (this)->write_lengths_address ();
284 : }
285 :
286 : // Allocate a new irange_storage object initialized to R.
287 :
288 : irange_storage *
289 257637942 : irange_storage::alloc (vrange_internal_alloc &allocator, const irange &r)
290 : {
291 257637942 : size_t size = irange_storage::size (r);
292 257637942 : irange_storage *p = static_cast <irange_storage *> (allocator.alloc (size));
293 257637942 : new (p) irange_storage (r);
294 257637942 : return p;
295 : }
296 :
297 : // Initialize the storage with R.
298 :
299 257637942 : irange_storage::irange_storage (const irange &r)
300 257637942 : : vrange_storage (VR_IRANGE), m_max_ranges (r.num_pairs ())
301 : {
302 257637942 : m_num_ranges = m_max_ranges;
303 257637942 : set_irange (r);
304 257637942 : }
305 :
306 : static inline void
307 696193216 : write_wide_int (HOST_WIDE_INT *&val, unsigned short *&len, const wide_int &w)
308 : {
309 696193216 : *len = w.get_len ();
310 1393660922 : for (unsigned i = 0; i < *len; ++i)
311 697467706 : *val++ = w.elt (i);
312 696193216 : ++len;
313 696193216 : }
314 :
315 : // Store R into the current storage.
316 :
317 : void
318 280176552 : irange_storage::set_irange (const irange &r)
319 : {
320 280176552 : gcc_checking_assert (fits_p (r));
321 :
322 280176552 : if (r.undefined_p ())
323 : {
324 18913987 : m_kind = VR_UNDEFINED;
325 134448635 : return;
326 : }
327 261262565 : if (r.varying_p ())
328 : {
329 115534648 : m_kind = VR_VARYING;
330 115534648 : return;
331 : }
332 :
333 145727917 : m_precision = TYPE_PRECISION (r.type ());
334 145727917 : m_num_ranges = r.num_pairs ();
335 145727917 : m_kind = VR_RANGE;
336 :
337 145727917 : HOST_WIDE_INT *val = &m_val[0];
338 145727917 : unsigned short *len = write_lengths_address ();
339 :
340 348096608 : for (unsigned i = 0; i < r.num_pairs (); ++i)
341 : {
342 202368691 : write_wide_int (val, len, r.lower_bound (i));
343 202371470 : write_wide_int (val, len, r.upper_bound (i));
344 : }
345 :
346 : // TODO: We could avoid streaming out the value if the mask is -1.
347 145727917 : irange_bitmask bm = r.m_bitmask;
348 145727917 : write_wide_int (val, len, bm.value ());
349 145727917 : write_wide_int (val, len, bm.mask ());
350 145727917 : }
351 :
352 : static inline void
353 4657385270 : read_wide_int (wide_int &w,
354 : const HOST_WIDE_INT *val, unsigned short len, unsigned prec)
355 : {
356 4657385270 : trailing_wide_int_storage stow (prec, &len,
357 1150723720 : const_cast <HOST_WIDE_INT *> (val));
358 3506661550 : w = trailing_wide_int (stow);
359 : }
360 :
361 : // Restore a range of TYPE from storage into R.
362 :
363 : void
364 1376679258 : irange_storage::get_irange (irange &r, tree type) const
365 : {
366 1376679258 : if (m_kind == VR_UNDEFINED)
367 : {
368 9892457 : r.set_undefined ();
369 425830035 : return;
370 : }
371 1366786801 : if (m_kind == VR_VARYING)
372 : {
373 406045121 : r.set_varying (type);
374 406045121 : return;
375 : }
376 :
377 960741680 : gcc_checking_assert (TYPE_PRECISION (type) == m_precision);
378 960741680 : const HOST_WIDE_INT *val = &m_val[0];
379 960741680 : const unsigned short *len = lengths_address ();
380 :
381 : // Handle the common case where R can fit the new range.
382 960741680 : if (r.m_max_ranges >= m_num_ranges)
383 : {
384 927979504 : r.m_kind = VR_RANGE;
385 927979504 : r.m_num_ranges = m_num_ranges;
386 927979504 : r.m_type = type;
387 3283917334 : for (unsigned i = 0; i < m_num_ranges * 2; ++i)
388 : {
389 2355937830 : read_wide_int (r.m_base[i], val, *len, m_precision);
390 2355937830 : val += *len++;
391 : }
392 : }
393 : // Otherwise build the range piecewise.
394 : else
395 : {
396 32762176 : r.set_undefined ();
397 255506392 : for (unsigned i = 0; i < m_num_ranges; ++i)
398 : {
399 189982040 : wide_int lb, ub;
400 189982040 : read_wide_int (lb, val, *len, m_precision);
401 189982040 : val += *len++;
402 189982040 : read_wide_int (ub, val, *len, m_precision);
403 189982040 : val += *len++;
404 189982040 : int_range<1> tmp (type, lb, ub);
405 189982040 : r.union_ (tmp);
406 190572732 : }
407 : }
408 :
409 960741680 : wide_int bits_value, bits_mask;
410 960741680 : read_wide_int (bits_value, val, *len, m_precision);
411 960741680 : val += *len++;
412 960741680 : read_wide_int (bits_mask, val, *len, m_precision);
413 960741680 : r.m_bitmask = irange_bitmask (bits_value, bits_mask);
414 960741680 : if (r.m_kind == VR_VARYING)
415 0 : r.m_kind = VR_RANGE;
416 :
417 960741680 : if (flag_checking)
418 960738278 : r.verify_range ();
419 960814703 : }
420 :
421 : bool
422 3799820 : irange_storage::equal_p (const irange &r) const
423 : {
424 3799820 : if (m_kind == VR_UNDEFINED || r.undefined_p ())
425 0 : return m_kind == r.m_kind;
426 3799820 : if (m_kind == VR_VARYING || r.varying_p ())
427 457060 : return m_kind == r.m_kind;
428 :
429 : // ?? We could make this faster by doing the comparison in place,
430 : // without going through get_irange.
431 3342760 : int_range_max tmp;
432 3342760 : get_irange (tmp, r.type ());
433 3342760 : return tmp == r;
434 3342760 : }
435 :
436 : // Return the size in bytes to allocate storage that can hold R.
437 :
438 : size_t
439 257637942 : irange_storage::size (const irange &r)
440 : {
441 257637942 : if (r.undefined_p ())
442 : return sizeof (irange_storage);
443 :
444 238865260 : unsigned prec = TYPE_PRECISION (r.type ());
445 238865260 : unsigned n = r.num_pairs () * 2 + 2;
446 238865260 : unsigned hwi_size = ((n * WIDE_INT_MAX_HWIS (prec) - 1)
447 : * sizeof (HOST_WIDE_INT));
448 238865260 : unsigned len_size = n * sizeof (unsigned short);
449 238865260 : return sizeof (irange_storage) + hwi_size + len_size;
450 : }
451 :
452 : // Return TRUE if R fits in the current storage.
453 :
454 : bool
455 329415578 : irange_storage::fits_p (const irange &r) const
456 : {
457 329415578 : return m_max_ranges >= r.num_pairs ();
458 : }
459 :
460 : void
461 0 : irange_storage::dump () const
462 : {
463 0 : fprintf (stderr, "irange_storage (prec=%d, ranges=%d):\n",
464 0 : m_precision, m_num_ranges);
465 :
466 0 : if (m_num_ranges == 0)
467 : return;
468 :
469 0 : const HOST_WIDE_INT *val = &m_val[0];
470 0 : const unsigned short *len = lengths_address ();
471 0 : int i, j;
472 :
473 0 : fprintf (stderr, " lengths = [ ");
474 0 : for (i = 0; i < m_num_ranges * 2 + 2; ++i)
475 0 : fprintf (stderr, "%d ", len[i]);
476 0 : fprintf (stderr, "]\n");
477 :
478 0 : for (i = 0; i < m_num_ranges; ++i)
479 : {
480 0 : for (j = 0; j < *len; ++j)
481 0 : fprintf (stderr, " [PAIR %d] LB " HOST_WIDE_INT_PRINT_DEC "\n", i,
482 0 : *val++);
483 0 : ++len;
484 0 : for (j = 0; j < *len; ++j)
485 0 : fprintf (stderr, " [PAIR %d] UB " HOST_WIDE_INT_PRINT_DEC "\n", i,
486 0 : *val++);
487 0 : ++len;
488 : }
489 :
490 : // Dump value/mask pair.
491 0 : for (j = 0; j < *len; ++j)
492 0 : fprintf (stderr, " [VALUE] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
493 0 : ++len;
494 0 : for (j = 0; j < *len; ++j)
495 0 : fprintf (stderr, " [MASK] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
496 : }
497 :
498 : DEBUG_FUNCTION void
499 0 : debug (const irange_storage &storage)
500 : {
501 0 : storage.dump ();
502 0 : fprintf (stderr, "\n");
503 0 : }
504 :
505 : //============================================================================
506 : // frange_storage implementation
507 : //============================================================================
508 :
509 : // Return the number of bytes to allocate for an frange_storage holding R.
510 :
511 : size_t
512 12817226 : frange_storage::size (const frange &r)
513 : {
514 12817226 : return sizeof (frange_storage) + (r.num_pairs () - 1) * sizeof (frange_pair);
515 : }
516 :
517 : // Allocate a new frange_storage object initialized to R.
518 :
519 : frange_storage *
520 12817226 : frange_storage::alloc (vrange_internal_alloc &allocator, const frange &r)
521 : {
522 12817226 : frange_storage *p
523 12817226 : = static_cast <frange_storage *> (allocator.alloc (size (r)));
524 12817226 : new (p) frange_storage (r);
525 12817226 : return p;
526 : }
527 :
528 12817226 : frange_storage::frange_storage (const frange &r)
529 12817226 : : vrange_storage (VR_FRANGE), m_max_ranges (r.num_pairs ())
530 : {
531 12817226 : set_frange (r);
532 12817226 : }
533 :
534 : void
535 13399092 : frange_storage::set_frange (const frange &r)
536 : {
537 13399092 : gcc_checking_assert (fits_p (r));
538 :
539 13399092 : m_kind = r.m_kind;
540 13399092 : m_num_ranges = r.m_num_ranges;
541 27285507 : for (unsigned i = 0; i < r.m_num_ranges; ++i)
542 13886415 : m_pairs[i] = r.m_pairs[i];
543 13399092 : m_pos_nan = r.m_pos_nan;
544 13399092 : m_neg_nan = r.m_neg_nan;
545 13399092 : }
546 :
547 : void
548 45406510 : frange_storage::get_frange (frange &r, tree type) const
549 : {
550 45406510 : gcc_checking_assert (r.supports_type_p (type));
551 :
552 : // Handle explicit NANs.
553 45406510 : if (m_kind == VR_NAN)
554 : {
555 112079 : if (HONOR_NANS (type))
556 : {
557 112079 : if (m_pos_nan && m_neg_nan)
558 106626 : r.set_nan (type);
559 : else
560 5453 : r.set_nan (type, m_neg_nan);
561 : }
562 : else
563 0 : r.set_undefined ();
564 : return;
565 : }
566 45294431 : if (m_kind == VR_UNDEFINED)
567 : {
568 60843 : r.set_undefined ();
569 60843 : return;
570 : }
571 45233588 : if (m_kind == VR_VARYING)
572 : {
573 31352965 : r.set_varying (type);
574 31352965 : return;
575 : }
576 :
577 : // Rebuild piecewise, like irange_storage::get_irange().
578 13880623 : r.set_undefined ();
579 43250706 : for (unsigned i = 0; i < m_num_ranges; ++i)
580 : {
581 15489460 : frange tmp (type, m_pairs[i].min, m_pairs[i].max, m_kind);
582 15489460 : r.union_ (tmp);
583 15489460 : }
584 :
585 : // The constructor will set the NAN bits for HONOR_NANS, but we must
586 : // make sure to set the NAN sign if known.
587 13880623 : if (HONOR_NANS (type) && (m_pos_nan ^ m_neg_nan) == 1)
588 1359509 : r.update_nan (m_neg_nan);
589 12521114 : else if (!m_pos_nan && !m_neg_nan)
590 10077440 : r.clear_nan ();
591 : }
592 :
593 : bool
594 20347 : frange_storage::equal_p (const frange &r) const
595 : {
596 20347 : if (r.undefined_p ())
597 0 : return m_kind == VR_UNDEFINED;
598 :
599 20347 : frange tmp;
600 20347 : get_frange (tmp, r.type ());
601 20347 : return tmp == r;
602 20347 : }
603 :
604 : bool
605 14611216 : frange_storage::fits_p (const frange &r) const
606 : {
607 14611216 : return m_max_ranges >= r.num_pairs ();
608 : }
609 :
610 : //============================================================================
611 : // prange_storage implementation
612 : //============================================================================
613 :
614 : prange_storage *
615 100401805 : prange_storage::alloc (vrange_internal_alloc &allocator, const prange &r,
616 : bool shared_p)
617 : {
618 100401805 : unsigned num_words;
619 100401805 : prange_format (r, num_words);
620 100401805 : size_t extra_size = 0;
621 100401805 : if (num_words)
622 : {
623 2345577 : unsigned short precision = TYPE_PRECISION (r.type ());
624 2345577 : extra_size = trailing_wide_ints<PRANGE_STORAGE_NINTS>
625 2345577 : ::extra_size (precision, num_words);
626 : }
627 :
628 100401805 : size_t size = sizeof (prange_storage) + extra_size;
629 100401805 : prange_storage *p = static_cast <prange_storage *> (allocator.alloc (size));
630 100401805 : new (p) prange_storage (r);
631 100401805 : if (p->m_pt && !shared_p)
632 2039873 : p->m_pt = unshare_expr_without_location (p->m_pt);
633 :
634 100401805 : return p;
635 : }
636 :
637 : // Initialize the storage with R.
638 :
639 100401805 : prange_storage::prange_storage (const prange &r) : vrange_storage (VR_PRANGE)
640 : {
641 100401805 : unsigned num_words;
642 100401805 : enum prange_kind kind = prange_format (r, num_words);
643 100401805 : unsigned short prec = (kind == PR_UNDEFINED) ? 0 : TYPE_PRECISION (r.type ());
644 100401805 : m_trailing_ints.set_precision (prec, num_words);
645 100401805 : set_prange (r);
646 100401805 : }
647 :
648 : // Return TRUE if R is exactly the nonzero set [1, MAX], which prange_storage
649 : // encodes compactly as PR_NONZERO.
650 : //
651 : // Compare the bounds against a fresh set_nonzero () rather than using
652 : // prange::operator==, because operator== also compares the bitmask and
653 : // points-to info, which are stored separately here, so a non-null pointer that
654 : // also carries e.g. an alignment bitmask still belongs in PR_NONZERO.
655 :
656 : static inline bool
657 145690677 : nonzero_range_p (const prange &r)
658 : {
659 145690677 : prange nonzero (r.type ());
660 145690677 : nonzero.set_nonzero (r.type ());
661 291381354 : return (r.lower_bound () == nonzero.lower_bound ()
662 289046675 : && r.upper_bound () == nonzero.upper_bound ());
663 145690677 : }
664 :
665 : // Return the prange_kind for range R, and the number of words of storage
666 : // it requires in NUM_WORDS.
667 :
668 : enum prange_kind
669 311726519 : prange_storage::prange_format (const prange &r, unsigned &num_words)
670 : {
671 311726519 : num_words = 0;
672 311726519 : if (r.undefined_p ())
673 : return PR_UNDEFINED;
674 :
675 281587675 : if (r.varying_p ())
676 : return PR_VARYING;
677 :
678 132134128 : if (r.zero_p ())
679 : return PR_ZERO;
680 :
681 131276579 : enum prange_kind kind = PR_NONZERO;
682 :
683 131276579 : if (!nonzero_range_p (r))
684 : {
685 2996377 : prange tmp (r.type ());
686 5992754 : if (r.lower_bound () == tmp.lower_bound ()
687 4360684 : && r.upper_bound () == tmp.upper_bound ())
688 : kind = PR_FULL;
689 : else
690 : {
691 : // PR_OTHER requires words of storage for the end points.
692 2779266 : kind = PR_OTHER;
693 2779266 : num_words += 2;
694 : }
695 2996377 : }
696 :
697 : // Bitmasks require 2 words of storage.
698 131276579 : if (!r.get_bitmask ().unknown_p ())
699 5261652 : num_words += 2;
700 :
701 : // PR_FULL must have a bitmask or points to, or it should be PR_VARYING.
702 131493690 : gcc_checking_assert (kind != PR_FULL || !r.get_bitmask ().unknown_p ()
703 : || r.m_pt != NULL_TREE);
704 131276579 : return kind;
705 : }
706 :
707 : void
708 103906362 : prange_storage::set_prange (const prange &r)
709 : {
710 103906362 : unsigned num_words;
711 103906362 : m_kind = prange_format (r, num_words);
712 103906362 : m_has_bitmask = false;
713 103906362 : m_points_to_p = false;
714 103906362 : m_pt = r.m_pt;
715 :
716 103906362 : unsigned index = 0;
717 :
718 103906362 : switch (m_kind)
719 : {
720 60156698 : case PR_UNDEFINED:
721 60156698 : case PR_VARYING:
722 60156698 : case PR_ZERO:
723 60156698 : return;
724 : case PR_NONZERO:
725 : case PR_FULL:
726 : break;
727 856699 : case PR_OTHER:
728 856699 : set_word (index++, r.lower_bound (), r.type ());
729 856699 : set_word (index++, r.upper_bound (), r.type ());
730 856699 : break;
731 0 : default:
732 0 : gcc_unreachable ();
733 : }
734 :
735 43749664 : m_has_bitmask = !r.get_bitmask ().unknown_p ();
736 43749664 : m_points_to_p = r.m_points_to_p;
737 :
738 43749664 : if (m_has_bitmask)
739 : {
740 1762019 : irange_bitmask bm = r.m_bitmask;
741 1762019 : set_word (index++, r.m_bitmask.value (), r.type ());
742 1762019 : set_word (index++, r.m_bitmask.mask (), r.type ());
743 1762019 : }
744 43749664 : gcc_checking_assert (index == num_words);
745 : }
746 :
747 : void
748 363735011 : prange_storage::get_prange (prange &r, tree type) const
749 : {
750 363735011 : gcc_checking_assert (r.supports_type_p (type));
751 363735011 : unsigned index = 0;
752 363735011 : switch (m_kind)
753 : {
754 972771 : case PR_UNDEFINED:
755 972771 : r.set_undefined ();
756 972771 : return;
757 :
758 201409907 : case PR_VARYING:
759 201409907 : r.set_varying (type);
760 201409907 : return;
761 :
762 484954 : case PR_ZERO:
763 484954 : r.set_zero (type);
764 484954 : return;
765 :
766 157468708 : case PR_NONZERO:
767 157468708 : r.set_nonzero (type);
768 157468708 : break;
769 :
770 522940 : case PR_FULL:
771 522940 : {
772 522940 : r.m_kind = VR_RANGE;
773 522940 : r.m_type = type;
774 522940 : prange tmp (type);
775 522940 : r.m_min = tmp.lower_bound ();
776 522940 : r.m_max = tmp.upper_bound ();
777 522940 : break;
778 522940 : }
779 :
780 2875731 : case PR_OTHER:
781 2875731 : {
782 2875731 : gcc_checking_assert (m_kind == PR_OTHER);
783 2875731 : r.m_kind = VR_RANGE;
784 2875731 : r.m_type = type;
785 2875731 : r.m_min = get_word (index++, type);
786 2875731 : r.m_max = get_word (index++, type);
787 2875731 : break;
788 : }
789 0 : default:
790 0 : gcc_unreachable ();
791 : }
792 :
793 160867379 : if (m_has_bitmask)
794 : {
795 17455629 : wide_int value = get_word (index++, type);
796 17455629 : wide_int mask = get_word (index++, type);
797 17455629 : r.m_bitmask = irange_bitmask (value, mask);
798 17455629 : }
799 : else
800 143411750 : r.m_bitmask.set_unknown (TYPE_PRECISION (type));
801 :
802 160867379 : r.m_points_to_p = m_points_to_p;
803 160867379 : r.m_pt = m_pt;
804 :
805 160867379 : if (flag_checking)
806 160867244 : r.verify_range ();
807 : }
808 :
809 : bool
810 14843018 : prange_storage::equal_p (const prange &r) const
811 : {
812 14843018 : if (r.undefined_p ())
813 0 : return m_kind == PR_UNDEFINED;
814 :
815 14843018 : unsigned index = 0;
816 14843018 : switch (m_kind)
817 : {
818 5596 : case PR_VARYING:
819 5596 : return r.varying_p ();
820 :
821 85769 : case PR_ZERO:
822 85769 : return r.zero_p ();
823 :
824 14414098 : case PR_NONZERO:
825 14414098 : if (!nonzero_range_p (r))
826 : return false;
827 : break;
828 :
829 296390 : case PR_FULL:
830 296390 : if (r.m_min != wi::zero (TYPE_PRECISION (r.m_type))
831 592382 : || r.m_max != wi::max_value (TYPE_PRECISION (r.m_type),
832 147996 : TYPE_SIGN (r.m_type)))
833 : return false;
834 : break;
835 :
836 41165 : case PR_OTHER:
837 82330 : if (r.m_min != get_word (index++, r.m_type)
838 65635 : || r.m_max != get_word (index++, r.m_type))
839 : return false;
840 : break;
841 :
842 0 : default:
843 0 : gcc_unreachable ();
844 : }
845 :
846 14182554 : if (m_has_bitmask)
847 : {
848 8355505 : wide_int value = get_word (index++, r.m_type);
849 8355505 : wide_int mask = get_word (index++, r.m_type);
850 8355505 : if (r.m_bitmask != irange_bitmask (value, mask))
851 4073820 : return false;
852 8355505 : }
853 : else
854 5827049 : if (!r.m_bitmask.unknown_p ())
855 : return false;
856 :
857 8509647 : if (m_pt != r.m_pt)
858 : return false;
859 : // Storage objects are only equal If they point to the same memory.
860 1499768 : if (m_points_to_p != r.m_points_to_p)
861 0 : return false;
862 :
863 : return true;
864 : }
865 :
866 : bool
867 7032935 : prange_storage::fits_p (const prange &r) const
868 : {
869 : // Undefined ranges always fit, because they don't store anything in
870 : // the trailing wide ints.
871 7032935 : if (r.undefined_p ())
872 : return true;
873 :
874 7016547 : unsigned num_words;
875 7016547 : prange_format (r, num_words);
876 7016547 : return num_words <= m_trailing_ints.num_elements ();
877 : }
878 :
879 :
880 : static vrange_allocator ggc_vrange_allocator (true);
881 :
882 0 : vrange_storage *ggc_alloc_vrange_storage (tree type)
883 : {
884 0 : return ggc_vrange_allocator.clone_varying (type);
885 : }
886 :
887 20789801 : vrange_storage *ggc_alloc_vrange_storage (const vrange &r, bool shared_p)
888 : {
889 20789801 : return ggc_vrange_allocator.clone (r, shared_p);
890 : }
|
