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 99519457 : vrange_internal_alloc () { }
40 99519445 : 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 99226091 : vrange_obstack_alloc ()
51 99226091 : {
52 99226091 : obstack_init (&m_obstack);
53 99226091 : }
54 99226079 : virtual ~vrange_obstack_alloc () final override
55 99226079 : {
56 99226079 : obstack_free (&m_obstack, NULL);
57 99226079 : }
58 426070394 : virtual void *alloc (size_t size) final override
59 : {
60 426070394 : 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 293366 : vrange_ggc_alloc () { }
71 293366 : virtual ~vrange_ggc_alloc () final override { }
72 21439282 : virtual void *alloc (size_t size) final override
73 : {
74 21439282 : 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 99519457 : vrange_allocator::vrange_allocator (bool gc)
83 : {
84 99519457 : if (gc)
85 293366 : m_alloc = new vrange_ggc_alloc;
86 : else
87 99226091 : m_alloc = new vrange_obstack_alloc;
88 99519457 : }
89 :
90 99519445 : vrange_allocator::~vrange_allocator ()
91 : {
92 99519445 : delete m_alloc;
93 99519445 : }
94 :
95 : void *
96 59616766 : vrange_allocator::alloc (size_t size)
97 : {
98 59616766 : 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 328285729 : vrange_allocator::clone (const vrange &r, bool shared_p)
112 : {
113 328285729 : return vrange_storage::alloc (*m_alloc, r, shared_p);
114 : }
115 :
116 : vrange_storage *
117 29857920 : vrange_allocator::clone_varying (tree type)
118 : {
119 29857920 : if (irange::supports_p (type))
120 19643964 : return irange_storage::alloc (*m_alloc, int_range <1> (type));
121 10213956 : if (prange::supports_p (type))
122 9730645 : return prange_storage::alloc (*m_alloc, prange (type));
123 483311 : if (frange::supports_p (type))
124 483311 : return frange_storage::alloc (*m_alloc, frange (type));
125 : return NULL;
126 : }
127 :
128 : vrange_storage *
129 29749261 : vrange_allocator::clone_undefined (tree type)
130 : {
131 29749261 : if (irange::supports_p (type))
132 19541106 : return irange_storage::alloc (*m_alloc, int_range<1> ());
133 10208155 : if (prange::supports_p (type))
134 9729016 : return prange_storage::alloc (*m_alloc, prange ());
135 479139 : if (frange::supports_p (type))
136 479139 : 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 328285729 : vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r,
145 : bool shared_p)
146 : {
147 328285729 : if (is_a <irange> (r))
148 233049186 : return irange_storage::alloc (allocator, as_a <irange> (r));
149 95236543 : if (is_a <prange> (r))
150 83193466 : return prange_storage::alloc (allocator, as_a <prange> (r), shared_p);
151 12043077 : if (is_a <frange> (r))
152 12043077 : return frange_storage::alloc (allocator, as_a <frange> (r));
153 : return NULL;
154 : }
155 :
156 : // Set storage to R.
157 :
158 : void
159 28289398 : vrange_storage::set_vrange (const vrange &r)
160 : {
161 28289398 : if (is_a <irange> (r))
162 : {
163 23885540 : irange_storage *s = static_cast <irange_storage *> (this);
164 23885540 : gcc_checking_assert (s->fits_p (as_a <irange> (r)));
165 23885540 : s->set_irange (as_a <irange> (r));
166 : }
167 4403858 : else if (is_a <prange> (r))
168 : {
169 3805313 : prange_storage *s = static_cast <prange_storage *> (this);
170 3805313 : gcc_checking_assert (s->fits_p (as_a <prange> (r)));
171 3805313 : s->set_prange (as_a <prange> (r));
172 : }
173 598545 : else if (is_a <frange> (r))
174 : {
175 598545 : frange_storage *s = static_cast <frange_storage *> (this);
176 598545 : gcc_checking_assert (s->fits_p (as_a <frange> (r)));
177 598545 : 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 28289398 : 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 28289330 : && !is_a <frange> (r)
188 55980183 : && !r.undefined_p ())
189 : {
190 27531020 : value_range tmp (r);
191 27531020 : get_vrange (tmp, r.type ());
192 27531020 : gcc_checking_assert (tmp == r);
193 27531020 : }
194 28289398 : }
195 :
196 : // Restore R from storage.
197 :
198 : void
199 1900667016 : vrange_storage::get_vrange (vrange &r, tree type) const
200 : {
201 1900667016 : if (is_a <irange> (r))
202 : {
203 1462722462 : const irange_storage *s = static_cast <const irange_storage *> (this);
204 1462722462 : s->get_irange (as_a <irange> (r), type);
205 : }
206 437944554 : else if (is_a <prange> (r))
207 : {
208 389676249 : const prange_storage *s = static_cast <const prange_storage *> (this);
209 389676249 : s->get_prange (as_a <prange> (r), type);
210 : }
211 48268305 : else if (is_a <frange> (r))
212 : {
213 48268305 : const frange_storage *s = static_cast <const frange_storage *> (this);
214 48268305 : s->get_frange (as_a <frange> (r), type);
215 : }
216 : else
217 0 : gcc_unreachable ();
218 1900667016 : }
219 :
220 : // Return TRUE if storage can fit R.
221 :
222 : bool
223 32683287 : vrange_storage::fits_p (const vrange &r) const
224 : {
225 32683287 : if (is_a <irange> (r))
226 : {
227 28199164 : const irange_storage *s = static_cast <const irange_storage *> (this);
228 28199164 : return s->fits_p (as_a <irange> (r));
229 : }
230 4484123 : if (is_a <prange> (r))
231 : {
232 3836969 : const prange_storage *s = static_cast <const prange_storage *> (this);
233 3836969 : return s->fits_p (as_a <prange> (r));
234 : }
235 647154 : if (is_a <frange> (r))
236 : {
237 647154 : const frange_storage *s = static_cast <const frange_storage *> (this);
238 647154 : 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 19183364 : vrange_storage::equal_p (const vrange &r) const
250 : {
251 19183364 : if (is_a <irange> (r))
252 : {
253 3818578 : const irange_storage *s = static_cast <const irange_storage *> (this);
254 3818578 : return s->equal_p (as_a <irange> (r));
255 : }
256 15364786 : if (is_a <prange> (r))
257 : {
258 15344387 : const prange_storage *s = static_cast <const prange_storage *> (this);
259 15344387 : return s->equal_p (as_a <prange> (r));
260 : }
261 20399 : if (is_a <frange> (r))
262 : {
263 20399 : const frange_storage *s = static_cast <const frange_storage *> (this);
264 20399 : 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 1165714010 : irange_storage::write_lengths_address ()
275 : {
276 1165714010 : return (unsigned short *)&m_val[(m_num_ranges * 2 + 2)
277 1165714010 : * WIDE_INT_MAX_HWIS (m_precision)];
278 : }
279 :
280 : const unsigned short *
281 1010454367 : irange_storage::lengths_address () const
282 : {
283 1010454367 : 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 272234256 : irange_storage::alloc (vrange_internal_alloc &allocator, const irange &r)
290 : {
291 272234256 : size_t size = irange_storage::size (r);
292 272234256 : irange_storage *p = static_cast <irange_storage *> (allocator.alloc (size));
293 272234256 : new (p) irange_storage (r);
294 272234256 : return p;
295 : }
296 :
297 : // Initialize the storage with R.
298 :
299 272234256 : irange_storage::irange_storage (const irange &r)
300 272234256 : : vrange_storage (VR_IRANGE), m_max_ranges (r.num_pairs ())
301 : {
302 272234256 : m_num_ranges = m_max_ranges;
303 272234256 : set_irange (r);
304 272234256 : }
305 :
306 : static inline void
307 744606538 : write_wide_int (HOST_WIDE_INT *&val, unsigned short *&len, const wide_int &w)
308 : {
309 744606538 : *len = w.get_len ();
310 1490569884 : for (unsigned i = 0; i < *len; ++i)
311 745963346 : *val++ = w.elt (i);
312 744606538 : ++len;
313 744606538 : }
314 :
315 : // Store R into the current storage.
316 :
317 : void
318 296119796 : irange_storage::set_irange (const irange &r)
319 : {
320 296119796 : gcc_checking_assert (fits_p (r));
321 :
322 296119796 : if (r.undefined_p ())
323 : {
324 19986118 : m_kind = VR_UNDEFINED;
325 140860153 : return;
326 : }
327 276133678 : if (r.varying_p ())
328 : {
329 120874035 : m_kind = VR_VARYING;
330 120874035 : return;
331 : }
332 :
333 155259643 : m_precision = TYPE_PRECISION (r.type ());
334 155259643 : m_num_ranges = r.num_pairs ();
335 155259643 : m_kind = VR_RANGE;
336 :
337 155259643 : HOST_WIDE_INT *val = &m_val[0];
338 155259643 : unsigned short *len = write_lengths_address ();
339 :
340 372303269 : for (unsigned i = 0; i < r.num_pairs (); ++i)
341 : {
342 217043626 : write_wide_int (val, len, r.lower_bound (i));
343 217046441 : 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 155259643 : irange_bitmask bm = r.m_bitmask;
348 155259643 : write_wide_int (val, len, bm.value ());
349 155259643 : write_wide_int (val, len, bm.mask ());
350 155259643 : }
351 :
352 : static inline void
353 4918079088 : read_wide_int (wide_int &w,
354 : const HOST_WIDE_INT *val, unsigned short len, unsigned prec)
355 : {
356 4918079088 : trailing_wide_int_storage stow (prec, &len,
357 1218783758 : const_cast <HOST_WIDE_INT *> (val));
358 3699295330 : w = trailing_wide_int (stow);
359 : }
360 :
361 : // Restore a range of TYPE from storage into R.
362 :
363 : void
364 1466090583 : irange_storage::get_irange (irange &r, tree type) const
365 : {
366 1466090583 : if (m_kind == VR_UNDEFINED)
367 : {
368 10120850 : r.set_undefined ();
369 465757066 : return;
370 : }
371 1455969733 : if (m_kind == VR_VARYING)
372 : {
373 445515366 : r.set_varying (type);
374 445515366 : return;
375 : }
376 :
377 1010454367 : gcc_checking_assert (TYPE_PRECISION (type) == m_precision);
378 1010454367 : const HOST_WIDE_INT *val = &m_val[0];
379 1010454367 : const unsigned short *len = lengths_address ();
380 :
381 : // Handle the common case where R can fit the new range.
382 1010454367 : if (r.m_max_ranges >= m_num_ranges)
383 : {
384 975639806 : r.m_kind = VR_RANGE;
385 975639806 : r.m_num_ranges = m_num_ranges;
386 975639806 : r.m_type = type;
387 3456151378 : for (unsigned i = 0; i < m_num_ranges * 2; ++i)
388 : {
389 2480511572 : read_wide_int (r.m_base[i], val, *len, m_precision);
390 2480511572 : val += *len++;
391 : }
392 : }
393 : // Otherwise build the range piecewise.
394 : else
395 : {
396 34814561 : r.set_undefined ();
397 277958513 : for (unsigned i = 0; i < m_num_ranges; ++i)
398 : {
399 208329391 : wide_int lb, ub;
400 208329391 : read_wide_int (lb, val, *len, m_precision);
401 208329391 : val += *len++;
402 208329391 : read_wide_int (ub, val, *len, m_precision);
403 208329391 : val += *len++;
404 208329391 : int_range<1> tmp (type, lb, ub);
405 208329391 : r.union_ (tmp);
406 208920083 : }
407 : }
408 :
409 1010454367 : wide_int bits_value, bits_mask;
410 1010454367 : read_wide_int (bits_value, val, *len, m_precision);
411 1010454367 : val += *len++;
412 1010454367 : read_wide_int (bits_mask, val, *len, m_precision);
413 1010454367 : r.m_bitmask = irange_bitmask (bits_value, bits_mask);
414 1010454367 : if (r.m_kind == VR_VARYING)
415 0 : r.m_kind = VR_RANGE;
416 :
417 1010454367 : if (flag_checking)
418 1010450963 : r.verify_range ();
419 1010527602 : }
420 :
421 : bool
422 3818578 : irange_storage::equal_p (const irange &r) const
423 : {
424 3818578 : if (m_kind == VR_UNDEFINED || r.undefined_p ())
425 0 : return m_kind == r.m_kind;
426 3818578 : if (m_kind == VR_VARYING || r.varying_p ())
427 450457 : 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 3368121 : int_range_max tmp;
432 3368121 : get_irange (tmp, r.type ());
433 3368121 : return tmp == r;
434 3368121 : }
435 :
436 : // Return the size in bytes to allocate storage that can hold R.
437 :
438 : size_t
439 272234256 : irange_storage::size (const irange &r)
440 : {
441 272234256 : if (r.undefined_p ())
442 : return sizeof (irange_storage);
443 :
444 252399547 : unsigned prec = TYPE_PRECISION (r.type ());
445 252399547 : unsigned n = r.num_pairs () * 2 + 2;
446 252399547 : unsigned hwi_size = ((n * WIDE_INT_MAX_HWIS (prec) - 1)
447 : * sizeof (HOST_WIDE_INT));
448 252399547 : unsigned len_size = n * sizeof (unsigned short);
449 252399547 : return sizeof (irange_storage) + hwi_size + len_size;
450 : }
451 :
452 : // Return TRUE if R fits in the current storage.
453 :
454 : bool
455 348204500 : irange_storage::fits_p (const irange &r) const
456 : {
457 348204500 : 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 13005527 : frange_storage::size (const frange &r)
513 : {
514 13005527 : 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 13005527 : frange_storage::alloc (vrange_internal_alloc &allocator, const frange &r)
521 : {
522 13005527 : frange_storage *p
523 13005527 : = static_cast <frange_storage *> (allocator.alloc (size (r)));
524 13005527 : new (p) frange_storage (r);
525 13005527 : return p;
526 : }
527 :
528 13005527 : frange_storage::frange_storage (const frange &r)
529 13005527 : : vrange_storage (VR_FRANGE), m_max_ranges (r.num_pairs ())
530 : {
531 13005527 : set_frange (r);
532 13005527 : }
533 :
534 : void
535 13604072 : frange_storage::set_frange (const frange &r)
536 : {
537 13604072 : gcc_checking_assert (fits_p (r));
538 :
539 13604072 : m_kind = r.m_kind;
540 13604072 : m_num_ranges = r.m_num_ranges;
541 27698728 : for (unsigned i = 0; i < r.m_num_ranges; ++i)
542 14094656 : m_pairs[i] = r.m_pairs[i];
543 13604072 : m_pos_nan = r.m_pos_nan;
544 13604072 : m_neg_nan = r.m_neg_nan;
545 13604072 : }
546 :
547 : void
548 48288704 : frange_storage::get_frange (frange &r, tree type) const
549 : {
550 48288704 : gcc_checking_assert (r.supports_type_p (type));
551 :
552 : // Handle explicit NANs.
553 48288704 : if (m_kind == VR_NAN)
554 : {
555 113687 : if (HONOR_NANS (type))
556 : {
557 113687 : if (m_pos_nan && m_neg_nan)
558 107671 : r.set_nan (type);
559 : else
560 6016 : r.set_nan (type, m_neg_nan);
561 : }
562 : else
563 0 : r.set_undefined ();
564 : return;
565 : }
566 48175017 : if (m_kind == VR_UNDEFINED)
567 : {
568 62120 : r.set_undefined ();
569 62120 : return;
570 : }
571 48112897 : if (m_kind == VR_VARYING)
572 : {
573 33889379 : r.set_varying (type);
574 33889379 : return;
575 : }
576 :
577 : // Rebuild piecewise, like irange_storage::get_irange().
578 14223518 : r.set_undefined ();
579 44299150 : for (unsigned i = 0; i < m_num_ranges; ++i)
580 : {
581 15852114 : frange tmp (type, m_pairs[i].min, m_pairs[i].max, m_kind);
582 15852114 : r.union_ (tmp);
583 15852114 : }
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 14223518 : if (HONOR_NANS (type) && (m_pos_nan ^ m_neg_nan) == 1)
588 1367909 : r.update_nan (m_neg_nan);
589 12855609 : else if (!m_pos_nan && !m_neg_nan)
590 10350898 : r.clear_nan ();
591 : }
592 :
593 : bool
594 20399 : frange_storage::equal_p (const frange &r) const
595 : {
596 20399 : if (r.undefined_p ())
597 0 : return m_kind == VR_UNDEFINED;
598 :
599 20399 : frange tmp;
600 20399 : get_frange (tmp, r.type ());
601 20399 : return tmp == r;
602 20399 : }
603 :
604 : bool
605 14849771 : frange_storage::fits_p (const frange &r) const
606 : {
607 14849771 : return m_max_ranges >= r.num_pairs ();
608 : }
609 :
610 : //============================================================================
611 : // prange_storage implementation
612 : //============================================================================
613 :
614 : prange_storage *
615 102653127 : prange_storage::alloc (vrange_internal_alloc &allocator, const prange &r,
616 : bool shared_p)
617 : {
618 102653127 : unsigned num_words;
619 102653127 : prange_format (r, num_words);
620 102653127 : size_t extra_size = 0;
621 102653127 : if (num_words)
622 : {
623 2432684 : unsigned short precision = TYPE_PRECISION (r.type ());
624 2432684 : extra_size = trailing_wide_ints<PRANGE_STORAGE_NINTS>
625 2432684 : ::extra_size (precision, num_words);
626 : }
627 :
628 102653127 : size_t size = sizeof (prange_storage) + extra_size;
629 102653127 : prange_storage *p = static_cast <prange_storage *> (allocator.alloc (size));
630 102653127 : new (p) prange_storage (r);
631 102653127 : if (p->m_pt && !shared_p)
632 2093333 : p->m_pt = unshare_expr_without_location (p->m_pt);
633 :
634 102653127 : return p;
635 : }
636 :
637 : // Initialize the storage with R.
638 :
639 102653127 : prange_storage::prange_storage (const prange &r) : vrange_storage (VR_PRANGE)
640 : {
641 102653127 : unsigned num_words;
642 102653127 : enum prange_kind kind = prange_format (r, num_words);
643 102653127 : unsigned short prec = (kind == PR_UNDEFINED) ? 0 : TYPE_PRECISION (r.type ());
644 102653127 : m_trailing_ints.set_precision (prec, num_words);
645 102653127 : set_prange (r);
646 102653127 : }
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 149268226 : nonzero_range_p (const prange &r)
658 : {
659 149268226 : prange nonzero (r.type ());
660 149268226 : nonzero.set_nonzero (r.type ());
661 298536452 : return (r.lower_bound () == nonzero.lower_bound ()
662 296089659 : && r.upper_bound () == nonzero.upper_bound ());
663 149268226 : }
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 319390240 : prange_storage::prange_format (const prange &r, unsigned &num_words)
670 : {
671 319390240 : num_words = 0;
672 319390240 : if (r.undefined_p ())
673 : return PR_UNDEFINED;
674 :
675 290058198 : if (r.varying_p ())
676 : return PR_VARYING;
677 :
678 135451125 : if (r.zero_p ())
679 : return PR_ZERO;
680 :
681 134358437 : enum prange_kind kind = PR_NONZERO;
682 :
683 134358437 : if (!nonzero_range_p (r))
684 : {
685 3146528 : prange tmp (r.type ());
686 6293056 : if (r.lower_bound () == tmp.lower_bound ()
687 4550594 : && 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 2928577 : kind = PR_OTHER;
693 2928577 : num_words += 2;
694 : }
695 3146528 : }
696 :
697 : // Bitmasks require 2 words of storage.
698 134358437 : if (!r.get_bitmask ().unknown_p ())
699 5403549 : num_words += 2;
700 :
701 : // PR_FULL must have a bitmask or points to, or it should be PR_VARYING.
702 134576388 : gcc_checking_assert (kind != PR_FULL || !r.get_bitmask ().unknown_p ()
703 : || r.m_pt != NULL_TREE);
704 134358437 : return kind;
705 : }
706 :
707 : void
708 106458440 : prange_storage::set_prange (const prange &r)
709 : {
710 106458440 : unsigned num_words;
711 106458440 : m_kind = prange_format (r, num_words);
712 106458440 : m_has_bitmask = false;
713 106458440 : m_points_to_p = false;
714 106458440 : m_pt = r.m_pt;
715 :
716 106458440 : unsigned index = 0;
717 :
718 106458440 : switch (m_kind)
719 : {
720 61684107 : case PR_UNDEFINED:
721 61684107 : case PR_VARYING:
722 61684107 : case PR_ZERO:
723 61684107 : return;
724 : case PR_NONZERO:
725 : case PR_FULL:
726 : break;
727 903893 : case PR_OTHER:
728 903893 : set_word (index++, r.lower_bound (), r.type ());
729 903893 : set_word (index++, r.upper_bound (), r.type ());
730 903893 : break;
731 0 : default:
732 0 : gcc_unreachable ();
733 : }
734 :
735 44774333 : m_has_bitmask = !r.get_bitmask ().unknown_p ();
736 44774333 : m_points_to_p = r.m_points_to_p;
737 :
738 44774333 : if (m_has_bitmask)
739 : {
740 1807880 : irange_bitmask bm = r.m_bitmask;
741 1807880 : set_word (index++, r.m_bitmask.value (), r.type ());
742 1807880 : set_word (index++, r.m_bitmask.mask (), r.type ());
743 1807880 : }
744 44774333 : gcc_checking_assert (index == num_words);
745 : }
746 :
747 : void
748 389676249 : prange_storage::get_prange (prange &r, tree type) const
749 : {
750 389676249 : gcc_checking_assert (r.supports_type_p (type));
751 389676249 : unsigned index = 0;
752 389676249 : switch (m_kind)
753 : {
754 971806 : case PR_UNDEFINED:
755 971806 : r.set_undefined ();
756 971806 : return;
757 :
758 219204324 : case PR_VARYING:
759 219204324 : r.set_varying (type);
760 219204324 : return;
761 :
762 641921 : case PR_ZERO:
763 641921 : r.set_zero (type);
764 641921 : return;
765 :
766 165145379 : case PR_NONZERO:
767 165145379 : r.set_nonzero (type);
768 165145379 : break;
769 :
770 526208 : case PR_FULL:
771 526208 : {
772 526208 : r.m_kind = VR_RANGE;
773 526208 : r.m_type = type;
774 526208 : prange tmp (type);
775 526208 : r.m_min = tmp.lower_bound ();
776 526208 : r.m_max = tmp.upper_bound ();
777 526208 : break;
778 526208 : }
779 :
780 3186611 : case PR_OTHER:
781 3186611 : {
782 3186611 : gcc_checking_assert (m_kind == PR_OTHER);
783 3186611 : r.m_kind = VR_RANGE;
784 3186611 : r.m_type = type;
785 3186611 : r.m_min = get_word (index++, type);
786 3186611 : r.m_max = get_word (index++, type);
787 3186611 : break;
788 : }
789 0 : default:
790 0 : gcc_unreachable ();
791 : }
792 :
793 168858198 : if (m_has_bitmask)
794 : {
795 18171683 : wide_int value = get_word (index++, type);
796 18171683 : wide_int mask = get_word (index++, type);
797 18171683 : r.m_bitmask = irange_bitmask (value, mask);
798 18171683 : }
799 : else
800 150686515 : r.m_bitmask.set_unknown (TYPE_PRECISION (type));
801 :
802 168858198 : r.m_points_to_p = m_points_to_p;
803 168858198 : r.m_pt = m_pt;
804 :
805 168858198 : if (flag_checking)
806 168858072 : r.verify_range ();
807 : }
808 :
809 : bool
810 15344387 : prange_storage::equal_p (const prange &r) const
811 : {
812 15344387 : if (r.undefined_p ())
813 0 : return m_kind == PR_UNDEFINED;
814 :
815 15344387 : unsigned index = 0;
816 15344387 : switch (m_kind)
817 : {
818 6494 : case PR_VARYING:
819 6494 : return r.varying_p ();
820 :
821 87002 : case PR_ZERO:
822 87002 : return r.zero_p ();
823 :
824 14909789 : case PR_NONZERO:
825 14909789 : if (!nonzero_range_p (r))
826 : return false;
827 : break;
828 :
829 297111 : case PR_FULL:
830 297111 : if (r.m_min != wi::zero (TYPE_PRECISION (r.m_type))
831 595147 : || r.m_max != wi::max_value (TYPE_PRECISION (r.m_type),
832 149018 : TYPE_SIGN (r.m_type)))
833 : return false;
834 : break;
835 :
836 43991 : case PR_OTHER:
837 87982 : if (r.m_min != get_word (index++, r.m_type)
838 73862 : || 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 14673328 : if (m_has_bitmask)
847 : {
848 8755824 : wide_int value = get_word (index++, r.m_type);
849 8755824 : wide_int mask = get_word (index++, r.m_type);
850 8755824 : if (r.m_bitmask != irange_bitmask (value, mask))
851 4267482 : return false;
852 8755824 : }
853 : else
854 5917504 : if (!r.m_bitmask.unknown_p ())
855 : return false;
856 :
857 8769853 : if (m_pt != r.m_pt)
858 : return false;
859 : // Storage objects are only equal If they point to the same memory.
860 1539539 : if (m_points_to_p != r.m_points_to_p)
861 0 : return false;
862 :
863 : return true;
864 : }
865 :
866 : bool
867 7642282 : 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 7642282 : if (r.undefined_p ())
872 : return true;
873 :
874 7625546 : unsigned num_words;
875 7625546 : prange_format (r, num_words);
876 7625546 : 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 21439282 : vrange_storage *ggc_alloc_vrange_storage (const vrange &r, bool shared_p)
888 : {
889 21439282 : return ggc_vrange_allocator.clone (r, shared_p);
890 : }
|
