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 "tree-pretty-print.h"
30 : #include "fold-const.h"
31 : #include "gimple-range.h"
32 : #include "value-range-storage.h"
33 :
34 : // Generic memory allocator to share one interface between GC and
35 : // obstack allocators.
36 :
37 : class vrange_internal_alloc
38 : {
39 : public:
40 120374388 : vrange_internal_alloc () { }
41 120374376 : virtual ~vrange_internal_alloc () { }
42 : virtual void *alloc (size_t size) = 0;
43 : virtual void free (void *) = 0;
44 : private:
45 : DISABLE_COPY_AND_ASSIGN (vrange_internal_alloc);
46 : };
47 :
48 : class vrange_obstack_alloc final: public vrange_internal_alloc
49 : {
50 : public:
51 120081362 : vrange_obstack_alloc ()
52 120081362 : {
53 120081362 : obstack_init (&m_obstack);
54 120081362 : }
55 120081350 : virtual ~vrange_obstack_alloc () final override
56 120081350 : {
57 120081350 : obstack_free (&m_obstack, NULL);
58 120081350 : }
59 410062594 : virtual void *alloc (size_t size) final override
60 : {
61 410062594 : return obstack_alloc (&m_obstack, size);
62 : }
63 0 : virtual void free (void *) final override { }
64 : private:
65 : obstack m_obstack;
66 : };
67 :
68 : class vrange_ggc_alloc final: public vrange_internal_alloc
69 : {
70 : public:
71 293026 : vrange_ggc_alloc () { }
72 293026 : virtual ~vrange_ggc_alloc () final override { }
73 20721192 : virtual void *alloc (size_t size) final override
74 : {
75 20721192 : return ggc_internal_alloc (size);
76 : }
77 0 : virtual void free (void *p) final override
78 : {
79 0 : return ggc_free (p);
80 : }
81 : };
82 :
83 120374388 : vrange_allocator::vrange_allocator (bool gc)
84 : {
85 120374388 : if (gc)
86 293026 : m_alloc = new vrange_ggc_alloc;
87 : else
88 120081362 : m_alloc = new vrange_obstack_alloc;
89 120374388 : }
90 :
91 120374376 : vrange_allocator::~vrange_allocator ()
92 : {
93 120374376 : delete m_alloc;
94 120374376 : }
95 :
96 : void *
97 58233587 : vrange_allocator::alloc (size_t size)
98 : {
99 58233587 : return m_alloc->alloc (size);
100 : }
101 :
102 : void
103 0 : vrange_allocator::free (void *p)
104 : {
105 0 : m_alloc->free (p);
106 0 : }
107 :
108 : // Allocate a new vrange_storage object initialized to R and return
109 : // it.
110 :
111 : vrange_storage *
112 314326687 : vrange_allocator::clone (const vrange &r, bool shared_p)
113 : {
114 314326687 : return vrange_storage::alloc (*m_alloc, r, shared_p);
115 : }
116 :
117 : vrange_storage *
118 29164361 : vrange_allocator::clone_varying (tree type)
119 : {
120 29164361 : if (irange::supports_p (type))
121 18681069 : return irange_storage::alloc (*m_alloc, int_range <1> (type));
122 10483292 : if (prange::supports_p (type))
123 10008305 : return prange_storage::alloc (*m_alloc, prange (type));
124 474987 : if (frange::supports_p (type))
125 474987 : return frange_storage::alloc (*m_alloc, frange (type));
126 : return NULL;
127 : }
128 :
129 : vrange_storage *
130 29059151 : vrange_allocator::clone_undefined (tree type)
131 : {
132 29059151 : if (irange::supports_p (type))
133 18581542 : return irange_storage::alloc (*m_alloc, int_range<1> ());
134 10477609 : if (prange::supports_p (type))
135 10006794 : return prange_storage::alloc (*m_alloc, prange ());
136 470815 : if (frange::supports_p (type))
137 470815 : return frange_storage::alloc (*m_alloc, frange ());
138 : return NULL;
139 : }
140 :
141 : // Allocate a new vrange_storage object initialized to R and return
142 : // it. Return NULL if R is unsupported.
143 :
144 : vrange_storage *
145 314326687 : vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r,
146 : bool shared_p)
147 : {
148 314326687 : if (is_a <irange> (r))
149 221912278 : return irange_storage::alloc (allocator, as_a <irange> (r));
150 92414409 : if (is_a <prange> (r))
151 80615198 : return prange_storage::alloc (allocator, as_a <prange> (r), shared_p);
152 11799211 : if (is_a <frange> (r))
153 11799211 : return frange_storage::alloc (allocator, as_a <frange> (r));
154 : return NULL;
155 : }
156 :
157 : // Set storage to R.
158 :
159 : void
160 26788406 : vrange_storage::set_vrange (const vrange &r)
161 : {
162 26788406 : if (is_a <irange> (r))
163 : {
164 22704062 : irange_storage *s = static_cast <irange_storage *> (this);
165 22704062 : gcc_checking_assert (s->fits_p (as_a <irange> (r)));
166 22704062 : s->set_irange (as_a <irange> (r));
167 : }
168 4084344 : else if (is_a <prange> (r))
169 : {
170 3508057 : prange_storage *s = static_cast <prange_storage *> (this);
171 3508057 : gcc_checking_assert (s->fits_p (as_a <prange> (r)));
172 3508057 : s->set_prange (as_a <prange> (r));
173 : }
174 576287 : else if (is_a <frange> (r))
175 : {
176 576287 : frange_storage *s = static_cast <frange_storage *> (this);
177 576287 : gcc_checking_assert (s->fits_p (as_a <frange> (r)));
178 576287 : s->set_frange (as_a <frange> (r));
179 : }
180 : else
181 0 : gcc_unreachable ();
182 :
183 : // Verify that reading back from the cache didn't drop bits.
184 26788406 : if (flag_checking
185 : // FIXME: Avoid checking frange, as it currently pessimizes some ranges:
186 : //
187 : // gfortran.dg/pr49472.f90 pessimizes [0.0, 1.0] into [-0.0, 1.0].
188 26788340 : && !is_a <frange> (r)
189 53000459 : && !r.undefined_p ())
190 : {
191 26064012 : value_range tmp (r);
192 26064012 : get_vrange (tmp, r.type ());
193 26064012 : gcc_checking_assert (tmp == r);
194 26064012 : }
195 26788406 : }
196 :
197 : // Restore R from storage.
198 :
199 : void
200 1810130129 : vrange_storage::get_vrange (vrange &r, tree type) const
201 : {
202 1810130129 : if (is_a <irange> (r))
203 : {
204 1377026279 : const irange_storage *s = static_cast <const irange_storage *> (this);
205 1377026279 : s->get_irange (as_a <irange> (r), type);
206 : }
207 433103850 : else if (is_a <prange> (r))
208 : {
209 387918370 : const prange_storage *s = static_cast <const prange_storage *> (this);
210 387918370 : s->get_prange (as_a <prange> (r), type);
211 : }
212 45185480 : else if (is_a <frange> (r))
213 : {
214 45185480 : const frange_storage *s = static_cast <const frange_storage *> (this);
215 45185480 : s->get_frange (as_a <frange> (r), type);
216 : }
217 : else
218 0 : gcc_unreachable ();
219 1810130129 : }
220 :
221 : // Return TRUE if storage can fit R.
222 :
223 : bool
224 31004946 : vrange_storage::fits_p (const vrange &r) const
225 : {
226 31004946 : if (is_a <irange> (r))
227 : {
228 26848986 : const irange_storage *s = static_cast <const irange_storage *> (this);
229 26848986 : return s->fits_p (as_a <irange> (r));
230 : }
231 4155960 : if (is_a <prange> (r))
232 : {
233 3532835 : const prange_storage *s = static_cast <const prange_storage *> (this);
234 3532835 : return s->fits_p (as_a <prange> (r));
235 : }
236 623125 : if (is_a <frange> (r))
237 : {
238 623125 : const frange_storage *s = static_cast <const frange_storage *> (this);
239 623125 : return s->fits_p (as_a <frange> (r));
240 : }
241 0 : gcc_unreachable ();
242 : return false;
243 : }
244 :
245 : // Return TRUE if the range in storage is equal to R. It is the
246 : // caller's responsibility to verify that the type of the range in
247 : // storage matches that of R.
248 :
249 : bool
250 18663315 : vrange_storage::equal_p (const vrange &r) const
251 : {
252 18663315 : if (is_a <irange> (r))
253 : {
254 3793879 : const irange_storage *s = static_cast <const irange_storage *> (this);
255 3793879 : return s->equal_p (as_a <irange> (r));
256 : }
257 14869436 : if (is_a <prange> (r))
258 : {
259 14849103 : const prange_storage *s = static_cast <const prange_storage *> (this);
260 14849103 : return s->equal_p (as_a <prange> (r));
261 : }
262 20333 : if (is_a <frange> (r))
263 : {
264 20333 : const frange_storage *s = static_cast <const frange_storage *> (this);
265 20333 : return s->equal_p (as_a <frange> (r));
266 : }
267 0 : gcc_unreachable ();
268 : }
269 :
270 : //============================================================================
271 : // irange_storage implementation
272 : //============================================================================
273 :
274 : unsigned short *
275 1109364155 : irange_storage::write_lengths_address ()
276 : {
277 1109364155 : return (unsigned short *)&m_val[(m_num_ranges * 2 + 2)
278 1109364155 : * WIDE_INT_MAX_HWIS (m_precision)];
279 : }
280 :
281 : const unsigned short *
282 962781913 : irange_storage::lengths_address () const
283 : {
284 962781913 : return const_cast <irange_storage *> (this)->write_lengths_address ();
285 : }
286 :
287 : // Allocate a new irange_storage object initialized to R.
288 :
289 : irange_storage *
290 259174889 : irange_storage::alloc (vrange_internal_alloc &allocator, const irange &r)
291 : {
292 259174889 : size_t size = irange_storage::size (r);
293 259174889 : irange_storage *p = static_cast <irange_storage *> (allocator.alloc (size));
294 259174889 : new (p) irange_storage (r);
295 259174889 : return p;
296 : }
297 :
298 : // Initialize the storage with R.
299 :
300 259174889 : irange_storage::irange_storage (const irange &r)
301 259174889 : : vrange_storage (VR_IRANGE), m_max_ranges (r.num_pairs ())
302 : {
303 259174889 : m_num_ranges = m_max_ranges;
304 259174889 : set_irange (r);
305 259174889 : }
306 :
307 : static inline void
308 699457138 : write_wide_int (HOST_WIDE_INT *&val, unsigned short *&len, const wide_int &w)
309 : {
310 699457138 : *len = w.get_len ();
311 1400183942 : for (unsigned i = 0; i < *len; ++i)
312 700726804 : *val++ = w.elt (i);
313 699457138 : ++len;
314 699457138 : }
315 :
316 : // Store R into the current storage.
317 :
318 : void
319 281878951 : irange_storage::set_irange (const irange &r)
320 : {
321 281878951 : gcc_checking_assert (fits_p (r));
322 :
323 281878951 : if (r.undefined_p ())
324 : {
325 19005543 : m_kind = VR_UNDEFINED;
326 135296709 : return;
327 : }
328 262873408 : if (r.varying_p ())
329 : {
330 116291166 : m_kind = VR_VARYING;
331 116291166 : return;
332 : }
333 :
334 146582242 : m_precision = TYPE_PRECISION (r.type ());
335 146582242 : m_num_ranges = r.num_pairs ();
336 146582242 : m_kind = VR_RANGE;
337 :
338 146582242 : HOST_WIDE_INT *val = &m_val[0];
339 146582242 : unsigned short *len = write_lengths_address ();
340 :
341 349728569 : for (unsigned i = 0; i < r.num_pairs (); ++i)
342 : {
343 203146327 : write_wide_int (val, len, r.lower_bound (i));
344 203149103 : write_wide_int (val, len, r.upper_bound (i));
345 : }
346 :
347 : // TODO: We could avoid streaming out the value if the mask is -1.
348 146582242 : irange_bitmask bm = r.m_bitmask;
349 146582242 : write_wide_int (val, len, bm.value ());
350 146582242 : write_wide_int (val, len, bm.mask ());
351 146582242 : }
352 :
353 : static inline void
354 4670413050 : read_wide_int (wide_int &w,
355 : const HOST_WIDE_INT *val, unsigned short len, unsigned prec)
356 : {
357 4670413050 : trailing_wide_int_storage stow (prec, &len,
358 1158379590 : const_cast <HOST_WIDE_INT *> (val));
359 3512033460 : w = trailing_wide_int (stow);
360 : }
361 :
362 : // Restore a range of TYPE from storage into R.
363 :
364 : void
365 1380363080 : irange_storage::get_irange (irange &r, tree type) const
366 : {
367 1380363080 : if (m_kind == VR_UNDEFINED)
368 : {
369 9919054 : r.set_undefined ();
370 427500221 : return;
371 : }
372 1370444026 : if (m_kind == VR_VARYING)
373 : {
374 407662113 : r.set_varying (type);
375 407662113 : return;
376 : }
377 :
378 962781913 : gcc_checking_assert (TYPE_PRECISION (type) == m_precision);
379 962781913 : const HOST_WIDE_INT *val = &m_val[0];
380 962781913 : const unsigned short *len = lengths_address ();
381 :
382 : // Handle the common case where R can fit the new range.
383 962781913 : if (r.m_max_ranges >= m_num_ranges)
384 : {
385 929093111 : r.m_kind = VR_RANGE;
386 929093111 : r.m_num_ranges = m_num_ranges;
387 929093111 : r.m_type = type;
388 3282746981 : for (unsigned i = 0; i < m_num_ranges * 2; ++i)
389 : {
390 2353653870 : read_wide_int (r.m_base[i], val, *len, m_precision);
391 2353653870 : val += *len++;
392 : }
393 : }
394 : // Otherwise build the range piecewise.
395 : else
396 : {
397 33688802 : r.set_undefined ();
398 262975281 : for (unsigned i = 0; i < m_num_ranges; ++i)
399 : {
400 195597677 : wide_int lb, ub;
401 195597677 : read_wide_int (lb, val, *len, m_precision);
402 195597677 : val += *len++;
403 195597677 : read_wide_int (ub, val, *len, m_precision);
404 195597677 : val += *len++;
405 195597677 : int_range<1> tmp (type, lb, ub);
406 195597677 : r.union_ (tmp);
407 196188369 : }
408 : }
409 :
410 962781913 : wide_int bits_value, bits_mask;
411 962781913 : read_wide_int (bits_value, val, *len, m_precision);
412 962781913 : val += *len++;
413 962781913 : read_wide_int (bits_mask, val, *len, m_precision);
414 962781913 : r.m_bitmask = irange_bitmask (bits_value, bits_mask);
415 962781913 : if (r.m_kind == VR_VARYING)
416 0 : r.m_kind = VR_RANGE;
417 :
418 962781913 : if (flag_checking)
419 962778527 : r.verify_range ();
420 962854990 : }
421 :
422 : bool
423 3793879 : irange_storage::equal_p (const irange &r) const
424 : {
425 3793879 : if (m_kind == VR_UNDEFINED || r.undefined_p ())
426 0 : return m_kind == r.m_kind;
427 3793879 : if (m_kind == VR_VARYING || r.varying_p ())
428 457078 : return m_kind == r.m_kind;
429 :
430 : // ?? We could make this faster by doing the comparison in place,
431 : // without going through get_irange.
432 3336801 : int_range_max tmp;
433 3336801 : get_irange (tmp, r.type ());
434 3336801 : return tmp == r;
435 3336801 : }
436 :
437 : // Return the size in bytes to allocate storage that can hold R.
438 :
439 : size_t
440 259174889 : irange_storage::size (const irange &r)
441 : {
442 259174889 : if (r.undefined_p ())
443 : return sizeof (irange_storage);
444 :
445 240309241 : unsigned prec = TYPE_PRECISION (r.type ());
446 240309241 : unsigned n = r.num_pairs () * 2 + 2;
447 240309241 : unsigned hwi_size = ((n * WIDE_INT_MAX_HWIS (prec) - 1)
448 : * sizeof (HOST_WIDE_INT));
449 240309241 : unsigned len_size = n * sizeof (unsigned short);
450 240309241 : return sizeof (irange_storage) + hwi_size + len_size;
451 : }
452 :
453 : // Return TRUE if R fits in the current storage.
454 :
455 : bool
456 331431999 : irange_storage::fits_p (const irange &r) const
457 : {
458 331431999 : return m_max_ranges >= r.num_pairs ();
459 : }
460 :
461 : void
462 0 : irange_storage::dump () const
463 : {
464 0 : fprintf (stderr, "irange_storage (prec=%d, ranges=%d):\n",
465 0 : m_precision, m_num_ranges);
466 :
467 0 : if (m_num_ranges == 0)
468 : return;
469 :
470 0 : const HOST_WIDE_INT *val = &m_val[0];
471 0 : const unsigned short *len = lengths_address ();
472 0 : int i, j;
473 :
474 0 : fprintf (stderr, " lengths = [ ");
475 0 : for (i = 0; i < m_num_ranges * 2 + 2; ++i)
476 0 : fprintf (stderr, "%d ", len[i]);
477 0 : fprintf (stderr, "]\n");
478 :
479 0 : for (i = 0; i < m_num_ranges; ++i)
480 : {
481 0 : for (j = 0; j < *len; ++j)
482 0 : fprintf (stderr, " [PAIR %d] LB " HOST_WIDE_INT_PRINT_DEC "\n", i,
483 0 : *val++);
484 0 : ++len;
485 0 : for (j = 0; j < *len; ++j)
486 0 : fprintf (stderr, " [PAIR %d] UB " HOST_WIDE_INT_PRINT_DEC "\n", i,
487 0 : *val++);
488 0 : ++len;
489 : }
490 :
491 : // Dump value/mask pair.
492 0 : for (j = 0; j < *len; ++j)
493 0 : fprintf (stderr, " [VALUE] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
494 0 : ++len;
495 0 : for (j = 0; j < *len; ++j)
496 0 : fprintf (stderr, " [MASK] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
497 : }
498 :
499 : DEBUG_FUNCTION void
500 0 : debug (const irange_storage &storage)
501 : {
502 0 : storage.dump ();
503 0 : fprintf (stderr, "\n");
504 0 : }
505 :
506 : //============================================================================
507 : // frange_storage implementation
508 : //============================================================================
509 :
510 : // Return the number of bytes to allocate for an frange_storage holding R.
511 :
512 : size_t
513 12745013 : frange_storage::size (const frange &r)
514 : {
515 12745013 : return sizeof (frange_storage) + (r.num_pairs () - 1) * sizeof (frange_pair);
516 : }
517 :
518 : // Allocate a new frange_storage object initialized to R.
519 :
520 : frange_storage *
521 12745013 : frange_storage::alloc (vrange_internal_alloc &allocator, const frange &r)
522 : {
523 12745013 : frange_storage *p
524 12745013 : = static_cast <frange_storage *> (allocator.alloc (size (r)));
525 12745013 : new (p) frange_storage (r);
526 12745013 : return p;
527 : }
528 :
529 12745013 : frange_storage::frange_storage (const frange &r)
530 12745013 : : vrange_storage (VR_FRANGE), m_max_ranges (r.num_pairs ())
531 : {
532 12745013 : set_frange (r);
533 12745013 : }
534 :
535 : void
536 13321300 : frange_storage::set_frange (const frange &r)
537 : {
538 13321300 : gcc_checking_assert (fits_p (r));
539 :
540 13321300 : m_kind = r.m_kind;
541 13321300 : m_num_ranges = r.m_num_ranges;
542 27101875 : for (unsigned i = 0; i < r.m_num_ranges; ++i)
543 13780575 : m_pairs[i] = r.m_pairs[i];
544 13321300 : m_pos_nan = r.m_pos_nan;
545 13321300 : m_neg_nan = r.m_neg_nan;
546 13321300 : }
547 :
548 : void
549 45205813 : frange_storage::get_frange (frange &r, tree type) const
550 : {
551 45205813 : gcc_checking_assert (r.supports_type_p (type));
552 :
553 : // Handle explicit NANs.
554 45205813 : if (m_kind == VR_NAN)
555 : {
556 111892 : if (HONOR_NANS (type))
557 : {
558 111892 : if (m_pos_nan && m_neg_nan)
559 106326 : r.set_nan (type);
560 : else
561 5566 : r.set_nan (type, m_neg_nan);
562 : }
563 : else
564 0 : r.set_undefined ();
565 : return;
566 : }
567 45093921 : if (m_kind == VR_UNDEFINED)
568 : {
569 59912 : r.set_undefined ();
570 59912 : return;
571 : }
572 45034009 : if (m_kind == VR_VARYING)
573 : {
574 31323601 : r.set_varying (type);
575 31323601 : return;
576 : }
577 :
578 : // Rebuild piecewise, like irange_storage::get_irange().
579 13710408 : r.set_undefined ();
580 42665853 : for (unsigned i = 0; i < m_num_ranges; ++i)
581 : {
582 15245037 : frange tmp (type, m_pairs[i].min, m_pairs[i].max, m_kind);
583 15245037 : r.union_ (tmp);
584 15245037 : }
585 :
586 : // The constructor will set the NAN bits for HONOR_NANS, but we must
587 : // make sure to set the NAN sign if known.
588 13710408 : if (HONOR_NANS (type) && (m_pos_nan ^ m_neg_nan) == 1)
589 1356063 : r.update_nan (m_neg_nan);
590 12354345 : else if (!m_pos_nan && !m_neg_nan)
591 9894248 : r.clear_nan ();
592 : }
593 :
594 : bool
595 20333 : frange_storage::equal_p (const frange &r) const
596 : {
597 20333 : if (r.undefined_p ())
598 0 : return m_kind == VR_UNDEFINED;
599 :
600 20333 : frange tmp;
601 20333 : get_frange (tmp, r.type ());
602 20333 : return tmp == r;
603 20333 : }
604 :
605 : bool
606 14520712 : frange_storage::fits_p (const frange &r) const
607 : {
608 14520712 : return m_max_ranges >= r.num_pairs ();
609 : }
610 :
611 : //============================================================================
612 : // prange_storage implementation
613 : //============================================================================
614 :
615 : prange_storage *
616 100630297 : prange_storage::alloc (vrange_internal_alloc &allocator, const prange &r,
617 : bool shared_p)
618 : {
619 100630297 : unsigned num_words;
620 100630297 : prange_format (r, num_words);
621 100630297 : size_t extra_size = 0;
622 100630297 : if (num_words)
623 : {
624 2350426 : unsigned short precision = TYPE_PRECISION (r.type ());
625 2350426 : extra_size = trailing_wide_ints<PRANGE_STORAGE_NINTS>
626 2350426 : ::extra_size (precision, num_words);
627 : }
628 :
629 100630297 : size_t size = sizeof (prange_storage) + extra_size;
630 100630297 : prange_storage *p = static_cast <prange_storage *> (allocator.alloc (size));
631 100630297 : new (p) prange_storage (r);
632 100630297 : if (p->m_pt && !shared_p)
633 2038277 : p->m_pt = unshare_expr_without_location (p->m_pt);
634 :
635 100630297 : return p;
636 : }
637 :
638 : // Initialize the storage with R.
639 :
640 100630297 : prange_storage::prange_storage (const prange &r) : vrange_storage (VR_PRANGE)
641 : {
642 100630297 : unsigned num_words;
643 100630297 : enum prange_kind kind = prange_format (r, num_words);
644 100630297 : unsigned short prec = (kind == PR_UNDEFINED) ? 0 : TYPE_PRECISION (r.type ());
645 100630297 : m_trailing_ints.set_precision (prec, num_words);
646 100630297 : set_prange (r);
647 100630297 : }
648 :
649 : // Return TRUE if R is exactly the nonzero set [1, MAX], which prange_storage
650 : // encodes compactly as PR_NONZERO.
651 : //
652 : // Compare the bounds against a fresh set_nonzero () rather than using
653 : // prange::operator==, because operator== also compares the bitmask and
654 : // points-to info, which are stored separately here, so a non-null pointer that
655 : // also carries e.g. an alignment bitmask still belongs in PR_NONZERO.
656 :
657 : static inline bool
658 145887200 : nonzero_range_p (const prange &r)
659 : {
660 145887200 : prange nonzero (r.type ());
661 145887200 : nonzero.set_nonzero (r.type ());
662 291774400 : return (r.lower_bound () == nonzero.lower_bound ()
663 289424950 : && r.upper_bound () == nonzero.upper_bound ());
664 145887200 : }
665 :
666 : // Return the prange_kind for range R, and the number of words of storage
667 : // it requires in NUM_WORDS.
668 :
669 : enum prange_kind
670 312423524 : prange_storage::prange_format (const prange &r, unsigned &num_words)
671 : {
672 312423524 : num_words = 0;
673 312423524 : if (r.undefined_p ())
674 : return PR_UNDEFINED;
675 :
676 282261439 : if (r.varying_p ())
677 : return PR_VARYING;
678 :
679 132336052 : if (r.zero_p ())
680 : return PR_ZERO;
681 :
682 131479374 : enum prange_kind kind = PR_NONZERO;
683 :
684 131479374 : if (!nonzero_range_p (r))
685 : {
686 3018325 : prange tmp (r.type ());
687 6036650 : if (r.lower_bound () == tmp.lower_bound ()
688 4401711 : && r.upper_bound () == tmp.upper_bound ())
689 : kind = PR_FULL;
690 : else
691 : {
692 : // PR_OTHER requires words of storage for the end points.
693 2802042 : kind = PR_OTHER;
694 2802042 : num_words += 2;
695 : }
696 3018325 : }
697 :
698 : // Bitmasks require 2 words of storage.
699 131479374 : if (!r.get_bitmask ().unknown_p ())
700 5257383 : num_words += 2;
701 :
702 : // PR_FULL must have a bitmask or points to, or it should be PR_VARYING.
703 131695657 : gcc_checking_assert (kind != PR_FULL || !r.get_bitmask ().unknown_p ()
704 : || r.m_pt != NULL_TREE);
705 131479374 : return kind;
706 : }
707 :
708 : void
709 104138354 : prange_storage::set_prange (const prange &r)
710 : {
711 104138354 : unsigned num_words;
712 104138354 : m_kind = prange_format (r, num_words);
713 104138354 : m_has_bitmask = !r.get_bitmask ().unknown_p ();
714 104138354 : m_pt = r.m_pt;
715 104138354 : m_points_to_p = r.m_points_to_p;
716 :
717 104138354 : unsigned index = 0;
718 :
719 104138354 : switch (m_kind)
720 : {
721 60321404 : case PR_UNDEFINED:
722 60321404 : case PR_VARYING:
723 60321404 : case PR_ZERO:
724 60321404 : return;
725 : case PR_NONZERO:
726 : case PR_FULL:
727 : break;
728 864040 : case PR_OTHER:
729 864040 : set_word (index++, r.lower_bound (), r.type ());
730 864040 : set_word (index++, r.upper_bound (), r.type ());
731 864040 : break;
732 0 : default:
733 0 : gcc_unreachable ();
734 : }
735 :
736 43816950 : if (m_has_bitmask)
737 : {
738 1760542 : irange_bitmask bm = r.m_bitmask;
739 1760542 : set_word (index++, r.m_bitmask.value (), r.type ());
740 1760542 : set_word (index++, r.m_bitmask.mask (), r.type ());
741 1760542 : }
742 43816950 : gcc_checking_assert (index == num_words);
743 : }
744 :
745 : void
746 387918370 : prange_storage::get_prange (prange &r, tree type) const
747 : {
748 387918370 : gcc_checking_assert (r.supports_type_p (type));
749 387918370 : unsigned index = 0;
750 387918370 : switch (m_kind)
751 : {
752 1035755 : case PR_UNDEFINED:
753 1035755 : r.set_undefined ();
754 1035755 : return;
755 :
756 215132901 : case PR_VARYING:
757 215132901 : r.set_varying (type);
758 215132901 : return;
759 :
760 854581 : case PR_ZERO:
761 854581 : r.set_zero (type);
762 854581 : return;
763 :
764 166858567 : case PR_NONZERO:
765 166858567 : r.set_nonzero (type);
766 166858567 : break;
767 :
768 530256 : case PR_FULL:
769 530256 : {
770 530256 : r.m_kind = VR_RANGE;
771 530256 : r.m_type = type;
772 530256 : prange tmp (type);
773 530256 : r.m_min = tmp.lower_bound ();
774 530256 : r.m_max = tmp.upper_bound ();
775 530256 : break;
776 530256 : }
777 :
778 3506310 : case PR_OTHER:
779 3506310 : {
780 3506310 : gcc_checking_assert (m_kind == PR_OTHER);
781 3506310 : r.m_kind = VR_RANGE;
782 3506310 : r.m_type = type;
783 3506310 : r.m_min = get_word (index++, type);
784 3506310 : r.m_max = get_word (index++, type);
785 3506310 : break;
786 : }
787 0 : default:
788 0 : gcc_unreachable ();
789 : }
790 :
791 170895133 : if (m_has_bitmask)
792 : {
793 17573389 : wide_int value = get_word (index++, type);
794 17573389 : wide_int mask = get_word (index++, type);
795 17573389 : r.m_bitmask = irange_bitmask (value, mask);
796 17573389 : }
797 : else
798 153321744 : r.m_bitmask.set_unknown (TYPE_PRECISION (type));
799 :
800 170895133 : r.m_points_to_p = m_points_to_p;
801 170895133 : r.m_pt = m_pt;
802 :
803 170895133 : if (flag_checking)
804 170894998 : r.verify_range ();
805 : }
806 :
807 : bool
808 14849103 : prange_storage::equal_p (const prange &r) const
809 : {
810 14849103 : if (r.undefined_p ())
811 0 : return m_kind == PR_UNDEFINED;
812 :
813 14849103 : unsigned index = 0;
814 14849103 : switch (m_kind)
815 : {
816 5612 : case PR_VARYING:
817 5612 : return r.varying_p ();
818 :
819 86926 : case PR_ZERO:
820 86926 : return r.zero_p ();
821 :
822 14407826 : case PR_NONZERO:
823 14407826 : if (!nonzero_range_p (r))
824 : return false;
825 : break;
826 :
827 300852 : case PR_FULL:
828 300852 : if (r.m_min != wi::zero (TYPE_PRECISION (r.m_type))
829 597216 : || r.m_max != wi::max_value (TYPE_PRECISION (r.m_type),
830 148182 : TYPE_SIGN (r.m_type)))
831 : return false;
832 : break;
833 :
834 47887 : case PR_OTHER:
835 95774 : if (r.m_min != get_word (index++, r.m_type)
836 76677 : || r.m_max != get_word (index++, r.m_type))
837 : return false;
838 : break;
839 :
840 0 : default:
841 0 : gcc_unreachable ();
842 : }
843 :
844 14180539 : if (m_has_bitmask)
845 : {
846 8362758 : wide_int value = get_word (index++, r.m_type);
847 8362758 : wide_int mask = get_word (index++, r.m_type);
848 8362758 : if (r.m_bitmask != irange_bitmask (value, mask))
849 4064811 : return false;
850 8362758 : }
851 : else
852 5817781 : if (!r.m_bitmask.unknown_p ())
853 : return false;
854 :
855 8516898 : if (m_pt != r.m_pt)
856 : return false;
857 : // Storage objects are only equal If they point to the same memory.
858 1505843 : if (m_points_to_p != r.m_points_to_p)
859 0 : return false;
860 :
861 : return true;
862 : }
863 :
864 : bool
865 7040892 : prange_storage::fits_p (const prange &r) const
866 : {
867 : // Undefined ranges always fit, because they don't store anything in
868 : // the trailing wide ints.
869 7040892 : if (r.undefined_p ())
870 : return true;
871 :
872 7024576 : unsigned num_words;
873 7024576 : prange_format (r, num_words);
874 7024576 : return num_words <= m_trailing_ints.num_elements ();
875 : }
876 :
877 :
878 : static vrange_allocator ggc_vrange_allocator (true);
879 :
880 0 : vrange_storage *ggc_alloc_vrange_storage (tree type)
881 : {
882 0 : return ggc_vrange_allocator.clone_varying (type);
883 : }
884 :
885 20721192 : vrange_storage *ggc_alloc_vrange_storage (const vrange &r, bool shared_p)
886 : {
887 20721192 : return ggc_vrange_allocator.clone (r, shared_p);
888 : }
|
