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 98699106 : vrange_internal_alloc () { }
40 98699094 : 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 98403096 : vrange_obstack_alloc ()
51 98403096 : {
52 98403096 : obstack_init (&m_obstack);
53 98403096 : }
54 98403084 : virtual ~vrange_obstack_alloc () final override
55 98403084 : {
56 98403084 : obstack_free (&m_obstack, NULL);
57 98403084 : }
58 426003377 : virtual void *alloc (size_t size) final override
59 : {
60 426003377 : 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 296010 : vrange_ggc_alloc () { }
71 296010 : virtual ~vrange_ggc_alloc () final override { }
72 42560666 : virtual void *alloc (size_t size) final override
73 : {
74 42560666 : 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 98699106 : vrange_allocator::vrange_allocator (bool gc)
83 : {
84 98699106 : if (gc)
85 296010 : m_alloc = new vrange_ggc_alloc;
86 : else
87 98403096 : m_alloc = new vrange_obstack_alloc;
88 98699106 : }
89 :
90 98699094 : vrange_allocator::~vrange_allocator ()
91 : {
92 98699094 : delete m_alloc;
93 98699094 : }
94 :
95 : void *
96 59665090 : vrange_allocator::alloc (size_t size)
97 : {
98 59665090 : 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 337467213 : vrange_allocator::clone (const vrange &r, bool shared_p)
112 : {
113 337467213 : return vrange_storage::alloc (*m_alloc, r, shared_p);
114 : }
115 :
116 : vrange_storage *
117 41658563 : vrange_allocator::clone_varying (tree type)
118 : {
119 41658563 : if (irange::supports_p (type))
120 19799793 : return irange_storage::alloc (*m_alloc, int_range <1> (type));
121 21858770 : if (prange::supports_p (type))
122 21374967 : return prange_storage::alloc (*m_alloc, prange (type));
123 483803 : if (frange::supports_p (type))
124 483803 : return frange_storage::alloc (*m_alloc, frange (type));
125 : return NULL;
126 : }
127 :
128 : vrange_storage *
129 29773177 : vrange_allocator::clone_undefined (tree type)
130 : {
131 29773177 : if (irange::supports_p (type))
132 19696925 : return irange_storage::alloc (*m_alloc, int_range<1> ());
133 10076252 : if (prange::supports_p (type))
134 9596621 : return prange_storage::alloc (*m_alloc, prange ());
135 479631 : if (frange::supports_p (type))
136 479631 : 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 337467213 : vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r,
145 : bool shared_p)
146 : {
147 337467213 : if (is_a <irange> (r))
148 234141819 : return irange_storage::alloc (allocator, as_a <irange> (r));
149 103325394 : if (is_a <prange> (r))
150 91258595 : return prange_storage::alloc (allocator, as_a <prange> (r), shared_p);
151 12066799 : if (is_a <frange> (r))
152 12066799 : return frange_storage::alloc (allocator, as_a <frange> (r));
153 : return NULL;
154 : }
155 :
156 : // Set storage to R.
157 :
158 : void
159 29124070 : vrange_storage::set_vrange (const vrange &r)
160 : {
161 29124070 : if (irange_storage *s = dyn_irange ())
162 : {
163 23765795 : gcc_checking_assert (s->fits_p (as_a <irange> (r)));
164 23765795 : s->set_irange (as_a <irange> (r));
165 : }
166 5358275 : else if (prange_storage *s = dyn_prange ())
167 : {
168 4759827 : gcc_checking_assert (s->fits_p (as_a <prange> (r)));
169 4759827 : s->set_prange (as_a <prange> (r));
170 : }
171 598448 : else if (frange_storage *s = dyn_frange ())
172 : {
173 598448 : gcc_checking_assert (s->fits_p (as_a <frange> (r)));
174 598448 : s->set_frange (as_a <frange> (r));
175 : }
176 : else
177 0 : gcc_unreachable ();
178 :
179 : // Verify that reading back from the cache didn't drop bits.
180 29124070 : if (flag_checking
181 : // FIXME: Avoid checking frange, as it currently pessimizes some ranges:
182 : //
183 : // gfortran.dg/pr49472.f90 pessimizes [0.0, 1.0] into [-0.0, 1.0].
184 29123999 : && !is_a <frange> (r)
185 57649621 : && !r.undefined_p ())
186 : {
187 28366361 : value_range tmp (r);
188 28366361 : get_vrange (tmp, r.type ());
189 28366361 : gcc_checking_assert (tmp == r);
190 28366361 : }
191 29124070 : }
192 :
193 : // Restore R from storage.
194 :
195 : void
196 2105201950 : vrange_storage::get_vrange (vrange &r, tree type) const
197 : {
198 2105201950 : if (const irange_storage *s = dyn_irange ())
199 1548032181 : s->get_irange (as_a <irange> (r), type);
200 557169769 : else if (const prange_storage *s = dyn_prange ())
201 508498017 : s->get_prange (as_a <prange> (r), type);
202 48671752 : else if (const frange_storage *s = dyn_frange ())
203 48671752 : s->get_frange (as_a <frange> (r), type);
204 : else
205 0 : gcc_unreachable ();
206 2105201950 : }
207 :
208 : // Return TRUE if storage can fit R.
209 :
210 : bool
211 34130316 : vrange_storage::fits_p (const vrange &r) const
212 : {
213 34130316 : if (const irange_storage *s = dyn_irange ())
214 28121247 : return s->fits_p (as_a <irange> (r));
215 6009069 : if (const prange_storage *s = dyn_prange ())
216 5361759 : return s->fits_p (as_a <prange> (r));
217 647310 : if (const frange_storage *s = dyn_frange ())
218 647310 : return s->fits_p (as_a <frange> (r));
219 0 : gcc_unreachable ();
220 : }
221 :
222 : // Return TRUE if the range in storage is equal to R. It is the
223 : // caller's responsibility to verify that the type of the range in
224 : // storage matches that of R.
225 :
226 : bool
227 15438680 : vrange_storage::equal_p (const vrange &r) const
228 : {
229 15438680 : if (const irange_storage *s = dyn_irange ())
230 4071279 : return s->equal_p (as_a <irange> (r));
231 11367401 : if (const prange_storage *s = dyn_prange ())
232 11347130 : return s->equal_p (as_a <prange> (r));
233 20271 : if (const frange_storage *s = dyn_frange ())
234 20271 : return s->equal_p (as_a <frange> (r));
235 0 : gcc_unreachable ();
236 : }
237 :
238 : //============================================================================
239 : // irange_storage implementation
240 : //============================================================================
241 :
242 : unsigned short *
243 1212920155 : irange_storage::write_lengths_address ()
244 : {
245 1212920155 : return (unsigned short *)&m_val[(m_num_ranges * 2 + 2)
246 1212920155 : * WIDE_INT_MAX_HWIS (m_precision)];
247 : }
248 :
249 : const unsigned short *
250 1056679726 : irange_storage::lengths_address () const
251 : {
252 1056679726 : return const_cast <irange_storage *> (this)->write_lengths_address ();
253 : }
254 :
255 : // Allocate a new irange_storage object initialized to R.
256 :
257 : irange_storage *
258 273638537 : irange_storage::alloc (vrange_internal_alloc &allocator, const irange &r)
259 : {
260 273638537 : size_t size = irange_storage::size (r);
261 273638537 : irange_storage *p = static_cast <irange_storage *> (allocator.alloc (size));
262 273638537 : new (p) irange_storage (r);
263 273638537 : return p;
264 : }
265 :
266 : // Initialize the storage with R.
267 :
268 273638537 : irange_storage::irange_storage (const irange &r)
269 273638537 : : vrange_storage (VR_IRANGE), m_max_ranges (r.num_pairs ())
270 : {
271 273638537 : m_num_ranges = m_max_ranges;
272 273638537 : set_irange (r);
273 273638537 : }
274 :
275 : static inline void
276 750647060 : write_wide_int (HOST_WIDE_INT *&val, unsigned short *&len, const wide_int &w)
277 : {
278 750647060 : *len = w.get_len ();
279 1502717498 : for (unsigned i = 0; i < *len; ++i)
280 752070438 : *val++ = w.elt (i);
281 750647060 : ++len;
282 750647060 : }
283 :
284 : // Store R into the current storage.
285 :
286 : void
287 297404332 : irange_storage::set_irange (const irange &r)
288 : {
289 297404332 : gcc_checking_assert (fits_p (r));
290 :
291 297404332 : if (r.undefined_p ())
292 : {
293 20143116 : m_kind = VR_UNDEFINED;
294 141163903 : return;
295 : }
296 277261216 : if (r.varying_p ())
297 : {
298 121020787 : m_kind = VR_VARYING;
299 121020787 : return;
300 : }
301 :
302 156240429 : m_precision = TYPE_PRECISION (r.type ());
303 156240429 : m_num_ranges = r.num_pairs ();
304 156240429 : m_kind = VR_RANGE;
305 :
306 156240429 : HOST_WIDE_INT *val = &m_val[0];
307 156240429 : unsigned short *len = write_lengths_address ();
308 :
309 375323530 : for (unsigned i = 0; i < r.num_pairs (); ++i)
310 : {
311 219083101 : write_wide_int (val, len, r.lower_bound (i));
312 219085919 : write_wide_int (val, len, r.upper_bound (i));
313 : }
314 :
315 : // TODO: We could avoid streaming out the value if the mask is -1.
316 156240429 : irange_bitmask bm = r.m_bitmask;
317 156240429 : write_wide_int (val, len, bm.value ());
318 156240429 : write_wide_int (val, len, bm.mask ());
319 156240429 : }
320 :
321 : static inline void
322 5145733598 : read_wide_int (wide_int &w,
323 : const HOST_WIDE_INT *val, unsigned short len, unsigned prec)
324 : {
325 5145733598 : trailing_wide_int_storage stow (prec, &len,
326 1277104935 : const_cast <HOST_WIDE_INT *> (val));
327 3868628663 : w = trailing_wide_int (stow);
328 : }
329 :
330 : // Restore a range of TYPE from storage into R.
331 :
332 : void
333 1551652972 : irange_storage::get_irange (irange &r, tree type) const
334 : {
335 1551652972 : if (m_kind == VR_UNDEFINED)
336 : {
337 10084283 : r.set_undefined ();
338 505057529 : return;
339 : }
340 1541568689 : if (m_kind == VR_VARYING)
341 : {
342 484888963 : r.set_varying (type);
343 484888963 : return;
344 : }
345 :
346 1056679726 : gcc_checking_assert (TYPE_PRECISION (type) == m_precision);
347 1056679726 : const HOST_WIDE_INT *val = &m_val[0];
348 1056679726 : const unsigned short *len = lengths_address ();
349 :
350 : // Handle the common case where R can fit the new range.
351 1056679726 : if (r.m_max_ranges >= m_num_ranges)
352 : {
353 1019919333 : r.m_kind = VR_RANGE;
354 1019919333 : r.m_num_ranges = m_num_ranges;
355 1019919333 : r.m_type = type;
356 3611443061 : for (unsigned i = 0; i < m_num_ranges * 2; ++i)
357 : {
358 2591523728 : read_wide_int (r.m_base[i], val, *len, m_precision);
359 2591523728 : val += *len++;
360 : }
361 : }
362 : // Otherwise build the range piecewise.
363 : else
364 : {
365 36760393 : r.set_undefined ();
366 293945995 : for (unsigned i = 0; i < m_num_ranges; ++i)
367 : {
368 220425209 : wide_int lb, ub;
369 220425209 : read_wide_int (lb, val, *len, m_precision);
370 220425209 : val += *len++;
371 220425209 : read_wide_int (ub, val, *len, m_precision);
372 220425209 : val += *len++;
373 220425209 : int_range<1> tmp (type, lb, ub);
374 220425209 : r.union_ (tmp);
375 221015901 : }
376 : }
377 :
378 1056679726 : wide_int bits_value, bits_mask;
379 1056679726 : read_wide_int (bits_value, val, *len, m_precision);
380 1056679726 : val += *len++;
381 1056679726 : read_wide_int (bits_mask, val, *len, m_precision);
382 1056679726 : r.m_bitmask = irange_bitmask (bits_value, bits_mask);
383 1056679726 : if (r.m_kind == VR_VARYING)
384 0 : r.m_kind = VR_RANGE;
385 :
386 1056679726 : if (flag_checking)
387 1056676282 : r.verify_range ();
388 1056753237 : }
389 :
390 : bool
391 4071279 : irange_storage::equal_p (const irange &r) const
392 : {
393 4071279 : if (m_kind == VR_UNDEFINED || r.undefined_p ())
394 0 : return m_kind == r.m_kind;
395 4071279 : if (m_kind == VR_VARYING || r.varying_p ())
396 450488 : return m_kind == r.m_kind;
397 :
398 : // ?? We could make this faster by doing the comparison in place,
399 : // without going through get_irange.
400 3620791 : int_range_max tmp;
401 3620791 : get_irange (tmp, r.type ());
402 3620791 : return tmp == r;
403 3620791 : }
404 :
405 : // Return the size in bytes to allocate storage that can hold R.
406 :
407 : size_t
408 273638537 : irange_storage::size (const irange &r)
409 : {
410 273638537 : if (r.undefined_p ())
411 : return sizeof (irange_storage);
412 :
413 253645992 : unsigned prec = TYPE_PRECISION (r.type ());
414 253645992 : unsigned n = r.num_pairs () * 2 + 2;
415 253645992 : unsigned hwi_size = ((n * WIDE_INT_MAX_HWIS (prec) - 1)
416 : * sizeof (HOST_WIDE_INT));
417 253645992 : unsigned len_size = n * sizeof (unsigned short);
418 253645992 : return sizeof (irange_storage) + hwi_size + len_size;
419 : }
420 :
421 : // Return TRUE if R fits in the current storage.
422 :
423 : bool
424 349291374 : irange_storage::fits_p (const irange &r) const
425 : {
426 349291374 : return m_max_ranges >= r.num_pairs ();
427 : }
428 :
429 : void
430 0 : irange_storage::dump () const
431 : {
432 0 : fprintf (stderr, "irange_storage (prec=%d, ranges=%d):\n",
433 0 : m_precision, m_num_ranges);
434 :
435 0 : if (m_num_ranges == 0)
436 : return;
437 :
438 0 : const HOST_WIDE_INT *val = &m_val[0];
439 0 : const unsigned short *len = lengths_address ();
440 0 : int i, j;
441 :
442 0 : fprintf (stderr, " lengths = [ ");
443 0 : for (i = 0; i < m_num_ranges * 2 + 2; ++i)
444 0 : fprintf (stderr, "%d ", len[i]);
445 0 : fprintf (stderr, "]\n");
446 :
447 0 : for (i = 0; i < m_num_ranges; ++i)
448 : {
449 0 : for (j = 0; j < *len; ++j)
450 0 : fprintf (stderr, " [PAIR %d] LB " HOST_WIDE_INT_PRINT_DEC "\n", i,
451 0 : *val++);
452 0 : ++len;
453 0 : for (j = 0; j < *len; ++j)
454 0 : fprintf (stderr, " [PAIR %d] UB " HOST_WIDE_INT_PRINT_DEC "\n", i,
455 0 : *val++);
456 0 : ++len;
457 : }
458 :
459 : // Dump value/mask pair.
460 0 : for (j = 0; j < *len; ++j)
461 0 : fprintf (stderr, " [VALUE] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
462 0 : ++len;
463 0 : for (j = 0; j < *len; ++j)
464 0 : fprintf (stderr, " [MASK] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
465 : }
466 :
467 : DEBUG_FUNCTION void
468 0 : debug (const irange_storage &storage)
469 : {
470 0 : storage.dump ();
471 0 : fprintf (stderr, "\n");
472 0 : }
473 :
474 : //============================================================================
475 : // frange_storage implementation
476 : //============================================================================
477 :
478 : // Return the number of bytes to allocate for an frange_storage holding R.
479 :
480 : size_t
481 13030233 : frange_storage::size (const frange &r)
482 : {
483 13030233 : return sizeof (frange_storage) + (r.num_pairs () - 1) * sizeof (frange_pair);
484 : }
485 :
486 : // Allocate a new frange_storage object initialized to R.
487 :
488 : frange_storage *
489 13030233 : frange_storage::alloc (vrange_internal_alloc &allocator, const frange &r)
490 : {
491 13030233 : frange_storage *p
492 13030233 : = static_cast <frange_storage *> (allocator.alloc (size (r)));
493 13030233 : new (p) frange_storage (r);
494 13030233 : return p;
495 : }
496 :
497 13030233 : frange_storage::frange_storage (const frange &r)
498 13030233 : : vrange_storage (VR_FRANGE), m_max_ranges (r.num_pairs ())
499 : {
500 13030233 : set_frange (r);
501 13030233 : }
502 :
503 : void
504 13628681 : frange_storage::set_frange (const frange &r)
505 : {
506 13628681 : gcc_checking_assert (fits_p (r));
507 :
508 13628681 : m_kind = r.m_kind;
509 13628681 : m_num_ranges = r.m_num_ranges;
510 27749378 : for (unsigned i = 0; i < r.m_num_ranges; ++i)
511 14120697 : m_pairs[i] = r.m_pairs[i];
512 13628681 : m_pos_nan = r.m_pos_nan;
513 13628681 : m_neg_nan = r.m_neg_nan;
514 13628681 : }
515 :
516 : void
517 48692023 : frange_storage::get_frange (frange &r, tree type) const
518 : {
519 48692023 : gcc_checking_assert (r.supports_type_p (type));
520 :
521 : // Handle explicit NANs.
522 48692023 : if (m_kind == VR_NAN)
523 : {
524 113072 : if (HONOR_NANS (type))
525 : {
526 113072 : if (m_pos_nan && m_neg_nan)
527 107059 : r.set_nan (type);
528 : else
529 6013 : r.set_nan (type, m_neg_nan);
530 : }
531 : else
532 0 : r.set_undefined ();
533 : return;
534 : }
535 48578951 : if (m_kind == VR_UNDEFINED)
536 : {
537 62529 : r.set_undefined ();
538 62529 : return;
539 : }
540 48516422 : if (m_kind == VR_VARYING)
541 : {
542 34133479 : r.set_varying (type);
543 34133479 : return;
544 : }
545 :
546 : // Rebuild piecewise, like irange_storage::get_irange().
547 14382943 : r.set_undefined ();
548 44785614 : for (unsigned i = 0; i < m_num_ranges; ++i)
549 : {
550 16019728 : frange tmp (type, m_pairs[i].min, m_pairs[i].max, m_kind);
551 16019728 : r.union_ (tmp);
552 16019728 : }
553 :
554 : // The constructor will set the NAN bits for HONOR_NANS, but we must
555 : // make sure to set the NAN sign if known.
556 14382943 : if (HONOR_NANS (type) && (m_pos_nan ^ m_neg_nan) == 1)
557 1390593 : r.update_nan (m_neg_nan);
558 12992350 : else if (!m_pos_nan && !m_neg_nan)
559 10457889 : r.clear_nan ();
560 : }
561 :
562 : bool
563 20271 : frange_storage::equal_p (const frange &r) const
564 : {
565 20271 : if (r.undefined_p ())
566 0 : return m_kind == VR_UNDEFINED;
567 :
568 20271 : frange tmp;
569 20271 : get_frange (tmp, r.type ());
570 20271 : return tmp == r;
571 20271 : }
572 :
573 : bool
574 14874439 : frange_storage::fits_p (const frange &r) const
575 : {
576 14874439 : return m_max_ranges >= r.num_pairs ();
577 : }
578 :
579 : //============================================================================
580 : // prange_storage implementation
581 : //============================================================================
582 :
583 : prange_storage *
584 122230183 : prange_storage::alloc (vrange_internal_alloc &allocator, const prange &r,
585 : bool shared_p)
586 : {
587 122230183 : unsigned num_words;
588 122230183 : prange_format (r, num_words);
589 122230183 : size_t extra_size = 0;
590 122230183 : if (num_words)
591 : {
592 5474942 : unsigned short precision = TYPE_PRECISION (r.type ());
593 5474942 : extra_size = trailing_wide_ints<PRANGE_STORAGE_NINTS>
594 5474942 : ::extra_size (precision, num_words);
595 : }
596 :
597 122230183 : size_t size = sizeof (prange_storage) + extra_size;
598 122230183 : prange_storage *p = static_cast <prange_storage *> (allocator.alloc (size));
599 122230183 : new (p) prange_storage (r);
600 122230183 : if (p->m_addr && !shared_p)
601 963847 : p->m_addr = unshare_expr_without_location (p->m_addr);
602 :
603 122230183 : return p;
604 : }
605 :
606 : // Initialize the storage with R.
607 :
608 122230183 : prange_storage::prange_storage (const prange &r) : vrange_storage (VR_PRANGE)
609 : {
610 : // None of these is part of the range, so none is ever copied from one.
611 : // Only the accessors in tree-ssanames.cc ever make them non-zero, and
612 : // range_info_set_range carries them across a reallocation.
613 122230183 : pt = NULL;
614 :
615 122230183 : unsigned num_words;
616 122230183 : enum prange_kind kind = prange_format (r, num_words);
617 122230183 : unsigned short prec = (kind == PR_UNDEFINED) ? 0 : TYPE_PRECISION (r.type ());
618 122230183 : m_trailing_ints.set_precision (prec, num_words);
619 122230183 : set_prange (r);
620 122230183 : }
621 :
622 : // Return TRUE if R is exactly the nonzero set [1, MAX], which prange_storage
623 : // encodes compactly as PR_NONZERO.
624 : //
625 : // Compare the bounds against a fresh set_nonzero () rather than using
626 : // prange::operator==, because operator== also compares the bitmask and
627 : // address info, which are stored separately here, so a non-null pointer that
628 : // also carries e.g. an alignment bitmask still belongs in PR_NONZERO.
629 :
630 : static inline bool
631 160381374 : nonzero_range_p (const prange &r)
632 : {
633 160381374 : prange nonzero (r.type ());
634 160381374 : nonzero.set_nonzero (r.type ());
635 320762748 : return (r.lower_bound () == nonzero.lower_bound ()
636 309406938 : && r.upper_bound () == nonzero.upper_bound ());
637 160381374 : }
638 :
639 : // Return the prange_kind for range R, and the number of words of storage
640 : // it requires in NUM_WORDS.
641 :
642 : enum prange_kind
643 381554700 : prange_storage::prange_format (const prange &r, unsigned &num_words)
644 : {
645 381554700 : num_words = 0;
646 381554700 : if (r.undefined_p ())
647 : return PR_UNDEFINED;
648 :
649 352608297 : if (r.varying_p ())
650 : return PR_VARYING;
651 :
652 151061374 : if (r.zero_p ())
653 : return PR_ZERO;
654 :
655 149691094 : enum prange_kind kind = PR_NONZERO;
656 :
657 149691094 : if (!nonzero_range_p (r))
658 : {
659 12273545 : prange tmp (r.type ());
660 24547090 : if (r.lower_bound () == tmp.lower_bound ()
661 22596876 : && r.upper_bound () == tmp.upper_bound ())
662 : kind = PR_FULL;
663 : else
664 : {
665 : // PR_OTHER requires words of storage for the end points.
666 3306226 : kind = PR_OTHER;
667 3306226 : num_words += 2;
668 : }
669 12273545 : }
670 :
671 : // Bitmasks require 2 words of storage.
672 149691094 : if (!r.get_bitmask ().unknown_p ())
673 16642423 : num_words += 2;
674 :
675 : // PR_FULL must have a bitmask or an address, or it should be PR_VARYING.
676 158658413 : gcc_checking_assert (kind != PR_FULL || !r.get_bitmask ().unknown_p ()
677 : || r.m_addr != NULL_TREE);
678 149691094 : return kind;
679 : }
680 :
681 : void
682 126990010 : prange_storage::set_prange (const prange &r)
683 : {
684 126990010 : unsigned num_words;
685 126990010 : m_kind = prange_format (r, num_words);
686 126990010 : m_has_bitmask = false;
687 126990010 : m_known_p = false;
688 126990010 : m_addr = r.m_addr;
689 :
690 126990010 : unsigned index = 0;
691 :
692 126990010 : switch (m_kind)
693 : {
694 77294888 : case PR_UNDEFINED:
695 77294888 : case PR_VARYING:
696 77294888 : case PR_ZERO:
697 77294888 : return;
698 : case PR_NONZERO:
699 : case PR_FULL:
700 : break;
701 1046940 : case PR_OTHER:
702 1046940 : set_word (index++, r.lower_bound (), r.type ());
703 1046940 : set_word (index++, r.upper_bound (), r.type ());
704 1046940 : break;
705 0 : default:
706 0 : gcc_unreachable ();
707 : }
708 :
709 49695122 : m_has_bitmask = !r.get_bitmask ().unknown_p ();
710 49695122 : m_known_p = r.m_known_p;
711 :
712 49695122 : if (m_has_bitmask)
713 : {
714 5362514 : irange_bitmask bm = r.m_bitmask;
715 5362514 : set_word (index++, r.m_bitmask.value (), r.type ());
716 5362514 : set_word (index++, r.m_bitmask.mask (), r.type ());
717 5362514 : }
718 49695122 : gcc_checking_assert (index == num_words);
719 : }
720 :
721 : void
722 508498017 : prange_storage::get_prange (prange &r, tree type) const
723 : {
724 508498017 : gcc_checking_assert (r.supports_type_p (type));
725 508498017 : unsigned index = 0;
726 508498017 : switch (m_kind)
727 : {
728 912820 : case PR_UNDEFINED:
729 912820 : r.set_undefined ();
730 912820 : return;
731 :
732 306030738 : case PR_VARYING:
733 306030738 : r.set_varying (type);
734 306030738 : return;
735 :
736 791114 : case PR_ZERO:
737 791114 : r.set_zero (type);
738 791114 : return;
739 :
740 185918168 : case PR_NONZERO:
741 185918168 : r.set_nonzero (type);
742 185918168 : break;
743 :
744 10797565 : case PR_FULL:
745 10797565 : {
746 10797565 : r.m_kind = VR_RANGE;
747 10797565 : r.m_type = type;
748 10797565 : prange tmp (type);
749 10797565 : r.m_min = tmp.lower_bound ();
750 10797565 : r.m_max = tmp.upper_bound ();
751 10797565 : break;
752 10797565 : }
753 :
754 4047612 : case PR_OTHER:
755 4047612 : {
756 4047612 : gcc_checking_assert (m_kind == PR_OTHER);
757 4047612 : r.m_kind = VR_RANGE;
758 4047612 : r.m_type = type;
759 4047612 : r.m_min = get_word (index++, type);
760 4047612 : r.m_max = get_word (index++, type);
761 4047612 : break;
762 : }
763 0 : default:
764 0 : gcc_unreachable ();
765 : }
766 :
767 200763345 : if (m_has_bitmask)
768 : {
769 32021036 : wide_int value = get_word (index++, type);
770 32021036 : wide_int mask = get_word (index++, type);
771 32021036 : r.m_bitmask = irange_bitmask (value, mask);
772 32021036 : }
773 : else
774 168742309 : r.m_bitmask.set_unknown (TYPE_PRECISION (type));
775 :
776 200763345 : r.m_known_p = m_known_p;
777 200763345 : r.m_addr = m_addr;
778 :
779 200763345 : if (flag_checking)
780 200763147 : r.verify_range ();
781 : }
782 :
783 : bool
784 11347130 : prange_storage::equal_p (const prange &r) const
785 : {
786 11347130 : if (r.undefined_p ())
787 0 : return m_kind == PR_UNDEFINED;
788 :
789 11347130 : unsigned index = 0;
790 11347130 : switch (m_kind)
791 : {
792 8715 : case PR_VARYING:
793 8715 : return r.varying_p ();
794 :
795 100875 : case PR_ZERO:
796 100875 : return r.zero_p ();
797 :
798 10690280 : case PR_NONZERO:
799 10690280 : if (!nonzero_range_p (r))
800 : return false;
801 : break;
802 :
803 517641 : case PR_FULL:
804 517641 : if (r.m_min != wi::zero (TYPE_PRECISION (r.m_type))
805 962815 : || r.m_max != wi::max_value (TYPE_PRECISION (r.m_type),
806 222587 : TYPE_SIGN (r.m_type)))
807 : return false;
808 : break;
809 :
810 29619 : case PR_OTHER:
811 59238 : if (r.m_min != get_word (index++, r.m_type)
812 46318 : || r.m_max != get_word (index++, r.m_type))
813 : return false;
814 : break;
815 :
816 0 : default:
817 0 : gcc_unreachable ();
818 : }
819 :
820 10686045 : if (m_has_bitmask)
821 : {
822 4274704 : wide_int value = get_word (index++, r.m_type);
823 4274704 : wide_int mask = get_word (index++, r.m_type);
824 4274704 : if (r.m_bitmask != irange_bitmask (value, mask))
825 1706431 : return false;
826 4274704 : }
827 : else
828 6411341 : if (!r.m_bitmask.unknown_p ())
829 : return false;
830 :
831 7033455 : if (m_addr != r.m_addr)
832 : return false;
833 : // Storage objects are only equal If they point to the same memory.
834 2547847 : if (m_known_p != r.m_known_p)
835 0 : return false;
836 :
837 : return true;
838 : }
839 :
840 : bool
841 10121586 : prange_storage::fits_p (const prange &r) const
842 : {
843 : // Undefined ranges always fit, because they don't store anything in
844 : // the trailing wide ints.
845 10121586 : if (r.undefined_p ())
846 : return true;
847 :
848 10104324 : unsigned num_words;
849 10104324 : prange_format (r, num_words);
850 10104324 : return num_words <= m_trailing_ints.num_elements ();
851 : }
852 :
853 : // Ensure this range of type TYPE does not contain zero.
854 :
855 : void
856 4704060 : prange_storage::set_nonnull (tree type)
857 : {
858 4704060 : gcc_checking_assert (m_kind != PR_UNDEFINED);
859 4704060 : switch (m_kind)
860 : {
861 1724989 : case PR_VARYING:
862 1724989 : case PR_FULL:
863 1724989 : m_kind = PR_NONZERO;
864 1724989 : return;
865 :
866 : case PR_NONZERO:
867 : return;
868 :
869 0 : case PR_ZERO:
870 0 : m_kind = PR_UNDEFINED;
871 0 : return;
872 :
873 32532 : case PR_OTHER:
874 32532 : if (get_word (0, type) != 0)
875 : return;
876 : // [0,1] -> [1,1] is a special case and requires adjustments.
877 : // otherwise we can simply set the lower bound to 1.
878 0 : if (get_word (1, type) != 1)
879 0 : set_word (0, wi::one (TYPE_PRECISION (type)), type);
880 : else
881 : {
882 : // This is very uncoomon, and rather than trying to cover
883 : // the edge cases (ie, bitmask present, address present)
884 : // simply load the range, remove zero, and resave it.
885 0 : prange pr;
886 0 : this->get_vrange (pr, type);
887 0 : prange nz;
888 0 : nz.set_nonzero (type);
889 0 : if (pr.intersect (nz))
890 0 : this->set_prange (pr);
891 0 : }
892 : return;
893 :
894 0 : default:
895 0 : gcc_unreachable ();
896 : }
897 : }
898 :
899 : irange_bitmask
900 97362455 : prange_storage::get_bitmask (tree type) const
901 : {
902 97362455 : gcc_checking_assert (m_kind != PR_UNDEFINED);
903 97362455 : unsigned prec = TYPE_PRECISION (type);
904 97362455 : unsigned index = 0;
905 :
906 97362455 : switch (m_kind)
907 : {
908 67843959 : case PR_VARYING:
909 67843959 : return irange_bitmask (prec);
910 :
911 409 : case PR_ZERO:
912 409 : return irange_bitmask (type, wi::zero (prec), wi::zero (prec));
913 :
914 : case PR_NONZERO:
915 : case PR_FULL:
916 : break;
917 :
918 337460 : case PR_OTHER:
919 337460 : index = 2;
920 337460 : break;
921 :
922 0 : default:
923 0 : gcc_unreachable ();
924 : }
925 :
926 29518087 : if (m_has_bitmask)
927 : {
928 11538812 : wide_int value = get_word (index++, type);
929 11538812 : wide_int mask = get_word (index++, type);
930 11538812 : return irange_bitmask (value, mask);
931 11538812 : }
932 17979275 : return irange_bitmask (prec);
933 : }
934 :
935 :
936 : static vrange_allocator ggc_vrange_allocator (true);
937 :
938 11776167 : vrange_storage *ggc_alloc_vrange_storage (tree type)
939 : {
940 11776167 : return ggc_vrange_allocator.clone_varying (type);
941 : }
942 :
943 30784499 : vrange_storage *ggc_alloc_vrange_storage (const vrange &r, bool shared_p)
944 : {
945 30784499 : return ggc_vrange_allocator.clone (r, shared_p);
946 : }
|