1	/* Support routines for value ranges.
2	Copyright (C) 2019-2023 Free Software Foundation, Inc.
3	Contributed by Aldy Hernandez <aldyh@redhat.com> and
4	Andrew Macleod <amacleod@redhat.com>.
5
6	This file is part of GCC.
7
8	GCC is free software; you can redistribute it and/or modify
9	it under the terms of the GNU General Public License as published by
10	the Free Software Foundation; either version 3, or (at your option)
11	any later version.
12
13	GCC is distributed in the hope that it will be useful,
14	but WITHOUT ANY WARRANTY; without even the implied warranty of
15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16	GNU General Public License for more details.
17
18	You should have received a copy of the GNU General Public License
19	along with GCC; see the file COPYING3. If not see
20	<http://www.gnu.org/licenses/>. */
21
22	#ifndef GCC_VALUE_RANGE_H
23	#define GCC_VALUE_RANGE_H
24
25	class irange;
26
27	// Types of value ranges.
28	enum value_range_kind
29	{
30	/* Empty range. */
31	VR_UNDEFINED,
32	/* Range spans the entire domain. */
33	VR_VARYING,
34	/* Range is [MIN, MAX]. */
35	VR_RANGE,
36	/* Range is ~[MIN, MAX]. */
37	VR_ANTI_RANGE,
38	/* Range is a NAN. */
39	VR_NAN,
40	/* Range is a nice guy. */
41	VR_LAST
42	};
43
44	// Discriminator between different vrange types.
45
46	enum value_range_discriminator
47	{
48	// Range holds an integer or pointer.
49	VR_IRANGE,
50	// Floating point range.
51	VR_FRANGE,
52	// Range holds an unsupported type.
53	VR_UNKNOWN
54	};
55
56	// Abstract class for ranges of any of the supported types.
57	//
58	// To query what types ranger and the entire ecosystem can support,
59	// use Value_Range::supports_type_p(tree type). This is a static
60	// method available independently of any vrange object.
61	//
62	// To query what a given vrange variant can support, use:
63	// irange::supports_p ()
64	// frange::supports_p ()
65	// etc
66	//
67	// To query what a range object can support, use:
68	// void foo (vrange &v, irange &i, frange &f)
69	// {
70	// if (v.supports_type_p (type)) ...
71	// if (i.supports_type_p (type)) ...
72	// if (f.supports_type_p (type)) ...
73	// }
74
75	class GTY((user)) vrange
76	{
77	template <typename T> friend bool is_a (vrange &);
78	friend class Value_Range;
79	friend void streamer_write_vrange (struct output_block *, const vrange &);
80	friend class range_op_handler;
81	public:
82	virtual void accept (const class vrange_visitor &v) const = 0;
83	virtual void set (tree, tree, value_range_kind = VR_RANGE);
84	virtual tree type () const;
85	virtual bool supports_type_p (const_tree type) const;
86	virtual void set_varying (tree type);
87	virtual void set_undefined ();
88	virtual bool union_ (const vrange &);
89	virtual bool intersect (const vrange &);
90	virtual bool singleton_p (tree *result = NULL) const;
91	virtual bool contains_p (tree cst) const;
92	virtual bool zero_p () const;
93	virtual bool nonzero_p () const;
94	virtual void set_nonzero (tree type);
95	virtual void set_zero (tree type);
96	virtual void set_nonnegative (tree type);
97	virtual bool fits_p (const vrange &r) const;
98
99	bool varying_p () const;
100	bool undefined_p () const;
101	vrange& operator= (const vrange &);
102	bool operator== (const vrange &) const;
103	bool operator!= (const vrange &r) const { return !(*this == r); }
104	void dump (FILE *) const;
105	protected:
106	vrange (enum value_range_discriminator d) : m_discriminator (d) { }
107	ENUM_BITFIELD(value_range_kind) m_kind : 8;
108	const ENUM_BITFIELD(value_range_discriminator) m_discriminator : 4;
109	};
110
111	namespace inchash
112	{
113	extern void add_vrange (const vrange &, hash &, unsigned flags = 0);
114	}
115
116	// A pair of values representing the known bits in a range. Zero bits
117	// in MASK cover constant values. Set bits in MASK cover unknown
118	// values. VALUE are the known bits.
119	//
120	// Set bits in MASK (no meaningful information) must have their
121	// corresponding bits in VALUE cleared, as this speeds up union and
122	// intersect.
123
124	class irange_bitmask
125	{
126	public:
127	irange_bitmask () { /* uninitialized */ }
128	irange_bitmask (unsigned prec) { set_unknown (prec); }
129	irange_bitmask (const wide_int &value, const wide_int &mask);
130	wide_int value () const { return m_value; }
131	wide_int mask () const { return m_mask; }
132	void set_unknown (unsigned prec);
133	bool unknown_p () const;
134	unsigned get_precision () const;
135	bool union_ (const irange_bitmask &src);
136	bool intersect (const irange_bitmask &src);
137	bool operator== (const irange_bitmask &src) const;
138	bool operator!= (const irange_bitmask &src) const { return !(*this == src); }
139	void verify_mask () const;
140	void dump (FILE *) const;
141
142	bool member_p (const wide_int &val) const;
143	void adjust_range (irange &r) const;
144
145	// Convenience functions for nonzero bitmask compatibility.
146	wide_int get_nonzero_bits () const;
147	void set_nonzero_bits (const wide_int &bits);
148	private:
149	wide_int m_value;
150	wide_int m_mask;
151	};
152
153	inline void
154	irange_bitmask::set_unknown (unsigned prec)
155	{
156	m_value = wi::zero (precision: prec);
157	m_mask = wi::minus_one (precision: prec);
158	if (flag_checking)
159	verify_mask ();
160	}
161
162	// Return TRUE if THIS does not have any meaningful information.
163
164	inline bool
165	irange_bitmask::unknown_p () const
166	{
167	return m_mask == -1;
168	}
169
170	inline
171	irange_bitmask::irange_bitmask (const wide_int &value, const wide_int &mask)
172	{
173	m_value = value;
174	m_mask = mask;
175	if (flag_checking)
176	verify_mask ();
177	}
178
179	inline unsigned
180	irange_bitmask::get_precision () const
181	{
182	return m_mask.get_precision ();
183	}
184
185	// The following two functions are meant for backwards compatability
186	// with the nonzero bitmask. A cleared bit means the value must be 0.
187	// A set bit means we have no information for the bit.
188
189	// Return the nonzero bits.
190	inline wide_int
191	irange_bitmask::get_nonzero_bits () const
192	{
193	return m_value | m_mask;
194	}
195
196	// Set the bitmask to the nonzero bits in BITS.
197	inline void
198	irange_bitmask::set_nonzero_bits (const wide_int &bits)
199	{
200	m_value = wi::zero (precision: bits.get_precision ());
201	m_mask = bits;
202	if (flag_checking)
203	verify_mask ();
204	}
205
206	// Return TRUE if val could be a valid value with this bitmask.
207
208	inline bool
209	irange_bitmask::member_p (const wide_int &val) const
210	{
211	if (unknown_p ())
212	return true;
213	wide_int res = m_mask & val;
214	if (m_value != 0)
215	res |= ~m_mask & m_value;
216	return res == val;
217	}
218
219	inline bool
220	irange_bitmask::operator== (const irange_bitmask &src) const
221	{
222	bool unknown1 = unknown_p ();
223	bool unknown2 = src.unknown_p ();
224	if (unknown1 || unknown2)
225	return unknown1 == unknown2;
226	return m_value == src.m_value && m_mask == src.m_mask;
227	}
228
229	inline bool
230	irange_bitmask::union_ (const irange_bitmask &orig_src)
231	{
232	// Normalize mask.
233	irange_bitmask src (orig_src.m_value & ~orig_src.m_mask, orig_src.m_mask);
234	m_value &= ~m_mask;
235
236	irange_bitmask save (*this);
237	m_mask = (m_mask | src.m_mask) | (m_value ^ src.m_value);
238	m_value = m_value & src.m_value;
239	if (flag_checking)
240	verify_mask ();
241	return *this != save;
242	}
243
244	inline bool
245	irange_bitmask::intersect (const irange_bitmask &orig_src)
246	{
247	// Normalize mask.
248	irange_bitmask src (orig_src.m_value & ~orig_src.m_mask, orig_src.m_mask);
249	m_value &= ~m_mask;
250
251	irange_bitmask save (*this);
252	// If we have two known bits that are incompatible, the resulting
253	// bit is undefined. It is unclear whether we should set the entire
254	// range to UNDEFINED, or just a subset of it. For now, set the
255	// entire bitmask to unknown (VARYING).
256	if (wi::bit_and (x: ~(m_mask | src.m_mask),
257	y: m_value ^ src.m_value) != 0)
258	{
259	unsigned prec = m_mask.get_precision ();
260	m_mask = wi::minus_one (precision: prec);
261	m_value = wi::zero (precision: prec);
262	}
263	else
264	{
265	m_mask = m_mask & src.m_mask;
266	m_value = m_value | src.m_value;
267	}
268	if (flag_checking)
269	verify_mask ();
270	return *this != save;
271	}
272
273	// An integer range without any storage.
274
275	class GTY((user)) irange : public vrange
276	{
277	friend value_range_kind get_legacy_range (const irange &, tree &, tree &);
278	friend class irange_storage;
279	friend class vrange_printer;
280	public:
281	// In-place setters.
282	void set (tree type, const wide_int &, const wide_int &,
283	value_range_kind = VR_RANGE);
284	virtual void set_nonzero (tree type) override;
285	virtual void set_zero (tree type) override;
286	virtual void set_nonnegative (tree type) override;
287	virtual void set_varying (tree type) override;
288	virtual void set_undefined () override;
289
290	// Range types.
291	static bool supports_p (const_tree type);
292	virtual bool supports_type_p (const_tree type) const override;
293	virtual tree type () const override;
294
295	// Iteration over sub-ranges.
296	unsigned num_pairs () const;
297	wide_int lower_bound (unsigned = 0) const;
298	wide_int upper_bound (unsigned) const;
299	wide_int upper_bound () const;
300
301	// Predicates.
302	virtual bool zero_p () const override;
303	virtual bool nonzero_p () const override;
304	virtual bool singleton_p (tree *result = NULL) const override;
305	bool singleton_p (wide_int &) const;
306	bool contains_p (const wide_int &) const;
307	bool nonnegative_p () const;
308	bool nonpositive_p () const;
309
310	// In-place operators.
311	virtual bool union_ (const vrange &) override;
312	virtual bool intersect (const vrange &) override;
313	void invert ();
314
315	// Operator overloads.
316	irange& operator= (const irange &);
317	bool operator== (const irange &) const;
318	bool operator!= (const irange &r) const { return !(*this == r); }
319
320	// Misc methods.
321	virtual bool fits_p (const vrange &r) const override;
322	virtual void accept (const vrange_visitor &v) const override;
323
324	void update_bitmask (const irange_bitmask &);
325	irange_bitmask get_bitmask () const;
326	// Nonzero masks.
327	wide_int get_nonzero_bits () const;
328	void set_nonzero_bits (const wide_int &bits);
329
330	protected:
331	void maybe_resize (int needed);
332	virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
333	virtual bool contains_p (tree cst) const override;
334	irange (wide_int *, unsigned nranges, bool resizable);
335
336	// In-place operators.
337	bool irange_contains_p (const irange &) const;
338	bool irange_single_pair_union (const irange &r);
339
340	void normalize_kind ();
341
342	void verify_range ();
343
344	// Hard limit on max ranges allowed.
345	static const int HARD_MAX_RANGES = 255;
346	private:
347	friend void gt_ggc_mx (irange *);
348	friend void gt_pch_nx (irange *);
349	friend void gt_pch_nx (irange *, gt_pointer_operator, void *);
350
351	bool varying_compatible_p () const;
352	bool intersect_bitmask (const irange &r);
353	bool union_bitmask (const irange &r);
354	irange_bitmask get_bitmask_from_range () const;
355	bool set_range_from_bitmask ();
356
357	bool intersect (const wide_int& lb, const wide_int& ub);
358	bool union_append (const irange &r);
359	unsigned char m_num_ranges;
360	bool m_resizable;
361	unsigned char m_max_ranges;
362	tree m_type;
363	irange_bitmask m_bitmask;
364	protected:
365	wide_int *m_base;
366	};
367
368	// Here we describe an irange with N pairs of ranges. The storage for
369	// the pairs is embedded in the class as an array.
370	//
371	// If RESIZABLE is true, the storage will be resized on the heap when
372	// the number of ranges needed goes past N up to a max of
373	// HARD_MAX_RANGES. This new storage is freed upon destruction.
374
375	template<unsigned N, bool RESIZABLE = false>
376	class GTY((user)) int_range : public irange
377	{
378	public:
379	int_range ();
380	int_range (tree type, const wide_int &, const wide_int &,
381	value_range_kind = VR_RANGE);
382	int_range (tree type);
383	int_range (const int_range &);
384	int_range (const irange &);
385	virtual ~int_range ();
386	int_range& operator= (const int_range &);
387	protected:
388	int_range (tree, tree, value_range_kind = VR_RANGE);
389	private:
390	wide_int m_ranges[N*2];
391	};
392
393	// Unsupported temporaries may be created by ranger before it's known
394	// they're unsupported, or by vr_values::get_value_range.
395
396	class unsupported_range : public vrange
397	{
398	public:
399	unsupported_range ()
400	: vrange (VR_UNKNOWN)
401	{
402	set_undefined ();
403	}
404	virtual void set_undefined () final override
405	{
406	m_kind = VR_UNDEFINED;
407	}
408	virtual void accept (const vrange_visitor &v) const override;
409	};
410
411	// The NAN state as an opaque object.
412
413	class nan_state
414	{
415	public:
416	nan_state (bool);
417	nan_state (bool pos_nan, bool neg_nan);
418	bool neg_p () const;
419	bool pos_p () const;
420	private:
421	bool m_pos_nan;
422	bool m_neg_nan;
423	};
424
425	// Set NAN state to +-NAN if NAN_P is true. Otherwise set NAN state
426	// to false.
427
428	inline
429	nan_state::nan_state (bool nan_p)
430	{
431	m_pos_nan = nan_p;
432	m_neg_nan = nan_p;
433	}
434
435	// Constructor initializing the object to +NAN if POS_NAN is set, -NAN
436	// if NEG_NAN is set, or +-NAN if both are set. Otherwise POS_NAN and
437	// NEG_NAN are clear, and the object cannot be a NAN.
438
439	inline
440	nan_state::nan_state (bool pos_nan, bool neg_nan)
441	{
442	m_pos_nan = pos_nan;
443	m_neg_nan = neg_nan;
444	}
445
446	// Return if +NAN is possible.
447
448	inline bool
449	nan_state::pos_p () const
450	{
451	return m_pos_nan;
452	}
453
454	// Return if -NAN is possible.
455
456	inline bool
457	nan_state::neg_p () const
458	{
459	return m_neg_nan;
460	}
461
462	// A floating point range.
463	//
464	// The representation is a type with a couple of endpoints, unioned
465	// with the set of { -NAN, +Nan }.
466
467	class GTY((user)) frange : public vrange
468	{
469	friend class frange_storage;
470	friend class vrange_printer;
471	friend void gt_ggc_mx (frange *);
472	friend void gt_pch_nx (frange *);
473	friend void gt_pch_nx (frange *, gt_pointer_operator, void *);
474	public:
475	frange ();
476	frange (const frange &);
477	frange (tree, tree, value_range_kind = VR_RANGE);
478	frange (tree type);
479	frange (tree type, const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
480	value_range_kind = VR_RANGE);
481	static bool supports_p (const_tree type)
482	{
483	// ?? Decimal floats can have multiple representations for the
484	// same number. Supporting them may be as simple as just
485	// disabling them in singleton_p. No clue.
486	return SCALAR_FLOAT_TYPE_P (type) && !DECIMAL_FLOAT_TYPE_P (type);
487	}
488	virtual tree type () const override;
489	void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
490	value_range_kind = VR_RANGE);
491	void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
492	const nan_state &, value_range_kind = VR_RANGE);
493	void set_nan (tree type);
494	void set_nan (tree type, bool sign);
495	void set_nan (tree type, const nan_state &);
496	virtual void set_varying (tree type) override;
497	virtual void set_undefined () override;
498	virtual bool union_ (const vrange &) override;
499	virtual bool intersect (const vrange &) override;
500	bool contains_p (const REAL_VALUE_TYPE &) const;
501	virtual bool singleton_p (tree *result = NULL) const override;
502	bool singleton_p (REAL_VALUE_TYPE &r) const;
503	virtual bool supports_type_p (const_tree type) const override;
504	virtual void accept (const vrange_visitor &v) const override;
505	virtual bool zero_p () const override;
506	virtual bool nonzero_p () const override;
507	virtual void set_nonzero (tree type) override;
508	virtual void set_zero (tree type) override;
509	virtual void set_nonnegative (tree type) override;
510	frange& operator= (const frange &);
511	bool operator== (const frange &) const;
512	bool operator!= (const frange &r) const { return !(*this == r); }
513	const REAL_VALUE_TYPE &lower_bound () const;
514	const REAL_VALUE_TYPE &upper_bound () const;
515	nan_state get_nan_state () const;
516	void update_nan ();
517	void update_nan (bool sign);
518	void update_nan (tree) = delete; // Disallow silent conversion to bool.
519	void update_nan (const nan_state &);
520	void clear_nan ();
521	void flush_denormals_to_zero ();
522
523	// fpclassify like API
524	bool known_isfinite () const;
525	bool known_isnan () const;
526	bool known_isinf () const;
527	bool maybe_isnan () const;
528	bool maybe_isnan (bool sign) const;
529	bool maybe_isinf () const;
530	bool signbit_p (bool &signbit) const;
531	bool nan_signbit_p (bool &signbit) const;
532
533	protected:
534	virtual bool contains_p (tree cst) const override;
535	virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
536
537	private:
538	bool internal_singleton_p (REAL_VALUE_TYPE * = NULL) const;
539	void verify_range ();
540	bool normalize_kind ();
541	bool union_nans (const frange &);
542	bool intersect_nans (const frange &);
543	bool combine_zeros (const frange &, bool union_p);
544
545	tree m_type;
546	REAL_VALUE_TYPE m_min;
547	REAL_VALUE_TYPE m_max;
548	bool m_pos_nan;
549	bool m_neg_nan;
550	};
551
552	inline const REAL_VALUE_TYPE &
553	frange::lower_bound () const
554	{
555	gcc_checking_assert (!undefined_p () && !known_isnan ());
556	return m_min;
557	}
558
559	inline const REAL_VALUE_TYPE &
560	frange::upper_bound () const
561	{
562	gcc_checking_assert (!undefined_p () && !known_isnan ());
563	return m_max;
564	}
565
566	// Return the NAN state.
567
568	inline nan_state
569	frange::get_nan_state () const
570	{
571	return nan_state (m_pos_nan, m_neg_nan);
572	}
573
574	// is_a<> and as_a<> implementation for vrange.
575
576	// Anything we haven't specialized is a hard fail.
577	template <typename T>
578	inline bool
579	is_a (vrange &)
580	{
581	gcc_unreachable ();
582	return false;
583	}
584
585	template <typename T>
586	inline bool
587	is_a (const vrange &v)
588	{
589	// Reuse is_a <vrange> to implement the const version.
590	const T &derived = static_cast<const T &> (v);
591	return is_a <T> (const_cast<T &> (derived));
592	}
593
594	template <typename T>
595	inline T &
596	as_a (vrange &v)
597	{
598	gcc_checking_assert (is_a <T> (v));
599	return static_cast <T &> (v);
600	}
601
602	template <typename T>
603	inline const T &
604	as_a (const vrange &v)
605	{
606	gcc_checking_assert (is_a <T> (v));
607	return static_cast <const T &> (v);
608	}
609
610	// Specializations for the different range types.
611
612	template <>
613	inline bool
614	is_a <irange> (vrange &v)
615	{
616	return v.m_discriminator == VR_IRANGE;
617	}
618
619	template <>
620	inline bool
621	is_a <frange> (vrange &v)
622	{
623	return v.m_discriminator == VR_FRANGE;
624	}
625
626	template <>
627	inline bool
628	is_a <unsupported_range> (vrange &v)
629	{
630	return v.m_discriminator == VR_UNKNOWN;
631	}
632
633	// For resizable ranges, resize the range up to HARD_MAX_RANGES if the
634	// NEEDED pairs is greater than the current capacity of the range.
635
636	inline void
637	irange::maybe_resize (int needed)
638	{
639	if (!m_resizable || m_max_ranges == HARD_MAX_RANGES)
640	return;
641
642	if (needed > m_max_ranges)
643	{
644	m_max_ranges = HARD_MAX_RANGES;
645	wide_int *newmem = new wide_int[m_max_ranges * 2];
646	unsigned n = num_pairs () * 2;
647	for (unsigned i = 0; i < n; ++i)
648	newmem[i] = m_base[i];
649	m_base = newmem;
650	}
651	}
652
653	template<unsigned N, bool RESIZABLE>
654	inline
655	int_range<N, RESIZABLE>::~int_range ()
656	{
657	if (RESIZABLE && m_base != m_ranges)
658	delete[] m_base;
659	}
660
661	// This is an "infinite" precision irange for use in temporary
662	// calculations. It starts with a sensible default covering 99% of
663	// uses, and goes up to HARD_MAX_RANGES when needed. Any allocated
664	// storage is freed upon destruction.
665	typedef int_range<3, /*RESIZABLE=*/true> int_range_max;
666
667	class vrange_visitor
668	{
669	public:
670	virtual void visit (const irange &) const { }
671	virtual void visit (const frange &) const { }
672	virtual void visit (const unsupported_range &) const { }
673	};
674
675	typedef int_range<2> value_range;
676
677	// This is an "infinite" precision range object for use in temporary
678	// calculations for any of the handled types. The object can be
679	// transparently used as a vrange.
680
681	class Value_Range
682	{
683	public:
684	Value_Range ();
685	Value_Range (const vrange &r);
686	Value_Range (tree type);
687	Value_Range (tree, tree, value_range_kind kind = VR_RANGE);
688	Value_Range (const Value_Range &);
689	void set_type (tree type);
690	vrange& operator= (const vrange &);
691	Value_Range& operator= (const Value_Range &);
692	bool operator== (const Value_Range &r) const;
693	bool operator!= (const Value_Range &r) const;
694	operator vrange &();
695	operator const vrange &() const;
696	void dump (FILE *) const;
697	static bool supports_type_p (const_tree type);
698
699	// Convenience methods for vrange compatibility.
700	tree type () { return m_vrange->type (); }
701	bool varying_p () const { return m_vrange->varying_p (); }
702	bool undefined_p () const { return m_vrange->undefined_p (); }
703	void set_varying (tree type) { init (type); m_vrange->set_varying (type); }
704	void set_undefined () { m_vrange->set_undefined (); }
705	bool union_ (const vrange &r) { return m_vrange->union_ (r); }
706	bool intersect (const vrange &r) { return m_vrange->intersect (r); }
707	bool contains_p (tree cst) const { return m_vrange->contains_p (cst); }
708	bool singleton_p (tree *result = NULL) const
709	{ return m_vrange->singleton_p (result); }
710	void set_zero (tree type) { init (type); return m_vrange->set_zero (type); }
711	void set_nonzero (tree type)
712	{ init (type); return m_vrange->set_nonzero (type); }
713	bool nonzero_p () const { return m_vrange->nonzero_p (); }
714	bool zero_p () const { return m_vrange->zero_p (); }
715	wide_int lower_bound () const; // For irange/prange comparability.
716	wide_int upper_bound () const; // For irange/prange comparability.
717	void accept (const vrange_visitor &v) const { m_vrange->accept (v); }
718	private:
719	void init (tree type);
720	unsupported_range m_unsupported;
721	vrange *m_vrange;
722	int_range_max m_irange;
723	frange m_frange;
724	};
725
726	inline
727	Value_Range::Value_Range ()
728	{
729	m_vrange = &m_unsupported;
730	}
731
732	// Copy constructor from a vrange.
733
734	inline
735	Value_Range::Value_Range (const vrange &r)
736	{
737	*this = r;
738	}
739
740	// Copy constructor from a TYPE. The range of the temporary is set to
741	// UNDEFINED.
742
743	inline
744	Value_Range::Value_Range (tree type)
745	{
746	init (type);
747	}
748
749	inline
750	Value_Range::Value_Range (tree min, tree max, value_range_kind kind)
751	{
752	init (TREE_TYPE (min));
753	m_vrange->set (min, max, kind);
754	}
755
756	inline
757	Value_Range::Value_Range (const Value_Range &r)
758	{
759	*this = *r.m_vrange;
760	}
761
762	// Initialize object so it is possible to store temporaries of TYPE
763	// into it.
764
765	inline void
766	Value_Range::init (tree type)
767	{
768	gcc_checking_assert (TYPE_P (type));
769
770	if (irange::supports_p (type))
771	m_vrange = &m_irange;
772	else if (frange::supports_p (type))
773	m_vrange = &m_frange;
774	else
775	m_vrange = &m_unsupported;
776	}
777
778	// Set the temporary to allow storing temporaries of TYPE. The range
779	// of the temporary is set to UNDEFINED.
780
781	inline void
782	Value_Range::set_type (tree type)
783	{
784	init (type);
785	m_vrange->set_undefined ();
786	}
787
788	// Assignment operator for temporaries. Copying incompatible types is
789	// allowed.
790
791	inline vrange &
792	Value_Range::operator= (const vrange &r)
793	{
794	if (is_a <irange> (v: r))
795	{
796	m_irange = as_a <irange> (v: r);
797	m_vrange = &m_irange;
798	}
799	else if (is_a <frange> (v: r))
800	{
801	m_frange = as_a <frange> (v: r);
802	m_vrange = &m_frange;
803	}
804	else if (is_a <unsupported_range> (v: r))
805	{
806	m_unsupported = as_a <unsupported_range> (v: r);
807	m_vrange = &m_unsupported;
808	}
809	else
810	gcc_unreachable ();
811
812	return *m_vrange;
813	}
814
815	inline Value_Range &
816	Value_Range::operator= (const Value_Range &r)
817	{
818	if (r.m_vrange == &r.m_irange)
819	{
820	m_irange = r.m_irange;
821	m_vrange = &m_irange;
822	}
823	else if (r.m_vrange == &r.m_frange)
824	{
825	m_frange = r.m_frange;
826	m_vrange = &m_frange;
827	}
828	else if (r.m_vrange == &r.m_unsupported)
829	{
830	m_unsupported = r.m_unsupported;
831	m_vrange = &m_unsupported;
832	}
833	else
834	gcc_unreachable ();
835
836	return *this;
837	}
838
839	inline bool
840	Value_Range::operator== (const Value_Range &r) const
841	{
842	return *m_vrange == *r.m_vrange;
843	}
844
845	inline bool
846	Value_Range::operator!= (const Value_Range &r) const
847	{
848	return *m_vrange != *r.m_vrange;
849	}
850
851	inline
852	Value_Range::operator vrange &()
853	{
854	return *m_vrange;
855	}
856
857	inline
858	Value_Range::operator const vrange &() const
859	{
860	return *m_vrange;
861	}
862
863	// Return TRUE if TYPE is supported by the vrange infrastructure.
864
865	inline bool
866	Value_Range::supports_type_p (const_tree type)
867	{
868	return irange::supports_p (type) || frange::supports_p (type);
869	}
870
871	extern value_range_kind get_legacy_range (const irange &, tree &min, tree &max);
872	extern void dump_value_range (FILE *, const vrange *);
873	extern bool vrp_operand_equal_p (const_tree, const_tree);
874	inline REAL_VALUE_TYPE frange_val_min (const_tree type);
875	inline REAL_VALUE_TYPE frange_val_max (const_tree type);
876
877	// Number of sub-ranges in a range.
878
879	inline unsigned
880	irange::num_pairs () const
881	{
882	return m_num_ranges;
883	}
884
885	inline tree
886	irange::type () const
887	{
888	gcc_checking_assert (m_num_ranges > 0);
889	return m_type;
890	}
891
892	inline bool
893	irange::varying_compatible_p () const
894	{
895	if (m_num_ranges != 1)
896	return false;
897
898	const wide_int &l = m_base[0];
899	const wide_int &u = m_base[1];
900	tree t = m_type;
901
902	if (m_kind == VR_VARYING && t == error_mark_node)
903	return true;
904
905	unsigned prec = TYPE_PRECISION (t);
906	signop sign = TYPE_SIGN (t);
907	if (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t))
908	return (l == wi::min_value (prec, sign)
909	&& u == wi::max_value (prec, sign)
910	&& m_bitmask.unknown_p ());
911	return true;
912	}
913
914	inline bool
915	vrange::varying_p () const
916	{
917	return m_kind == VR_VARYING;
918	}
919
920	inline bool
921	vrange::undefined_p () const
922	{
923	return m_kind == VR_UNDEFINED;
924	}
925
926	inline bool
927	irange::zero_p () const
928	{
929	return (m_kind == VR_RANGE && m_num_ranges == 1
930	&& lower_bound (0) == 0
931	&& upper_bound (0) == 0);
932	}
933
934	inline bool
935	irange::nonzero_p () const
936	{
937	if (undefined_p ())
938	return false;
939
940	wide_int zero = wi::zero (TYPE_PRECISION (type ()));
941	return *this == int_range<2> (type (), zero, zero, VR_ANTI_RANGE);
942	}
943
944	inline bool
945	irange::supports_p (const_tree type)
946	{
947	return INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type);
948	}
949
950	inline bool
951	irange::contains_p (tree cst) const
952	{
953	return contains_p (wi::to_wide (t: cst));
954	}
955
956	inline bool
957	range_includes_zero_p (const irange *vr)
958	{
959	if (vr->undefined_p ())
960	return false;
961
962	if (vr->varying_p ())
963	return true;
964
965	wide_int zero = wi::zero (TYPE_PRECISION (vr->type ()));
966	return vr->contains_p (zero);
967	}
968
969	extern void gt_ggc_mx (vrange *);
970	extern void gt_pch_nx (vrange *);
971	extern void gt_pch_nx (vrange *, gt_pointer_operator, void *);
972	extern void gt_ggc_mx (irange *);
973	extern void gt_pch_nx (irange *);
974	extern void gt_pch_nx (irange *, gt_pointer_operator, void *);
975	extern void gt_ggc_mx (frange *);
976	extern void gt_pch_nx (frange *);
977	extern void gt_pch_nx (frange *, gt_pointer_operator, void *);
978
979	template<unsigned N>
980	inline void
981	gt_ggc_mx (int_range<N> *x)
982	{
983	gt_ggc_mx ((irange *) x);
984	}
985
986	template<unsigned N>
987	inline void
988	gt_pch_nx (int_range<N> *x)
989	{
990	gt_pch_nx ((irange *) x);
991	}
992
993	template<unsigned N>
994	inline void
995	gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
996	{
997	gt_pch_nx ((irange *) x, op, cookie);
998	}
999
1000	// Constructors for irange
1001
1002	inline
1003	irange::irange (wide_int *base, unsigned nranges, bool resizable)
1004	: vrange (VR_IRANGE),
1005	m_resizable (resizable),
1006	m_max_ranges (nranges)
1007	{
1008	m_base = base;
1009	set_undefined ();
1010	}
1011
1012	// Constructors for int_range<>.
1013
1014	template<unsigned N, bool RESIZABLE>
1015	inline
1016	int_range<N, RESIZABLE>::int_range ()
1017	: irange (m_ranges, N, RESIZABLE)
1018	{
1019	}
1020
1021	template<unsigned N, bool RESIZABLE>
1022	int_range<N, RESIZABLE>::int_range (const int_range &other)
1023	: irange (m_ranges, N, RESIZABLE)
1024	{
1025	irange::operator= (other);
1026	}
1027
1028	template<unsigned N, bool RESIZABLE>
1029	int_range<N, RESIZABLE>::int_range (tree min, tree max, value_range_kind kind)
1030	: irange (m_ranges, N, RESIZABLE)
1031	{
1032	irange::set (min, max, kind);
1033	}
1034
1035	template<unsigned N, bool RESIZABLE>
1036	int_range<N, RESIZABLE>::int_range (tree type)
1037	: irange (m_ranges, N, RESIZABLE)
1038	{
1039	set_varying (type);
1040	}
1041
1042	template<unsigned N, bool RESIZABLE>
1043	int_range<N, RESIZABLE>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
1044	value_range_kind kind)
1045	: irange (m_ranges, N, RESIZABLE)
1046	{
1047	set (type, wmin, wmax, kind);
1048	}
1049
1050	template<unsigned N, bool RESIZABLE>
1051	int_range<N, RESIZABLE>::int_range (const irange &other)
1052	: irange (m_ranges, N, RESIZABLE)
1053	{
1054	irange::operator= (other);
1055	}
1056
1057	template<unsigned N, bool RESIZABLE>
1058	int_range<N, RESIZABLE>&
1059	int_range<N, RESIZABLE>::operator= (const int_range &src)
1060	{
1061	irange::operator= (src);
1062	return *this;
1063	}
1064
1065	inline void
1066	irange::set_undefined ()
1067	{
1068	m_kind = VR_UNDEFINED;
1069	m_num_ranges = 0;
1070	}
1071
1072	inline void
1073	irange::set_varying (tree type)
1074	{
1075	m_kind = VR_VARYING;
1076	m_num_ranges = 1;
1077	m_bitmask.set_unknown (TYPE_PRECISION (type));
1078
1079	if (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))
1080	{
1081	m_type = type;
1082	// Strict enum's require varying to be not TYPE_MIN/MAX, but rather
1083	// min_value and max_value.
1084	m_base[0] = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1085	m_base[1] = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1086	}
1087	else
1088	m_type = error_mark_node;
1089	}
1090
1091	// Return the lower bound of a sub-range. PAIR is the sub-range in
1092	// question.
1093
1094	inline wide_int
1095	irange::lower_bound (unsigned pair) const
1096	{
1097	gcc_checking_assert (m_num_ranges > 0);
1098	gcc_checking_assert (pair + 1 <= num_pairs ());
1099	return m_base[pair * 2];
1100	}
1101
1102	// Return the upper bound of a sub-range. PAIR is the sub-range in
1103	// question.
1104
1105	inline wide_int
1106	irange::upper_bound (unsigned pair) const
1107	{
1108	gcc_checking_assert (m_num_ranges > 0);
1109	gcc_checking_assert (pair + 1 <= num_pairs ());
1110	return m_base[pair * 2 + 1];
1111	}
1112
1113	// Return the highest bound of a range.
1114
1115	inline wide_int
1116	irange::upper_bound () const
1117	{
1118	unsigned pairs = num_pairs ();
1119	gcc_checking_assert (pairs > 0);
1120	return upper_bound (pair: pairs - 1);
1121	}
1122
1123	// Set value range VR to a nonzero range of type TYPE.
1124
1125	inline void
1126	irange::set_nonzero (tree type)
1127	{
1128	unsigned prec = TYPE_PRECISION (type);
1129
1130	if (TYPE_UNSIGNED (type))
1131	{
1132	m_type = type;
1133	m_kind = VR_RANGE;
1134	m_base[0] = wi::one (precision: prec);
1135	m_base[1] = wi::minus_one (precision: prec);
1136	m_bitmask.set_unknown (prec);
1137	m_num_ranges = 1;
1138
1139	if (flag_checking)
1140	verify_range ();
1141	}
1142	else
1143	{
1144	wide_int zero = wi::zero (precision: prec);
1145	set (type, zero, zero, VR_ANTI_RANGE);
1146	}
1147	}
1148
1149	// Set value range VR to a ZERO range of type TYPE.
1150
1151	inline void
1152	irange::set_zero (tree type)
1153	{
1154	wide_int zero = wi::zero (TYPE_PRECISION (type));
1155	set (type, zero, zero);
1156	}
1157
1158	// Normalize a range to VARYING or UNDEFINED if possible.
1159
1160	inline void
1161	irange::normalize_kind ()
1162	{
1163	if (m_num_ranges == 0)
1164	set_undefined ();
1165	else if (varying_compatible_p ())
1166	{
1167	if (m_kind == VR_RANGE)
1168	m_kind = VR_VARYING;
1169	else if (m_kind == VR_ANTI_RANGE)
1170	set_undefined ();
1171	}
1172	if (flag_checking)
1173	verify_range ();
1174	}
1175
1176	inline bool
1177	contains_zero_p (const irange &r)
1178	{
1179	if (r.undefined_p ())
1180	return false;
1181
1182	wide_int zero = wi::zero (TYPE_PRECISION (r.type ()));
1183	return r.contains_p (zero);
1184	}
1185
1186	inline wide_int
1187	irange_val_min (const_tree type)
1188	{
1189	gcc_checking_assert (irange::supports_p (type));
1190	return wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1191	}
1192
1193	inline wide_int
1194	irange_val_max (const_tree type)
1195	{
1196	gcc_checking_assert (irange::supports_p (type));
1197	return wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1198	}
1199
1200	inline
1201	frange::frange ()
1202	: vrange (VR_FRANGE)
1203	{
1204	set_undefined ();
1205	}
1206
1207	inline
1208	frange::frange (const frange &src)
1209	: vrange (VR_FRANGE)
1210	{
1211	*this = src;
1212	}
1213
1214	inline
1215	frange::frange (tree type)
1216	: vrange (VR_FRANGE)
1217	{
1218	set_varying (type);
1219	}
1220
1221	// frange constructor from REAL_VALUE_TYPE endpoints.
1222
1223	inline
1224	frange::frange (tree type,
1225	const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1226	value_range_kind kind)
1227	: vrange (VR_FRANGE)
1228	{
1229	set (type, min, max, kind);
1230	}
1231
1232	// frange constructor from trees.
1233
1234	inline
1235	frange::frange (tree min, tree max, value_range_kind kind)
1236	: vrange (VR_FRANGE)
1237	{
1238	set (min, max, kind);
1239	}
1240
1241	inline tree
1242	frange::type () const
1243	{
1244	gcc_checking_assert (!undefined_p ());
1245	return m_type;
1246	}
1247
1248	inline void
1249	frange::set_varying (tree type)
1250	{
1251	m_kind = VR_VARYING;
1252	m_type = type;
1253	m_min = frange_val_min (type);
1254	m_max = frange_val_max (type);
1255	if (HONOR_NANS (m_type))
1256	{
1257	m_pos_nan = true;
1258	m_neg_nan = true;
1259	}
1260	else
1261	{
1262	m_pos_nan = false;
1263	m_neg_nan = false;
1264	}
1265	}
1266
1267	inline void
1268	frange::set_undefined ()
1269	{
1270	m_kind = VR_UNDEFINED;
1271	m_type = NULL;
1272	m_pos_nan = false;
1273	m_neg_nan = false;
1274	// m_min and m_min are uninitialized as they are REAL_VALUE_TYPE ??.
1275	if (flag_checking)
1276	verify_range ();
1277	}
1278
1279	// Set the NAN bits to NAN and adjust the range.
1280
1281	inline void
1282	frange::update_nan (const nan_state &nan)
1283	{
1284	gcc_checking_assert (!undefined_p ());
1285	if (HONOR_NANS (m_type))
1286	{
1287	m_pos_nan = nan.pos_p ();
1288	m_neg_nan = nan.neg_p ();
1289	normalize_kind ();
1290	if (flag_checking)
1291	verify_range ();
1292	}
1293	}
1294
1295	// Set the NAN bit to +-NAN.
1296
1297	inline void
1298	frange::update_nan ()
1299	{
1300	gcc_checking_assert (!undefined_p ());
1301	nan_state nan (true);
1302	update_nan (nan);
1303	}
1304
1305	// Like above, but set the sign of the NAN.
1306
1307	inline void
1308	frange::update_nan (bool sign)
1309	{
1310	gcc_checking_assert (!undefined_p ());
1311	nan_state nan (/*pos=*/!sign, /*neg=*/sign);
1312	update_nan (nan);
1313	}
1314
1315	inline bool
1316	frange::contains_p (tree cst) const
1317	{
1318	return contains_p (*TREE_REAL_CST_PTR (cst));
1319	}
1320
1321	// Clear the NAN bit and adjust the range.
1322
1323	inline void
1324	frange::clear_nan ()
1325	{
1326	gcc_checking_assert (!undefined_p ());
1327	m_pos_nan = false;
1328	m_neg_nan = false;
1329	normalize_kind ();
1330	if (flag_checking)
1331	verify_range ();
1332	}
1333
1334	// Set R to maximum representable value for TYPE.
1335
1336	inline REAL_VALUE_TYPE
1337	real_max_representable (const_tree type)
1338	{
1339	REAL_VALUE_TYPE r;
1340	char buf[128];
1341	get_max_float (REAL_MODE_FORMAT (TYPE_MODE (type)),
1342	buf, sizeof (buf), false);
1343	int res = real_from_string (&r, buf);
1344	gcc_checking_assert (!res);
1345	return r;
1346	}
1347
1348	// Return the minimum representable value for TYPE.
1349
1350	inline REAL_VALUE_TYPE
1351	real_min_representable (const_tree type)
1352	{
1353	REAL_VALUE_TYPE r = real_max_representable (type);
1354	r = real_value_negate (&r);
1355	return r;
1356	}
1357
1358	// Return the minimum value for TYPE.
1359
1360	inline REAL_VALUE_TYPE
1361	frange_val_min (const_tree type)
1362	{
1363	if (HONOR_INFINITIES (type))
1364	return dconstninf;
1365	else
1366	return real_min_representable (type);
1367	}
1368
1369	// Return the maximum value for TYPE.
1370
1371	inline REAL_VALUE_TYPE
1372	frange_val_max (const_tree type)
1373	{
1374	if (HONOR_INFINITIES (type))
1375	return dconstinf;
1376	else
1377	return real_max_representable (type);
1378	}
1379
1380	// Return TRUE if R is the minimum value for TYPE.
1381
1382	inline bool
1383	frange_val_is_min (const REAL_VALUE_TYPE &r, const_tree type)
1384	{
1385	REAL_VALUE_TYPE min = frange_val_min (type);
1386	return real_identical (&min, &r);
1387	}
1388
1389	// Return TRUE if R is the max value for TYPE.
1390
1391	inline bool
1392	frange_val_is_max (const REAL_VALUE_TYPE &r, const_tree type)
1393	{
1394	REAL_VALUE_TYPE max = frange_val_max (type);
1395	return real_identical (&max, &r);
1396	}
1397
1398	// Build a NAN with a state of NAN.
1399
1400	inline void
1401	frange::set_nan (tree type, const nan_state &nan)
1402	{
1403	gcc_checking_assert (nan.pos_p () || nan.neg_p ());
1404	if (HONOR_NANS (type))
1405	{
1406	m_kind = VR_NAN;
1407	m_type = type;
1408	m_neg_nan = nan.neg_p ();
1409	m_pos_nan = nan.pos_p ();
1410	if (flag_checking)
1411	verify_range ();
1412	}
1413	else
1414	set_undefined ();
1415	}
1416
1417	// Build a signless NAN of type TYPE.
1418
1419	inline void
1420	frange::set_nan (tree type)
1421	{
1422	nan_state nan (true);
1423	set_nan (type, nan);
1424	}
1425
1426	// Build a NAN of type TYPE with SIGN.
1427
1428	inline void
1429	frange::set_nan (tree type, bool sign)
1430	{
1431	nan_state nan (/*pos=*/!sign, /*neg=*/sign);
1432	set_nan (type, nan);
1433	}
1434
1435	// Return TRUE if range is known to be finite.
1436
1437	inline bool
1438	frange::known_isfinite () const
1439	{
1440	if (undefined_p () || varying_p () || m_kind == VR_ANTI_RANGE)
1441	return false;
1442	return (!maybe_isnan () && !real_isinf (&m_min) && !real_isinf (&m_max));
1443	}
1444
1445	// Return TRUE if range may be infinite.
1446
1447	inline bool
1448	frange::maybe_isinf () const
1449	{
1450	if (undefined_p () || m_kind == VR_ANTI_RANGE || m_kind == VR_NAN)
1451	return false;
1452	if (varying_p ())
1453	return true;
1454	return real_isinf (&m_min) || real_isinf (&m_max);
1455	}
1456
1457	// Return TRUE if range is known to be the [-INF,-INF] or [+INF,+INF].
1458
1459	inline bool
1460	frange::known_isinf () const
1461	{
1462	return (m_kind == VR_RANGE
1463	&& !maybe_isnan ()
1464	&& real_identical (&m_min, &m_max)
1465	&& real_isinf (&m_min));
1466	}
1467
1468	// Return TRUE if range is possibly a NAN.
1469
1470	inline bool
1471	frange::maybe_isnan () const
1472	{
1473	if (undefined_p ())
1474	return false;
1475	return m_pos_nan || m_neg_nan;
1476	}
1477
1478	// Return TRUE if range is possibly a NAN with SIGN.
1479
1480	inline bool
1481	frange::maybe_isnan (bool sign) const
1482	{
1483	if (undefined_p ())
1484	return false;
1485	if (sign)
1486	return m_neg_nan;
1487	return m_pos_nan;
1488	}
1489
1490	// Return TRUE if range is a +NAN or -NAN.
1491
1492	inline bool
1493	frange::known_isnan () const
1494	{
1495	return m_kind == VR_NAN;
1496	}
1497
1498	// If the signbit for the range is known, set it in SIGNBIT and return
1499	// TRUE.
1500
1501	inline bool
1502	frange::signbit_p (bool &signbit) const
1503	{
1504	if (undefined_p ())
1505	return false;
1506
1507	// NAN with unknown sign.
1508	if (m_pos_nan && m_neg_nan)
1509	return false;
1510	// No NAN.
1511	if (!m_pos_nan && !m_neg_nan)
1512	{
1513	if (m_min.sign == m_max.sign)
1514	{
1515	signbit = m_min.sign;
1516	return true;
1517	}
1518	return false;
1519	}
1520	// NAN with known sign.
1521	bool nan_sign = m_neg_nan;
1522	if (known_isnan ()
1523	|| (nan_sign == m_min.sign && nan_sign == m_max.sign))
1524	{
1525	signbit = nan_sign;
1526	return true;
1527	}
1528	return false;
1529	}
1530
1531	// If range has a NAN with a known sign, set it in SIGNBIT and return
1532	// TRUE.
1533
1534	inline bool
1535	frange::nan_signbit_p (bool &signbit) const
1536	{
1537	if (undefined_p ())
1538	return false;
1539
1540	if (m_pos_nan == m_neg_nan)
1541	return false;
1542
1543	signbit = m_neg_nan;
1544	return true;
1545	}
1546
1547	void frange_nextafter (enum machine_mode, REAL_VALUE_TYPE &,
1548	const REAL_VALUE_TYPE &);
1549	void frange_arithmetic (enum tree_code, tree, REAL_VALUE_TYPE &,
1550	const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
1551	const REAL_VALUE_TYPE &);
1552
1553	#endif // GCC_VALUE_RANGE_H
1554