1	/* Code for range operators.
2	Copyright (C) 2017-2023 Free Software Foundation, Inc.
3	Contributed by Andrew MacLeod <amacleod@redhat.com>
4	and Aldy Hernandez <aldyh@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	#include "config.h"
23	#include "system.h"
24	#include "coretypes.h"
25	#include "backend.h"
26	#include "insn-codes.h"
27	#include "rtl.h"
28	#include "tree.h"
29	#include "gimple.h"
30	#include "cfghooks.h"
31	#include "tree-pass.h"
32	#include "ssa.h"
33	#include "optabs-tree.h"
34	#include "gimple-pretty-print.h"
35	#include "diagnostic-core.h"
36	#include "flags.h"
37	#include "fold-const.h"
38	#include "stor-layout.h"
39	#include "calls.h"
40	#include "cfganal.h"
41	#include "gimple-iterator.h"
42	#include "gimple-fold.h"
43	#include "tree-eh.h"
44	#include "gimple-walk.h"
45	#include "tree-cfg.h"
46	#include "wide-int.h"
47	#include "value-relation.h"
48	#include "range-op.h"
49	#include "tree-ssa-ccp.h"
50	#include "range-op-mixed.h"
51
52	// Instantiate the operators which apply to multiple types here.
53
54	operator_equal op_equal;
55	operator_not_equal op_not_equal;
56	operator_lt op_lt;
57	operator_le op_le;
58	operator_gt op_gt;
59	operator_ge op_ge;
60	operator_identity op_ident;
61	operator_cst op_cst;
62	operator_cast op_cast;
63	operator_plus op_plus;
64	operator_abs op_abs;
65	operator_minus op_minus;
66	operator_negate op_negate;
67	operator_mult op_mult;
68	operator_addr_expr op_addr;
69	operator_bitwise_not op_bitwise_not;
70	operator_bitwise_xor op_bitwise_xor;
71	operator_bitwise_and op_bitwise_and;
72	operator_bitwise_or op_bitwise_or;
73	operator_min op_min;
74	operator_max op_max;
75
76	// Instantaite a range operator table.
77	range_op_table operator_table;
78
79	// Invoke the initialization routines for each class of range.
80
81	range_op_table::range_op_table ()
82	{
83	initialize_integral_ops ();
84	initialize_pointer_ops ();
85	initialize_float_ops ();
86
87	set (code: EQ_EXPR, op&: op_equal);
88	set (code: NE_EXPR, op&: op_not_equal);
89	set (code: LT_EXPR, op&: op_lt);
90	set (code: LE_EXPR, op&: op_le);
91	set (code: GT_EXPR, op&: op_gt);
92	set (code: GE_EXPR, op&: op_ge);
93	set (code: SSA_NAME, op&: op_ident);
94	set (code: PAREN_EXPR, op&: op_ident);
95	set (code: OBJ_TYPE_REF, op&: op_ident);
96	set (code: REAL_CST, op&: op_cst);
97	set (code: INTEGER_CST, op&: op_cst);
98	set (code: NOP_EXPR, op&: op_cast);
99	set (code: CONVERT_EXPR, op&: op_cast);
100	set (code: PLUS_EXPR, op&: op_plus);
101	set (code: ABS_EXPR, op&: op_abs);
102	set (code: MINUS_EXPR, op&: op_minus);
103	set (code: NEGATE_EXPR, op&: op_negate);
104	set (code: MULT_EXPR, op&: op_mult);
105
106	// Occur in both integer and pointer tables, but currently share
107	// integral implementation.
108	set (code: ADDR_EXPR, op&: op_addr);
109	set (code: BIT_NOT_EXPR, op&: op_bitwise_not);
110	set (code: BIT_XOR_EXPR, op&: op_bitwise_xor);
111
112	// These are in both integer and pointer tables, but pointer has a different
113	// implementation.
114	// If commented out, there is a hybrid version in range-op-ptr.cc which
115	// is used until there is a pointer range class. Then we can simply
116	// uncomment the operator here and use the unified version.
117
118	// set (BIT_AND_EXPR, op_bitwise_and);
119	// set (BIT_IOR_EXPR, op_bitwise_or);
120	// set (MIN_EXPR, op_min);
121	// set (MAX_EXPR, op_max);
122	}
123
124	// Instantiate a default range operator for opcodes with no entry.
125
126	range_operator default_operator;
127
128	// Create a default range_op_handler.
129
130	range_op_handler::range_op_handler ()
131	{
132	m_operator = &default_operator;
133	}
134
135	// Create a range_op_handler for CODE. Use a default operatoer if CODE
136	// does not have an entry.
137
138	range_op_handler::range_op_handler (unsigned code)
139	{
140	m_operator = operator_table[code];
141	if (!m_operator)
142	m_operator = &default_operator;
143	}
144
145	// Return TRUE if this handler has a non-default operator.
146
147	range_op_handler::operator bool () const
148	{
149	return m_operator != &default_operator;
150	}
151
152	// Return a pointer to the range operator assocaited with this handler.
153	// If it is a default operator, return NULL.
154	// This is the equivalent of indexing the range table.
155
156	range_operator *
157	range_op_handler::range_op () const
158	{
159	if (m_operator != &default_operator)
160	return m_operator;
161	return NULL;
162	}
163
164	// Create a dispatch pattern for value range discriminators LHS, OP1, and OP2.
165	// This is used to produce a unique value for each dispatch pattern. Shift
166	// values are based on the size of the m_discriminator field in value_range.h.
167
168	constexpr unsigned
169	dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
170	{
171	return ((lhs << 8) + (op1 << 4) + (op2));
172	}
173
174	// These are the supported dispatch patterns. These map to the parameter list
175	// of the routines in range_operator. Note the last 3 characters are
176	// shorthand for the LHS, OP1, and OP2 range discriminator class.
177
178	const unsigned RO_III = dispatch_trio (lhs: VR_IRANGE, op1: VR_IRANGE, op2: VR_IRANGE);
179	const unsigned RO_IFI = dispatch_trio (lhs: VR_IRANGE, op1: VR_FRANGE, op2: VR_IRANGE);
180	const unsigned RO_IFF = dispatch_trio (lhs: VR_IRANGE, op1: VR_FRANGE, op2: VR_FRANGE);
181	const unsigned RO_FFF = dispatch_trio (lhs: VR_FRANGE, op1: VR_FRANGE, op2: VR_FRANGE);
182	const unsigned RO_FIF = dispatch_trio (lhs: VR_FRANGE, op1: VR_IRANGE, op2: VR_FRANGE);
183	const unsigned RO_FII = dispatch_trio (lhs: VR_FRANGE, op1: VR_IRANGE, op2: VR_IRANGE);
184
185	// Return a dispatch value for parameter types LHS, OP1 and OP2.
186
187	unsigned
188	range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
189	const vrange& op2) const
190	{
191	return dispatch_trio (lhs: lhs.m_discriminator, op1: op1.m_discriminator,
192	op2: op2.m_discriminator);
193	}
194
195	// Dispatch a call to fold_range based on the types of R, LH and RH.
196
197	bool
198	range_op_handler::fold_range (vrange &r, tree type,
199	const vrange &lh,
200	const vrange &rh,
201	relation_trio rel) const
202	{
203	gcc_checking_assert (m_operator);
204	switch (dispatch_kind (lhs: r, op1: lh, op2: rh))
205	{
206	case RO_III:
207	return m_operator->fold_range (r&: as_a <irange> (v&: r), type,
208	lh: as_a <irange> (v: lh),
209	rh: as_a <irange> (v: rh), rel);
210	case RO_IFI:
211	return m_operator->fold_range (r&: as_a <irange> (v&: r), type,
212	lh: as_a <frange> (v: lh),
213	rh: as_a <irange> (v: rh), rel);
214	case RO_IFF:
215	return m_operator->fold_range (r&: as_a <irange> (v&: r), type,
216	lh: as_a <frange> (v: lh),
217	rh: as_a <frange> (v: rh), rel);
218	case RO_FFF:
219	return m_operator->fold_range (r&: as_a <frange> (v&: r), type,
220	lh: as_a <frange> (v: lh),
221	rh: as_a <frange> (v: rh), rel);
222	case RO_FII:
223	return m_operator->fold_range (r&: as_a <frange> (v&: r), type,
224	lh: as_a <irange> (v: lh),
225	rh: as_a <irange> (v: rh), rel);
226	default:
227	return false;
228	}
229	}
230
231	// Dispatch a call to op1_range based on the types of R, LHS and OP2.
232
233	bool
234	range_op_handler::op1_range (vrange &r, tree type,
235	const vrange &lhs,
236	const vrange &op2,
237	relation_trio rel) const
238	{
239	gcc_checking_assert (m_operator);
240
241	if (lhs.undefined_p ())
242	return false;
243	switch (dispatch_kind (lhs: r, op1: lhs, op2))
244	{
245	case RO_III:
246	return m_operator->op1_range (r&: as_a <irange> (v&: r), type,
247	lhs: as_a <irange> (v: lhs),
248	op2: as_a <irange> (v: op2), rel);
249	case RO_FIF:
250	return m_operator->op1_range (r&: as_a <frange> (v&: r), type,
251	lhs: as_a <irange> (v: lhs),
252	op2: as_a <frange> (v: op2), rel);
253	case RO_FFF:
254	return m_operator->op1_range (r&: as_a <frange> (v&: r), type,
255	lhs: as_a <frange> (v: lhs),
256	op2: as_a <frange> (v: op2), rel);
257	default:
258	return false;
259	}
260	}
261
262	// Dispatch a call to op2_range based on the types of R, LHS and OP1.
263
264	bool
265	range_op_handler::op2_range (vrange &r, tree type,
266	const vrange &lhs,
267	const vrange &op1,
268	relation_trio rel) const
269	{
270	gcc_checking_assert (m_operator);
271	if (lhs.undefined_p ())
272	return false;
273
274	switch (dispatch_kind (lhs: r, op1: lhs, op2: op1))
275	{
276	case RO_III:
277	return m_operator->op2_range (r&: as_a <irange> (v&: r), type,
278	lhs: as_a <irange> (v: lhs),
279	op1: as_a <irange> (v: op1), rel);
280	case RO_FIF:
281	return m_operator->op2_range (r&: as_a <frange> (v&: r), type,
282	lhs: as_a <irange> (v: lhs),
283	op1: as_a <frange> (v: op1), rel);
284	case RO_FFF:
285	return m_operator->op2_range (r&: as_a <frange> (v&: r), type,
286	lhs: as_a <frange> (v: lhs),
287	op1: as_a <frange> (v: op1), rel);
288	default:
289	return false;
290	}
291	}
292
293	// Dispatch a call to lhs_op1_relation based on the types of LHS, OP1 and OP2.
294
295	relation_kind
296	range_op_handler::lhs_op1_relation (const vrange &lhs,
297	const vrange &op1,
298	const vrange &op2,
299	relation_kind rel) const
300	{
301	gcc_checking_assert (m_operator);
302
303	switch (dispatch_kind (lhs, op1, op2))
304	{
305	case RO_III:
306	return m_operator->lhs_op1_relation (lhs: as_a <irange> (v: lhs),
307	op1: as_a <irange> (v: op1),
308	op2: as_a <irange> (v: op2), rel);
309	case RO_IFF:
310	return m_operator->lhs_op1_relation (lhs: as_a <irange> (v: lhs),
311	op1: as_a <frange> (v: op1),
312	op2: as_a <frange> (v: op2), rel);
313	case RO_FFF:
314	return m_operator->lhs_op1_relation (lhs: as_a <frange> (v: lhs),
315	op1: as_a <frange> (v: op1),
316	op2: as_a <frange> (v: op2), rel);
317	default:
318	return VREL_VARYING;
319	}
320	}
321
322	// Dispatch a call to lhs_op2_relation based on the types of LHS, OP1 and OP2.
323
324	relation_kind
325	range_op_handler::lhs_op2_relation (const vrange &lhs,
326	const vrange &op1,
327	const vrange &op2,
328	relation_kind rel) const
329	{
330	gcc_checking_assert (m_operator);
331	switch (dispatch_kind (lhs, op1, op2))
332	{
333	case RO_III:
334	return m_operator->lhs_op2_relation (lhs: as_a <irange> (v: lhs),
335	op1: as_a <irange> (v: op1),
336	op2: as_a <irange> (v: op2), rel);
337	case RO_IFF:
338	return m_operator->lhs_op2_relation (lhs: as_a <irange> (v: lhs),
339	op1: as_a <frange> (v: op1),
340	op2: as_a <frange> (v: op2), rel);
341	case RO_FFF:
342	return m_operator->lhs_op2_relation (lhs: as_a <frange> (v: lhs),
343	op1: as_a <frange> (v: op1),
344	op2: as_a <frange> (v: op2), rel);
345	default:
346	return VREL_VARYING;
347	}
348	}
349
350	// Dispatch a call to op1_op2_relation based on the type of LHS.
351
352	relation_kind
353	range_op_handler::op1_op2_relation (const vrange &lhs,
354	const vrange &op1,
355	const vrange &op2) const
356	{
357	gcc_checking_assert (m_operator);
358	switch (dispatch_kind (lhs, op1, op2))
359	{
360	case RO_III:
361	return m_operator->op1_op2_relation (lhs: as_a <irange> (v: lhs),
362	op1: as_a <irange> (v: op1),
363	op2: as_a <irange> (v: op2));
364
365	case RO_IFF:
366	return m_operator->op1_op2_relation (lhs: as_a <irange> (v: lhs),
367	op1: as_a <frange> (v: op1),
368	op2: as_a <frange> (v: op2));
369
370	case RO_FFF:
371	return m_operator->op1_op2_relation (lhs: as_a <frange> (v: lhs),
372	op1: as_a <frange> (v: op1),
373	op2: as_a <frange> (v: op2));
374
375	default:
376	return VREL_VARYING;
377	}
378	}
379
380	bool
381	range_op_handler::overflow_free_p (const vrange &lh,
382	const vrange &rh,
383	relation_trio rel) const
384	{
385	gcc_checking_assert (m_operator);
386	switch (dispatch_kind (lhs: lh, op1: lh, op2: rh))
387	{
388	case RO_III:
389	return m_operator->overflow_free_p(lh: as_a <irange> (v: lh),
390	rh: as_a <irange> (v: rh),
391	rel);
392	default:
393	return false;
394	}
395	}
396
397	// Update the known bitmasks in R when applying the operation CODE to
398	// LH and RH.
399
400	void
401	update_known_bitmask (irange &r, tree_code code,
402	const irange &lh, const irange &rh)
403	{
404	if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
405	|| r.singleton_p ())
406	return;
407
408	widest_int widest_value, widest_mask;
409	tree type = r.type ();
410	signop sign = TYPE_SIGN (type);
411	int prec = TYPE_PRECISION (type);
412	irange_bitmask lh_bits = lh.get_bitmask ();
413	irange_bitmask rh_bits = rh.get_bitmask ();
414
415	switch (get_gimple_rhs_class (code))
416	{
417	case GIMPLE_UNARY_RHS:
418	bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
419	TYPE_SIGN (lh.type ()),
420	TYPE_PRECISION (lh.type ()),
421	widest_int::from (x: lh_bits.value (), sgn: sign),
422	widest_int::from (x: lh_bits.mask (), sgn: sign));
423	break;
424	case GIMPLE_BINARY_RHS:
425	bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
426	TYPE_SIGN (lh.type ()),
427	TYPE_PRECISION (lh.type ()),
428	widest_int::from (x: lh_bits.value (), sgn: sign),
429	widest_int::from (x: lh_bits.mask (), sgn: sign),
430	TYPE_SIGN (rh.type ()),
431	TYPE_PRECISION (rh.type ()),
432	widest_int::from (x: rh_bits.value (), sgn: sign),
433	widest_int::from (x: rh_bits.mask (), sgn: sign));
434	break;
435	default:
436	gcc_unreachable ();
437	}
438
439	wide_int mask = wide_int::from (x: widest_mask, precision: prec, sgn: sign);
440	wide_int value = wide_int::from (x: widest_value, precision: prec, sgn: sign);
441	// Bitmasks must have the unknown value bits cleared.
442	value &= ~mask;
443	irange_bitmask bm (value, mask);
444	r.update_bitmask (bm);
445	}
446
447	// Return the upper limit for a type.
448
449	static inline wide_int
450	max_limit (const_tree type)
451	{
452	return irange_val_max (type);
453	}
454
455	// Return the lower limit for a type.
456
457	static inline wide_int
458	min_limit (const_tree type)
459	{
460	return irange_val_min (type);
461	}
462
463	// Return false if shifting by OP is undefined behavior. Otherwise, return
464	// true and the range it is to be shifted by. This allows trimming out of
465	// undefined ranges, leaving only valid ranges if there are any.
466
467	static inline bool
468	get_shift_range (irange &r, tree type, const irange &op)
469	{
470	if (op.undefined_p ())
471	return false;
472
473	// Build valid range and intersect it with the shift range.
474	r = value_range (op.type (),
475	wi::shwi (val: 0, TYPE_PRECISION (op.type ())),
476	wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
477	r.intersect (op);
478
479	// If there are no valid ranges in the shift range, returned false.
480	if (r.undefined_p ())
481	return false;
482	return true;
483	}
484
485	// Default wide_int fold operation returns [MIN, MAX].
486
487	void
488	range_operator::wi_fold (irange &r, tree type,
489	const wide_int &lh_lb ATTRIBUTE_UNUSED,
490	const wide_int &lh_ub ATTRIBUTE_UNUSED,
491	const wide_int &rh_lb ATTRIBUTE_UNUSED,
492	const wide_int &rh_ub ATTRIBUTE_UNUSED) const
493	{
494	gcc_checking_assert (r.supports_type_p (type));
495	r.set_varying (type);
496	}
497
498	// Call wi_fold when both op1 and op2 are equivalent. Further split small
499	// subranges into constants. This can provide better precision.
500	// For x + y, when x == y with a range of [0,4] instead of [0, 8] produce
501	// [0,0][2, 2][4,4][6, 6][8, 8]
502	// LIMIT is the maximum number of elements in range allowed before we
503	// do not process them individually.
504
505	void
506	range_operator::wi_fold_in_parts_equiv (irange &r, tree type,
507	const wide_int &lh_lb,
508	const wide_int &lh_ub,
509	unsigned limit) const
510	{
511	int_range_max tmp;
512	widest_int lh_range = wi::sub (x: widest_int::from (x: lh_ub, TYPE_SIGN (type)),
513	y: widest_int::from (x: lh_lb, TYPE_SIGN (type)));
514	// if there are 1 to 8 values in the LH range, split them up.
515	r.set_undefined ();
516	if (lh_range >= 0 && lh_range < limit)
517	{
518	for (unsigned x = 0; x <= lh_range; x++)
519	{
520	wide_int val = lh_lb + x;
521	wi_fold (r&: tmp, type, lh_lb: val, lh_ub: val, rh_lb: val, rh_ub: val);
522	r.union_ (tmp);
523	}
524	}
525	// Otherwise just call wi_fold.
526	else
527	wi_fold (r, type, lh_lb, lh_ub, rh_lb: lh_lb, rh_ub: lh_ub);
528	}
529
530	// Call wi_fold, except further split small subranges into constants.
531	// This can provide better precision. For something 8 >> [0,1]
532	// Instead of [8, 16], we will produce [8,8][16,16]
533
534	void
535	range_operator::wi_fold_in_parts (irange &r, tree type,
536	const wide_int &lh_lb,
537	const wide_int &lh_ub,
538	const wide_int &rh_lb,
539	const wide_int &rh_ub) const
540	{
541	int_range_max tmp;
542	widest_int rh_range = wi::sub (x: widest_int::from (x: rh_ub, TYPE_SIGN (type)),
543	y: widest_int::from (x: rh_lb, TYPE_SIGN (type)));
544	widest_int lh_range = wi::sub (x: widest_int::from (x: lh_ub, TYPE_SIGN (type)),
545	y: widest_int::from (x: lh_lb, TYPE_SIGN (type)));
546	// If there are 2, 3, or 4 values in the RH range, do them separately.
547	// Call wi_fold_in_parts to check the RH side.
548	if (rh_range > 0 && rh_range < 4)
549	{
550	wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_ub: rh_lb);
551	if (rh_range > 1)
552	{
553	wi_fold_in_parts (r&: tmp, type, lh_lb, lh_ub, rh_lb: rh_lb + 1, rh_ub: rh_lb + 1);
554	r.union_ (tmp);
555	if (rh_range == 3)
556	{
557	wi_fold_in_parts (r&: tmp, type, lh_lb, lh_ub, rh_lb: rh_lb + 2, rh_ub: rh_lb + 2);
558	r.union_ (tmp);
559	}
560	}
561	wi_fold_in_parts (r&: tmp, type, lh_lb, lh_ub, rh_lb: rh_ub, rh_ub);
562	r.union_ (tmp);
563	}
564	// Otherwise check for 2, 3, or 4 values in the LH range and split them up.
565	// The RH side has been checked, so no recursion needed.
566	else if (lh_range > 0 && lh_range < 4)
567	{
568	wi_fold (r, type, lh_lb, lh_ub: lh_lb, rh_lb, rh_ub);
569	if (lh_range > 1)
570	{
571	wi_fold (r&: tmp, type, lh_lb: lh_lb + 1, lh_ub: lh_lb + 1, rh_lb, rh_ub);
572	r.union_ (tmp);
573	if (lh_range == 3)
574	{
575	wi_fold (r&: tmp, type, lh_lb: lh_lb + 2, lh_ub: lh_lb + 2, rh_lb, rh_ub);
576	r.union_ (tmp);
577	}
578	}
579	wi_fold (r&: tmp, type, lh_lb: lh_ub, lh_ub, rh_lb, rh_ub);
580	r.union_ (tmp);
581	}
582	// Otherwise just call wi_fold.
583	else
584	wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
585	}
586
587	// The default for fold is to break all ranges into sub-ranges and
588	// invoke the wi_fold method on each sub-range pair.
589
590	bool
591	range_operator::fold_range (irange &r, tree type,
592	const irange &lh,
593	const irange &rh,
594	relation_trio trio) const
595	{
596	gcc_checking_assert (r.supports_type_p (type));
597	if (empty_range_varying (r, type, op1: lh, op2: rh))
598	return true;
599
600	relation_kind rel = trio.op1_op2 ();
601	unsigned num_lh = lh.num_pairs ();
602	unsigned num_rh = rh.num_pairs ();
603
604	// If op1 and op2 are equivalences, then we don't need a complete cross
605	// product, just pairs of matching elements.
606	if (relation_equiv_p (r: rel) && lh == rh)
607	{
608	int_range_max tmp;
609	r.set_undefined ();
610	for (unsigned x = 0; x < num_lh; ++x)
611	{
612	// If the number of subranges is too high, limit subrange creation.
613	unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
614	wide_int lh_lb = lh.lower_bound (pair: x);
615	wide_int lh_ub = lh.upper_bound (pair: x);
616	wi_fold_in_parts_equiv (r&: tmp, type, lh_lb, lh_ub, limit);
617	r.union_ (tmp);
618	if (r.varying_p ())
619	break;
620	}
621	op1_op2_relation_effect (lhs_range&: r, type, op1_range: lh, op2_range: rh, rel);
622	update_bitmask (r, lh, rh);
623	return true;
624	}
625
626	// If both ranges are single pairs, fold directly into the result range.
627	// If the number of subranges grows too high, produce a summary result as the
628	// loop becomes exponential with little benefit. See PR 103821.
629	if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
630	{
631	wi_fold_in_parts (r, type, lh_lb: lh.lower_bound (), lh_ub: lh.upper_bound (),
632	rh_lb: rh.lower_bound (), rh_ub: rh.upper_bound ());
633	op1_op2_relation_effect (lhs_range&: r, type, op1_range: lh, op2_range: rh, rel);
634	update_bitmask (r, lh, rh);
635	return true;
636	}
637
638	int_range_max tmp;
639	r.set_undefined ();
640	for (unsigned x = 0; x < num_lh; ++x)
641	for (unsigned y = 0; y < num_rh; ++y)
642	{
643	wide_int lh_lb = lh.lower_bound (pair: x);
644	wide_int lh_ub = lh.upper_bound (pair: x);
645	wide_int rh_lb = rh.lower_bound (pair: y);
646	wide_int rh_ub = rh.upper_bound (pair: y);
647	wi_fold_in_parts (r&: tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
648	r.union_ (tmp);
649	if (r.varying_p ())
650	{
651	op1_op2_relation_effect (lhs_range&: r, type, op1_range: lh, op2_range: rh, rel);
652	update_bitmask (r, lh, rh);
653	return true;
654	}
655	}
656	op1_op2_relation_effect (lhs_range&: r, type, op1_range: lh, op2_range: rh, rel);
657	update_bitmask (r, lh, rh);
658	return true;
659	}
660
661	// The default for op1_range is to return false.
662
663	bool
664	range_operator::op1_range (irange &r ATTRIBUTE_UNUSED,
665	tree type ATTRIBUTE_UNUSED,
666	const irange &lhs ATTRIBUTE_UNUSED,
667	const irange &op2 ATTRIBUTE_UNUSED,
668	relation_trio) const
669	{
670	return false;
671	}
672
673	// The default for op2_range is to return false.
674
675	bool
676	range_operator::op2_range (irange &r ATTRIBUTE_UNUSED,
677	tree type ATTRIBUTE_UNUSED,
678	const irange &lhs ATTRIBUTE_UNUSED,
679	const irange &op1 ATTRIBUTE_UNUSED,
680	relation_trio) const
681	{
682	return false;
683	}
684
685	// The default relation routines return VREL_VARYING.
686
687	relation_kind
688	range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
689	const irange &op1 ATTRIBUTE_UNUSED,
690	const irange &op2 ATTRIBUTE_UNUSED,
691	relation_kind rel ATTRIBUTE_UNUSED) const
692	{
693	return VREL_VARYING;
694	}
695
696	relation_kind
697	range_operator::lhs_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
698	const irange &op1 ATTRIBUTE_UNUSED,
699	const irange &op2 ATTRIBUTE_UNUSED,
700	relation_kind rel ATTRIBUTE_UNUSED) const
701	{
702	return VREL_VARYING;
703	}
704
705	relation_kind
706	range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
707	const irange &op1 ATTRIBUTE_UNUSED,
708	const irange &op2 ATTRIBUTE_UNUSED) const
709	{
710	return VREL_VARYING;
711	}
712
713	// Default is no relation affects the LHS.
714
715	bool
716	range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
717	tree type ATTRIBUTE_UNUSED,
718	const irange &op1_range ATTRIBUTE_UNUSED,
719	const irange &op2_range ATTRIBUTE_UNUSED,
720	relation_kind rel ATTRIBUTE_UNUSED) const
721	{
722	return false;
723	}
724
725	bool
726	range_operator::overflow_free_p (const irange &, const irange &,
727	relation_trio) const
728	{
729	return false;
730	}
731
732	// Apply any known bitmask updates based on this operator.
733
734	void
735	range_operator::update_bitmask (irange &, const irange &,
736	const irange &) const
737	{
738	}
739
740	// Create and return a range from a pair of wide-ints that are known
741	// to have overflowed (or underflowed).
742
743	static void
744	value_range_from_overflowed_bounds (irange &r, tree type,
745	const wide_int &wmin,
746	const wide_int &wmax)
747	{
748	const signop sgn = TYPE_SIGN (type);
749	const unsigned int prec = TYPE_PRECISION (type);
750
751	wide_int tmin = wide_int::from (x: wmin, precision: prec, sgn);
752	wide_int tmax = wide_int::from (x: wmax, precision: prec, sgn);
753
754	bool covers = false;
755	wide_int tem = tmin;
756	tmin = tmax + 1;
757	if (wi::cmp (x: tmin, y: tmax, sgn) < 0)
758	covers = true;
759	tmax = tem - 1;
760	if (wi::cmp (x: tmax, y: tem, sgn) > 0)
761	covers = true;
762
763	// If the anti-range would cover nothing, drop to varying.
764	// Likewise if the anti-range bounds are outside of the types
765	// values.
766	if (covers || wi::cmp (x: tmin, y: tmax, sgn) > 0)
767	r.set_varying (type);
768	else
769	r.set (type, tmin, tmax, VR_ANTI_RANGE);
770	}
771
772	// Create and return a range from a pair of wide-ints. MIN_OVF and
773	// MAX_OVF describe any overflow that might have occurred while
774	// calculating WMIN and WMAX respectively.
775
776	static void
777	value_range_with_overflow (irange &r, tree type,
778	const wide_int &wmin, const wide_int &wmax,
779	wi::overflow_type min_ovf = wi::OVF_NONE,
780	wi::overflow_type max_ovf = wi::OVF_NONE)
781	{
782	const signop sgn = TYPE_SIGN (type);
783	const unsigned int prec = TYPE_PRECISION (type);
784	const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
785
786	// For one bit precision if max != min, then the range covers all
787	// values.
788	if (prec == 1 && wi::ne_p (x: wmax, y: wmin))
789	{
790	r.set_varying (type);
791	return;
792	}
793
794	if (overflow_wraps)
795	{
796	// If overflow wraps, truncate the values and adjust the range,
797	// kind, and bounds appropriately.
798	if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
799	{
800	wide_int tmin = wide_int::from (x: wmin, precision: prec, sgn);
801	wide_int tmax = wide_int::from (x: wmax, precision: prec, sgn);
802	// If the limits are swapped, we wrapped around and cover
803	// the entire range.
804	if (wi::gt_p (x: tmin, y: tmax, sgn))
805	r.set_varying (type);
806	else
807	// No overflow or both overflow or underflow. The range
808	// kind stays normal.
809	r.set (type, tmin, tmax);
810	return;
811	}
812
813	if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
814	|| (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
815	value_range_from_overflowed_bounds (r, type, wmin, wmax);
816	else
817	// Other underflow and/or overflow, drop to VR_VARYING.
818	r.set_varying (type);
819	}
820	else
821	{
822	// If both bounds either underflowed or overflowed, then the result
823	// is undefined.
824	if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
825	|| (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
826	{
827	r.set_undefined ();
828	return;
829	}
830
831	// If overflow does not wrap, saturate to [MIN, MAX].
832	wide_int new_lb, new_ub;
833	if (min_ovf == wi::OVF_UNDERFLOW)
834	new_lb = wi::min_value (prec, sgn);
835	else if (min_ovf == wi::OVF_OVERFLOW)
836	new_lb = wi::max_value (prec, sgn);
837	else
838	new_lb = wmin;
839
840	if (max_ovf == wi::OVF_UNDERFLOW)
841	new_ub = wi::min_value (prec, sgn);
842	else if (max_ovf == wi::OVF_OVERFLOW)
843	new_ub = wi::max_value (prec, sgn);
844	else
845	new_ub = wmax;
846
847	r.set (type, new_lb, new_ub);
848	}
849	}
850
851	// Create and return a range from a pair of wide-ints. Canonicalize
852	// the case where the bounds are swapped. In which case, we transform
853	// [10,5] into [MIN,5][10,MAX].
854
855	static inline void
856	create_possibly_reversed_range (irange &r, tree type,
857	const wide_int &new_lb, const wide_int &new_ub)
858	{
859	signop s = TYPE_SIGN (type);
860	// If the bounds are swapped, treat the result as if an overflow occurred.
861	if (wi::gt_p (x: new_lb, y: new_ub, sgn: s))
862	value_range_from_overflowed_bounds (r, type, wmin: new_lb, wmax: new_ub);
863	else
864	// Otherwise it's just a normal range.
865	r.set (type, new_lb, new_ub);
866	}
867
868	// Return the summary information about boolean range LHS. If EMPTY/FULL,
869	// return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
870
871	bool_range_state
872	get_bool_state (vrange &r, const vrange &lhs, tree val_type)
873	{
874	// If there is no result, then this is unexecutable.
875	if (lhs.undefined_p ())
876	{
877	r.set_undefined ();
878	return BRS_EMPTY;
879	}
880
881	if (lhs.zero_p ())
882	return BRS_FALSE;
883
884	// For TRUE, we can't just test for [1,1] because Ada can have
885	// multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
886	if (lhs.contains_p (cst: build_zero_cst (lhs.type ())))
887	{
888	r.set_varying (val_type);
889	return BRS_FULL;
890	}
891
892	return BRS_TRUE;
893	}
894
895	// ------------------------------------------------------------------------
896
897	void
898	operator_equal::update_bitmask (irange &r, const irange &lh,
899	const irange &rh) const
900	{
901	update_known_bitmask (r, code: EQ_EXPR, lh, rh);
902	}
903
904	// Check if the LHS range indicates a relation between OP1 and OP2.
905
906	relation_kind
907	operator_equal::op1_op2_relation (const irange &lhs, const irange &,
908	const irange &) const
909	{
910	if (lhs.undefined_p ())
911	return VREL_UNDEFINED;
912
913	// FALSE = op1 == op2 indicates NE_EXPR.
914	if (lhs.zero_p ())
915	return VREL_NE;
916
917	// TRUE = op1 == op2 indicates EQ_EXPR.
918	if (!contains_zero_p (r: lhs))
919	return VREL_EQ;
920	return VREL_VARYING;
921	}
922
923	bool
924	operator_equal::fold_range (irange &r, tree type,
925	const irange &op1,
926	const irange &op2,
927	relation_trio rel) const
928	{
929	if (relop_early_resolve (r, type, op1, op2, trio: rel, my_rel: VREL_EQ))
930	return true;
931
932	// We can be sure the values are always equal or not if both ranges
933	// consist of a single value, and then compare them.
934	bool op1_const = wi::eq_p (x: op1.lower_bound (), y: op1.upper_bound ());
935	bool op2_const = wi::eq_p (x: op2.lower_bound (), y: op2.upper_bound ());
936	if (op1_const && op2_const)
937	{
938	if (wi::eq_p (x: op1.lower_bound (), y: op2.upper_bound()))
939	r = range_true (type);
940	else
941	r = range_false (type);
942	}
943	else
944	{
945	// If ranges do not intersect, we know the range is not equal,
946	// otherwise we don't know anything for sure.
947	int_range_max tmp = op1;
948	tmp.intersect (op2);
949	if (tmp.undefined_p ())
950	r = range_false (type);
951	// Check if a constant cannot satisfy the bitmask requirements.
952	else if (op2_const && !op1.get_bitmask ().member_p (val: op2.lower_bound ()))
953	r = range_false (type);
954	else if (op1_const && !op2.get_bitmask ().member_p (val: op1.lower_bound ()))
955	r = range_false (type);
956	else
957	r = range_true_and_false (type);
958	}
959	return true;
960	}
961
962	bool
963	operator_equal::op1_range (irange &r, tree type,
964	const irange &lhs,
965	const irange &op2,
966	relation_trio) const
967	{
968	switch (get_bool_state (r, lhs, val_type: type))
969	{
970	case BRS_TRUE:
971	// If it's true, the result is the same as OP2.
972	r = op2;
973	break;
974
975	case BRS_FALSE:
976	// If the result is false, the only time we know anything is
977	// if OP2 is a constant.
978	if (!op2.undefined_p ()
979	&& wi::eq_p (x: op2.lower_bound(), y: op2.upper_bound()))
980	{
981	r = op2;
982	r.invert ();
983	}
984	else
985	r.set_varying (type);
986	break;
987
988	default:
989	break;
990	}
991	return true;
992	}
993
994	bool
995	operator_equal::op2_range (irange &r, tree type,
996	const irange &lhs,
997	const irange &op1,
998	relation_trio rel) const
999	{
1000	return operator_equal::op1_range (r, type, lhs, op2: op1, rel.swap_op1_op2 ());
1001	}
1002
1003	// -------------------------------------------------------------------------
1004
1005	void
1006	operator_not_equal::update_bitmask (irange &r, const irange &lh,
1007	const irange &rh) const
1008	{
1009	update_known_bitmask (r, code: NE_EXPR, lh, rh);
1010	}
1011
1012	// Check if the LHS range indicates a relation between OP1 and OP2.
1013
1014	relation_kind
1015	operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1016	const irange &) const
1017	{
1018	if (lhs.undefined_p ())
1019	return VREL_UNDEFINED;
1020
1021	// FALSE = op1 != op2 indicates EQ_EXPR.
1022	if (lhs.zero_p ())
1023	return VREL_EQ;
1024
1025	// TRUE = op1 != op2 indicates NE_EXPR.
1026	if (!contains_zero_p (r: lhs))
1027	return VREL_NE;
1028	return VREL_VARYING;
1029	}
1030
1031	bool
1032	operator_not_equal::fold_range (irange &r, tree type,
1033	const irange &op1,
1034	const irange &op2,
1035	relation_trio rel) const
1036	{
1037	if (relop_early_resolve (r, type, op1, op2, trio: rel, my_rel: VREL_NE))
1038	return true;
1039
1040	// We can be sure the values are always equal or not if both ranges
1041	// consist of a single value, and then compare them.
1042	bool op1_const = wi::eq_p (x: op1.lower_bound (), y: op1.upper_bound ());
1043	bool op2_const = wi::eq_p (x: op2.lower_bound (), y: op2.upper_bound ());
1044	if (op1_const && op2_const)
1045	{
1046	if (wi::ne_p (x: op1.lower_bound (), y: op2.upper_bound()))
1047	r = range_true (type);
1048	else
1049	r = range_false (type);
1050	}
1051	else
1052	{
1053	// If ranges do not intersect, we know the range is not equal,
1054	// otherwise we don't know anything for sure.
1055	int_range_max tmp = op1;
1056	tmp.intersect (op2);
1057	if (tmp.undefined_p ())
1058	r = range_true (type);
1059	// Check if a constant cannot satisfy the bitmask requirements.
1060	else if (op2_const && !op1.get_bitmask ().member_p (val: op2.lower_bound ()))
1061	r = range_true (type);
1062	else if (op1_const && !op2.get_bitmask ().member_p (val: op1.lower_bound ()))
1063	r = range_true (type);
1064	else
1065	r = range_true_and_false (type);
1066	}
1067	return true;
1068	}
1069
1070	bool
1071	operator_not_equal::op1_range (irange &r, tree type,
1072	const irange &lhs,
1073	const irange &op2,
1074	relation_trio) const
1075	{
1076	switch (get_bool_state (r, lhs, val_type: type))
1077	{
1078	case BRS_TRUE:
1079	// If the result is true, the only time we know anything is if
1080	// OP2 is a constant.
1081	if (!op2.undefined_p ()
1082	&& wi::eq_p (x: op2.lower_bound(), y: op2.upper_bound()))
1083	{
1084	r = op2;
1085	r.invert ();
1086	}
1087	else
1088	r.set_varying (type);
1089	break;
1090
1091	case BRS_FALSE:
1092	// If it's false, the result is the same as OP2.
1093	r = op2;
1094	break;
1095
1096	default:
1097	break;
1098	}
1099	return true;
1100	}
1101
1102
1103	bool
1104	operator_not_equal::op2_range (irange &r, tree type,
1105	const irange &lhs,
1106	const irange &op1,
1107	relation_trio rel) const
1108	{
1109	return operator_not_equal::op1_range (r, type, lhs, op2: op1, rel.swap_op1_op2 ());
1110	}
1111
1112	// (X < VAL) produces the range of [MIN, VAL - 1].
1113
1114	static void
1115	build_lt (irange &r, tree type, const wide_int &val)
1116	{
1117	wi::overflow_type ov;
1118	wide_int lim;
1119	signop sgn = TYPE_SIGN (type);
1120
1121	// Signed 1 bit cannot represent 1 for subtraction.
1122	if (sgn == SIGNED)
1123	lim = wi::add (x: val, y: -1, sgn, overflow: &ov);
1124	else
1125	lim = wi::sub (x: val, y: 1, sgn, overflow: &ov);
1126
1127	// If val - 1 underflows, check if X < MIN, which is an empty range.
1128	if (ov)
1129	r.set_undefined ();
1130	else
1131	r = int_range<1> (type, min_limit (type), lim);
1132	}
1133
1134	// (X <= VAL) produces the range of [MIN, VAL].
1135
1136	static void
1137	build_le (irange &r, tree type, const wide_int &val)
1138	{
1139	r = int_range<1> (type, min_limit (type), val);
1140	}
1141
1142	// (X > VAL) produces the range of [VAL + 1, MAX].
1143
1144	static void
1145	build_gt (irange &r, tree type, const wide_int &val)
1146	{
1147	wi::overflow_type ov;
1148	wide_int lim;
1149	signop sgn = TYPE_SIGN (type);
1150
1151	// Signed 1 bit cannot represent 1 for addition.
1152	if (sgn == SIGNED)
1153	lim = wi::sub (x: val, y: -1, sgn, overflow: &ov);
1154	else
1155	lim = wi::add (x: val, y: 1, sgn, overflow: &ov);
1156	// If val + 1 overflows, check is for X > MAX, which is an empty range.
1157	if (ov)
1158	r.set_undefined ();
1159	else
1160	r = int_range<1> (type, lim, max_limit (type));
1161	}
1162
1163	// (X >= val) produces the range of [VAL, MAX].
1164
1165	static void
1166	build_ge (irange &r, tree type, const wide_int &val)
1167	{
1168	r = int_range<1> (type, val, max_limit (type));
1169	}
1170
1171
1172	void
1173	operator_lt::update_bitmask (irange &r, const irange &lh,
1174	const irange &rh) const
1175	{
1176	update_known_bitmask (r, code: LT_EXPR, lh, rh);
1177	}
1178
1179	// Check if the LHS range indicates a relation between OP1 and OP2.
1180
1181	relation_kind
1182	operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1183	const irange &) const
1184	{
1185	if (lhs.undefined_p ())
1186	return VREL_UNDEFINED;
1187
1188	// FALSE = op1 < op2 indicates GE_EXPR.
1189	if (lhs.zero_p ())
1190	return VREL_GE;
1191
1192	// TRUE = op1 < op2 indicates LT_EXPR.
1193	if (!contains_zero_p (r: lhs))
1194	return VREL_LT;
1195	return VREL_VARYING;
1196	}
1197
1198	bool
1199	operator_lt::fold_range (irange &r, tree type,
1200	const irange &op1,
1201	const irange &op2,
1202	relation_trio rel) const
1203	{
1204	if (relop_early_resolve (r, type, op1, op2, trio: rel, my_rel: VREL_LT))
1205	return true;
1206
1207	signop sign = TYPE_SIGN (op1.type ());
1208	gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1209
1210	if (wi::lt_p (x: op1.upper_bound (), y: op2.lower_bound (), sgn: sign))
1211	r = range_true (type);
1212	else if (!wi::lt_p (x: op1.lower_bound (), y: op2.upper_bound (), sgn: sign))
1213	r = range_false (type);
1214	// Use nonzero bits to determine if < 0 is false.
1215	else if (op2.zero_p () && !wi::neg_p (x: op1.get_nonzero_bits (), sgn: sign))
1216	r = range_false (type);
1217	else
1218	r = range_true_and_false (type);
1219	return true;
1220	}
1221
1222	bool
1223	operator_lt::op1_range (irange &r, tree type,
1224	const irange &lhs,
1225	const irange &op2,
1226	relation_trio) const
1227	{
1228	if (op2.undefined_p ())
1229	return false;
1230
1231	switch (get_bool_state (r, lhs, val_type: type))
1232	{
1233	case BRS_TRUE:
1234	build_lt (r, type, val: op2.upper_bound ());
1235	break;
1236
1237	case BRS_FALSE:
1238	build_ge (r, type, val: op2.lower_bound ());
1239	break;
1240
1241	default:
1242	break;
1243	}
1244	return true;
1245	}
1246
1247	bool
1248	operator_lt::op2_range (irange &r, tree type,
1249	const irange &lhs,
1250	const irange &op1,
1251	relation_trio) const
1252	{
1253	if (op1.undefined_p ())
1254	return false;
1255
1256	switch (get_bool_state (r, lhs, val_type: type))
1257	{
1258	case BRS_TRUE:
1259	build_gt (r, type, val: op1.lower_bound ());
1260	break;
1261
1262	case BRS_FALSE:
1263	build_le (r, type, val: op1.upper_bound ());
1264	break;
1265
1266	default:
1267	break;
1268	}
1269	return true;
1270	}
1271
1272
1273	void
1274	operator_le::update_bitmask (irange &r, const irange &lh,
1275	const irange &rh) const
1276	{
1277	update_known_bitmask (r, code: LE_EXPR, lh, rh);
1278	}
1279
1280	// Check if the LHS range indicates a relation between OP1 and OP2.
1281
1282	relation_kind
1283	operator_le::op1_op2_relation (const irange &lhs, const irange &,
1284	const irange &) const
1285	{
1286	if (lhs.undefined_p ())
1287	return VREL_UNDEFINED;
1288
1289	// FALSE = op1 <= op2 indicates GT_EXPR.
1290	if (lhs.zero_p ())
1291	return VREL_GT;
1292
1293	// TRUE = op1 <= op2 indicates LE_EXPR.
1294	if (!contains_zero_p (r: lhs))
1295	return VREL_LE;
1296	return VREL_VARYING;
1297	}
1298
1299	bool
1300	operator_le::fold_range (irange &r, tree type,
1301	const irange &op1,
1302	const irange &op2,
1303	relation_trio rel) const
1304	{
1305	if (relop_early_resolve (r, type, op1, op2, trio: rel, my_rel: VREL_LE))
1306	return true;
1307
1308	signop sign = TYPE_SIGN (op1.type ());
1309	gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1310
1311	if (wi::le_p (x: op1.upper_bound (), y: op2.lower_bound (), sgn: sign))
1312	r = range_true (type);
1313	else if (!wi::le_p (x: op1.lower_bound (), y: op2.upper_bound (), sgn: sign))
1314	r = range_false (type);
1315	else
1316	r = range_true_and_false (type);
1317	return true;
1318	}
1319
1320	bool
1321	operator_le::op1_range (irange &r, tree type,
1322	const irange &lhs,
1323	const irange &op2,
1324	relation_trio) const
1325	{
1326	if (op2.undefined_p ())
1327	return false;
1328
1329	switch (get_bool_state (r, lhs, val_type: type))
1330	{
1331	case BRS_TRUE:
1332	build_le (r, type, val: op2.upper_bound ());
1333	break;
1334
1335	case BRS_FALSE:
1336	build_gt (r, type, val: op2.lower_bound ());
1337	break;
1338
1339	default:
1340	break;
1341	}
1342	return true;
1343	}
1344
1345	bool
1346	operator_le::op2_range (irange &r, tree type,
1347	const irange &lhs,
1348	const irange &op1,
1349	relation_trio) const
1350	{
1351	if (op1.undefined_p ())
1352	return false;
1353
1354	switch (get_bool_state (r, lhs, val_type: type))
1355	{
1356	case BRS_TRUE:
1357	build_ge (r, type, val: op1.lower_bound ());
1358	break;
1359
1360	case BRS_FALSE:
1361	build_lt (r, type, val: op1.upper_bound ());
1362	break;
1363
1364	default:
1365	break;
1366	}
1367	return true;
1368	}
1369
1370
1371	void
1372	operator_gt::update_bitmask (irange &r, const irange &lh,
1373	const irange &rh) const
1374	{
1375	update_known_bitmask (r, code: GT_EXPR, lh, rh);
1376	}
1377
1378	// Check if the LHS range indicates a relation between OP1 and OP2.
1379
1380	relation_kind
1381	operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1382	const irange &) const
1383	{
1384	if (lhs.undefined_p ())
1385	return VREL_UNDEFINED;
1386
1387	// FALSE = op1 > op2 indicates LE_EXPR.
1388	if (lhs.zero_p ())
1389	return VREL_LE;
1390
1391	// TRUE = op1 > op2 indicates GT_EXPR.
1392	if (!contains_zero_p (r: lhs))
1393	return VREL_GT;
1394	return VREL_VARYING;
1395	}
1396
1397	bool
1398	operator_gt::fold_range (irange &r, tree type,
1399	const irange &op1, const irange &op2,
1400	relation_trio rel) const
1401	{
1402	if (relop_early_resolve (r, type, op1, op2, trio: rel, my_rel: VREL_GT))
1403	return true;
1404
1405	signop sign = TYPE_SIGN (op1.type ());
1406	gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1407
1408	if (wi::gt_p (x: op1.lower_bound (), y: op2.upper_bound (), sgn: sign))
1409	r = range_true (type);
1410	else if (!wi::gt_p (x: op1.upper_bound (), y: op2.lower_bound (), sgn: sign))
1411	r = range_false (type);
1412	else
1413	r = range_true_and_false (type);
1414	return true;
1415	}
1416
1417	bool
1418	operator_gt::op1_range (irange &r, tree type,
1419	const irange &lhs, const irange &op2,
1420	relation_trio) const
1421	{
1422	if (op2.undefined_p ())
1423	return false;
1424
1425	switch (get_bool_state (r, lhs, val_type: type))
1426	{
1427	case BRS_TRUE:
1428	build_gt (r, type, val: op2.lower_bound ());
1429	break;
1430
1431	case BRS_FALSE:
1432	build_le (r, type, val: op2.upper_bound ());
1433	break;
1434
1435	default:
1436	break;
1437	}
1438	return true;
1439	}
1440
1441	bool
1442	operator_gt::op2_range (irange &r, tree type,
1443	const irange &lhs,
1444	const irange &op1,
1445	relation_trio) const
1446	{
1447	if (op1.undefined_p ())
1448	return false;
1449
1450	switch (get_bool_state (r, lhs, val_type: type))
1451	{
1452	case BRS_TRUE:
1453	build_lt (r, type, val: op1.upper_bound ());
1454	break;
1455
1456	case BRS_FALSE:
1457	build_ge (r, type, val: op1.lower_bound ());
1458	break;
1459
1460	default:
1461	break;
1462	}
1463	return true;
1464	}
1465
1466
1467	void
1468	operator_ge::update_bitmask (irange &r, const irange &lh,
1469	const irange &rh) const
1470	{
1471	update_known_bitmask (r, code: GE_EXPR, lh, rh);
1472	}
1473
1474	// Check if the LHS range indicates a relation between OP1 and OP2.
1475
1476	relation_kind
1477	operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1478	const irange &) const
1479	{
1480	if (lhs.undefined_p ())
1481	return VREL_UNDEFINED;
1482
1483	// FALSE = op1 >= op2 indicates LT_EXPR.
1484	if (lhs.zero_p ())
1485	return VREL_LT;
1486
1487	// TRUE = op1 >= op2 indicates GE_EXPR.
1488	if (!contains_zero_p (r: lhs))
1489	return VREL_GE;
1490	return VREL_VARYING;
1491	}
1492
1493	bool
1494	operator_ge::fold_range (irange &r, tree type,
1495	const irange &op1,
1496	const irange &op2,
1497	relation_trio rel) const
1498	{
1499	if (relop_early_resolve (r, type, op1, op2, trio: rel, my_rel: VREL_GE))
1500	return true;
1501
1502	signop sign = TYPE_SIGN (op1.type ());
1503	gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1504
1505	if (wi::ge_p (x: op1.lower_bound (), y: op2.upper_bound (), sgn: sign))
1506	r = range_true (type);
1507	else if (!wi::ge_p (x: op1.upper_bound (), y: op2.lower_bound (), sgn: sign))
1508	r = range_false (type);
1509	else
1510	r = range_true_and_false (type);
1511	return true;
1512	}
1513
1514	bool
1515	operator_ge::op1_range (irange &r, tree type,
1516	const irange &lhs,
1517	const irange &op2,
1518	relation_trio) const
1519	{
1520	if (op2.undefined_p ())
1521	return false;
1522
1523	switch (get_bool_state (r, lhs, val_type: type))
1524	{
1525	case BRS_TRUE:
1526	build_ge (r, type, val: op2.lower_bound ());
1527	break;
1528
1529	case BRS_FALSE:
1530	build_lt (r, type, val: op2.upper_bound ());
1531	break;
1532
1533	default:
1534	break;
1535	}
1536	return true;
1537	}
1538
1539	bool
1540	operator_ge::op2_range (irange &r, tree type,
1541	const irange &lhs,
1542	const irange &op1,
1543	relation_trio) const
1544	{
1545	if (op1.undefined_p ())
1546	return false;
1547
1548	switch (get_bool_state (r, lhs, val_type: type))
1549	{
1550	case BRS_TRUE:
1551	build_le (r, type, val: op1.upper_bound ());
1552	break;
1553
1554	case BRS_FALSE:
1555	build_gt (r, type, val: op1.lower_bound ());
1556	break;
1557
1558	default:
1559	break;
1560	}
1561	return true;
1562	}
1563
1564
1565	void
1566	operator_plus::update_bitmask (irange &r, const irange &lh,
1567	const irange &rh) const
1568	{
1569	update_known_bitmask (r, code: PLUS_EXPR, lh, rh);
1570	}
1571
1572	// Check to see if the range of OP2 indicates anything about the relation
1573	// between LHS and OP1.
1574
1575	relation_kind
1576	operator_plus::lhs_op1_relation (const irange &lhs,
1577	const irange &op1,
1578	const irange &op2,
1579	relation_kind) const
1580	{
1581	if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1582	return VREL_VARYING;
1583
1584	tree type = lhs.type ();
1585	unsigned prec = TYPE_PRECISION (type);
1586	wi::overflow_type ovf1, ovf2;
1587	signop sign = TYPE_SIGN (type);
1588
1589	// LHS = OP1 + 0 indicates LHS == OP1.
1590	if (op2.zero_p ())
1591	return VREL_EQ;
1592
1593	if (TYPE_OVERFLOW_WRAPS (type))
1594	{
1595	wi::add (x: op1.lower_bound (), y: op2.lower_bound (), sgn: sign, overflow: &ovf1);
1596	wi::add (x: op1.upper_bound (), y: op2.upper_bound (), sgn: sign, overflow: &ovf2);
1597	}
1598	else
1599	ovf1 = ovf2 = wi::OVF_NONE;
1600
1601	// Never wrapping additions.
1602	if (!ovf1 && !ovf2)
1603	{
1604	// Positive op2 means lhs > op1.
1605	if (wi::gt_p (x: op2.lower_bound (), y: wi::zero (precision: prec), sgn: sign))
1606	return VREL_GT;
1607	if (wi::ge_p (x: op2.lower_bound (), y: wi::zero (precision: prec), sgn: sign))
1608	return VREL_GE;
1609
1610	// Negative op2 means lhs < op1.
1611	if (wi::lt_p (x: op2.upper_bound (), y: wi::zero (precision: prec), sgn: sign))
1612	return VREL_LT;
1613	if (wi::le_p (x: op2.upper_bound (), y: wi::zero (precision: prec), sgn: sign))
1614	return VREL_LE;
1615	}
1616	// Always wrapping additions.
1617	else if (ovf1 && ovf1 == ovf2)
1618	{
1619	// Positive op2 means lhs < op1.
1620	if (wi::gt_p (x: op2.lower_bound (), y: wi::zero (precision: prec), sgn: sign))
1621	return VREL_LT;
1622	if (wi::ge_p (x: op2.lower_bound (), y: wi::zero (precision: prec), sgn: sign))
1623	return VREL_LE;
1624
1625	// Negative op2 means lhs > op1.
1626	if (wi::lt_p (x: op2.upper_bound (), y: wi::zero (precision: prec), sgn: sign))
1627	return VREL_GT;
1628	if (wi::le_p (x: op2.upper_bound (), y: wi::zero (precision: prec), sgn: sign))
1629	return VREL_GE;
1630	}
1631
1632	// If op2 does not contain 0, then LHS and OP1 can never be equal.
1633	if (!range_includes_zero_p (vr: &op2))
1634	return VREL_NE;
1635
1636	return VREL_VARYING;
1637	}
1638
1639	// PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1640	// operands.
1641
1642	relation_kind
1643	operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1644	const irange &op2, relation_kind rel) const
1645	{
1646	return lhs_op1_relation (lhs, op1: op2, op2: op1, rel);
1647	}
1648
1649	void
1650	operator_plus::wi_fold (irange &r, tree type,
1651	const wide_int &lh_lb, const wide_int &lh_ub,
1652	const wide_int &rh_lb, const wide_int &rh_ub) const
1653	{
1654	wi::overflow_type ov_lb, ov_ub;
1655	signop s = TYPE_SIGN (type);
1656	wide_int new_lb = wi::add (x: lh_lb, y: rh_lb, sgn: s, overflow: &ov_lb);
1657	wide_int new_ub = wi::add (x: lh_ub, y: rh_ub, sgn: s, overflow: &ov_ub);
1658	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub, min_ovf: ov_lb, max_ovf: ov_ub);
1659	}
1660
1661	// Given addition or subtraction, determine the possible NORMAL ranges and
1662	// OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1663	// Return the relation that exists between the LHS and OP1 in order for the
1664	// NORMAL range to apply.
1665	// a return value of VREL_VARYING means no ranges were applicable.
1666
1667	static relation_kind
1668	plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1669	bool add_p)
1670	{
1671	relation_kind kind = VREL_VARYING;
1672	// For now, only deal with constant adds. This could be extended to ranges
1673	// when someone is so motivated.
1674	if (!offset.singleton_p () || offset.zero_p ())
1675	return kind;
1676
1677	// Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1678	wide_int off = offset.lower_bound ();
1679	if (wi::neg_p (x: off, sgn: SIGNED))
1680	{
1681	add_p = !add_p;
1682	off = wi::neg (x: off);
1683	}
1684
1685	wi::overflow_type ov;
1686	tree type = offset.type ();
1687	unsigned prec = TYPE_PRECISION (type);
1688	wide_int ub;
1689	wide_int lb;
1690	// calculate the normal range and relation for the operation.
1691	if (add_p)
1692	{
1693	// [ 0 , INF - OFF]
1694	lb = wi::zero (precision: prec);
1695	ub = wi::sub (x: irange_val_max (type), y: off, sgn: UNSIGNED, overflow: &ov);
1696	kind = VREL_GT;
1697	}
1698	else
1699	{
1700	// [ OFF, INF ]
1701	lb = off;
1702	ub = irange_val_max (type);
1703	kind = VREL_LT;
1704	}
1705	int_range<2> normal_range (type, lb, ub);
1706	int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1707
1708	r_ov = ov_range;
1709	r_normal = normal_range;
1710	return kind;
1711	}
1712
1713	// Once op1 has been calculated by operator_plus or operator_minus, check
1714	// to see if the relation passed causes any part of the calculation to
1715	// be not possible. ie
1716	// a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1717	// and that further refines a_2 to [0, 0].
1718	// R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1719	// relation between LHS relation OP1 and ADD_P is true for PLUS, false for
1720	// MINUS. IF any adjustment can be made, R will reflect it.
1721
1722	static void
1723	adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1724	bool add_p)
1725	{
1726	if (r.undefined_p ())
1727	return;
1728	tree type = r.type ();
1729	// Check for unsigned overflow and calculate the overflow part.
1730	signop s = TYPE_SIGN (type);
1731	if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1732	return;
1733
1734	// Only work with <, <=, >, >= relations.
1735	if (!relation_lt_le_gt_ge_p (r: rel))
1736	return;
1737
1738	// Get the ranges for this offset.
1739	int_range_max normal, overflow;
1740	relation_kind k = plus_minus_ranges (r_ov&: overflow, r_normal&: normal, offset: op2, add_p);
1741
1742	// VREL_VARYING means there are no adjustments.
1743	if (k == VREL_VARYING)
1744	return;
1745
1746	// If the relations match use the normal range, otherwise use overflow range.
1747	if (relation_intersect (r1: k, r2: rel) == k)
1748	r.intersect (normal);
1749	else
1750	r.intersect (overflow);
1751	return;
1752	}
1753
1754	bool
1755	operator_plus::op1_range (irange &r, tree type,
1756	const irange &lhs,
1757	const irange &op2,
1758	relation_trio trio) const
1759	{
1760	if (lhs.undefined_p ())
1761	return false;
1762	// Start with the default operation.
1763	range_op_handler minus (MINUS_EXPR);
1764	if (!minus)
1765	return false;
1766	bool res = minus.fold_range (r, type, lh: lhs, rh: op2);
1767	relation_kind rel = trio.lhs_op1 ();
1768	// Check for a relation refinement.
1769	if (res)
1770	adjust_op1_for_overflow (r, op2, rel, add_p: true /* PLUS_EXPR */);
1771	return res;
1772	}
1773
1774	bool
1775	operator_plus::op2_range (irange &r, tree type,
1776	const irange &lhs,
1777	const irange &op1,
1778	relation_trio rel) const
1779	{
1780	return op1_range (r, type, lhs, op2: op1, trio: rel.swap_op1_op2 ());
1781	}
1782
1783	class operator_widen_plus_signed : public range_operator
1784	{
1785	public:
1786	virtual void wi_fold (irange &r, tree type,
1787	const wide_int &lh_lb,
1788	const wide_int &lh_ub,
1789	const wide_int &rh_lb,
1790	const wide_int &rh_ub) const;
1791	} op_widen_plus_signed;
1792
1793	void
1794	operator_widen_plus_signed::wi_fold (irange &r, tree type,
1795	const wide_int &lh_lb,
1796	const wide_int &lh_ub,
1797	const wide_int &rh_lb,
1798	const wide_int &rh_ub) const
1799	{
1800	wi::overflow_type ov_lb, ov_ub;
1801	signop s = TYPE_SIGN (type);
1802
1803	wide_int lh_wlb
1804	= wide_int::from (x: lh_lb, precision: wi::get_precision (x: lh_lb) * 2, sgn: SIGNED);
1805	wide_int lh_wub
1806	= wide_int::from (x: lh_ub, precision: wi::get_precision (x: lh_ub) * 2, sgn: SIGNED);
1807	wide_int rh_wlb = wide_int::from (x: rh_lb, precision: wi::get_precision (x: rh_lb) * 2, sgn: s);
1808	wide_int rh_wub = wide_int::from (x: rh_ub, precision: wi::get_precision (x: rh_ub) * 2, sgn: s);
1809
1810	wide_int new_lb = wi::add (x: lh_wlb, y: rh_wlb, sgn: s, overflow: &ov_lb);
1811	wide_int new_ub = wi::add (x: lh_wub, y: rh_wub, sgn: s, overflow: &ov_ub);
1812
1813	r = int_range<2> (type, new_lb, new_ub);
1814	}
1815
1816	class operator_widen_plus_unsigned : public range_operator
1817	{
1818	public:
1819	virtual void wi_fold (irange &r, tree type,
1820	const wide_int &lh_lb,
1821	const wide_int &lh_ub,
1822	const wide_int &rh_lb,
1823	const wide_int &rh_ub) const;
1824	} op_widen_plus_unsigned;
1825
1826	void
1827	operator_widen_plus_unsigned::wi_fold (irange &r, tree type,
1828	const wide_int &lh_lb,
1829	const wide_int &lh_ub,
1830	const wide_int &rh_lb,
1831	const wide_int &rh_ub) const
1832	{
1833	wi::overflow_type ov_lb, ov_ub;
1834	signop s = TYPE_SIGN (type);
1835
1836	wide_int lh_wlb
1837	= wide_int::from (x: lh_lb, precision: wi::get_precision (x: lh_lb) * 2, sgn: UNSIGNED);
1838	wide_int lh_wub
1839	= wide_int::from (x: lh_ub, precision: wi::get_precision (x: lh_ub) * 2, sgn: UNSIGNED);
1840	wide_int rh_wlb = wide_int::from (x: rh_lb, precision: wi::get_precision (x: rh_lb) * 2, sgn: s);
1841	wide_int rh_wub = wide_int::from (x: rh_ub, precision: wi::get_precision (x: rh_ub) * 2, sgn: s);
1842
1843	wide_int new_lb = wi::add (x: lh_wlb, y: rh_wlb, sgn: s, overflow: &ov_lb);
1844	wide_int new_ub = wi::add (x: lh_wub, y: rh_wub, sgn: s, overflow: &ov_ub);
1845
1846	r = int_range<2> (type, new_lb, new_ub);
1847	}
1848
1849	void
1850	operator_minus::update_bitmask (irange &r, const irange &lh,
1851	const irange &rh) const
1852	{
1853	update_known_bitmask (r, code: MINUS_EXPR, lh, rh);
1854	}
1855
1856	void
1857	operator_minus::wi_fold (irange &r, tree type,
1858	const wide_int &lh_lb, const wide_int &lh_ub,
1859	const wide_int &rh_lb, const wide_int &rh_ub) const
1860	{
1861	wi::overflow_type ov_lb, ov_ub;
1862	signop s = TYPE_SIGN (type);
1863	wide_int new_lb = wi::sub (x: lh_lb, y: rh_ub, sgn: s, overflow: &ov_lb);
1864	wide_int new_ub = wi::sub (x: lh_ub, y: rh_lb, sgn: s, overflow: &ov_ub);
1865	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub, min_ovf: ov_lb, max_ovf: ov_ub);
1866	}
1867
1868
1869	// Return the relation between LHS and OP1 based on the relation between
1870	// OP1 and OP2.
1871
1872	relation_kind
1873	operator_minus::lhs_op1_relation (const irange &, const irange &op1,
1874	const irange &, relation_kind rel) const
1875	{
1876	if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
1877	switch (rel)
1878	{
1879	case VREL_GT:
1880	case VREL_GE:
1881	return VREL_LE;
1882	default:
1883	break;
1884	}
1885	return VREL_VARYING;
1886	}
1887
1888	// Check to see if the relation REL between OP1 and OP2 has any effect on the
1889	// LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
1890	// function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1891
1892	bool
1893	minus_op1_op2_relation_effect (irange &lhs_range, tree type,
1894	const irange &op1_range ATTRIBUTE_UNUSED,
1895	const irange &op2_range ATTRIBUTE_UNUSED,
1896	relation_kind rel)
1897	{
1898	if (rel == VREL_VARYING)
1899	return false;
1900
1901	int_range<2> rel_range;
1902	unsigned prec = TYPE_PRECISION (type);
1903	signop sgn = TYPE_SIGN (type);
1904
1905	// == and != produce [0,0] and ~[0,0] regardless of wrapping.
1906	if (rel == VREL_EQ)
1907	rel_range = int_range<2> (type, wi::zero (precision: prec), wi::zero (precision: prec));
1908	else if (rel == VREL_NE)
1909	rel_range = int_range<2> (type, wi::zero (precision: prec), wi::zero (precision: prec),
1910	VR_ANTI_RANGE);
1911	else if (TYPE_OVERFLOW_WRAPS (type))
1912	{
1913	switch (rel)
1914	{
1915	// For wrapping signed values and unsigned, if op1 > op2 or
1916	// op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1917	case VREL_GT:
1918	case VREL_LT:
1919	rel_range = int_range<2> (type, wi::zero (precision: prec), wi::zero (precision: prec),
1920	VR_ANTI_RANGE);
1921	break;
1922	default:
1923	return false;
1924	}
1925	}
1926	else
1927	{
1928	switch (rel)
1929	{
1930	// op1 > op2, op1 - op2 can be restricted to [1, +INF]
1931	case VREL_GT:
1932	rel_range = int_range<2> (type, wi::one (precision: prec),
1933	wi::max_value (prec, sgn));
1934	break;
1935	// op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1936	case VREL_GE:
1937	rel_range = int_range<2> (type, wi::zero (precision: prec),
1938	wi::max_value (prec, sgn));
1939	break;
1940	// op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1941	case VREL_LT:
1942	rel_range = int_range<2> (type, wi::min_value (prec, sgn),
1943	wi::minus_one (precision: prec));
1944	break;
1945	// op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1946	case VREL_LE:
1947	rel_range = int_range<2> (type, wi::min_value (prec, sgn),
1948	wi::zero (precision: prec));
1949	break;
1950	default:
1951	return false;
1952	}
1953	}
1954	lhs_range.intersect (rel_range);
1955	return true;
1956	}
1957
1958	bool
1959	operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type,
1960	const irange &op1_range,
1961	const irange &op2_range,
1962	relation_kind rel) const
1963	{
1964	return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
1965	rel);
1966	}
1967
1968	bool
1969	operator_minus::op1_range (irange &r, tree type,
1970	const irange &lhs,
1971	const irange &op2,
1972	relation_trio trio) const
1973	{
1974	if (lhs.undefined_p ())
1975	return false;
1976	// Start with the default operation.
1977	range_op_handler minus (PLUS_EXPR);
1978	if (!minus)
1979	return false;
1980	bool res = minus.fold_range (r, type, lh: lhs, rh: op2);
1981	relation_kind rel = trio.lhs_op1 ();
1982	if (res)
1983	adjust_op1_for_overflow (r, op2, rel, add_p: false /* PLUS_EXPR */);
1984	return res;
1985
1986	}
1987
1988	bool
1989	operator_minus::op2_range (irange &r, tree type,
1990	const irange &lhs,
1991	const irange &op1,
1992	relation_trio) const
1993	{
1994	if (lhs.undefined_p ())
1995	return false;
1996	return fold_range (r, type, lh: op1, rh: lhs);
1997	}
1998
1999	void
2000	operator_min::update_bitmask (irange &r, const irange &lh,
2001	const irange &rh) const
2002	{
2003	update_known_bitmask (r, code: MIN_EXPR, lh, rh);
2004	}
2005
2006	void
2007	operator_min::wi_fold (irange &r, tree type,
2008	const wide_int &lh_lb, const wide_int &lh_ub,
2009	const wide_int &rh_lb, const wide_int &rh_ub) const
2010	{
2011	signop s = TYPE_SIGN (type);
2012	wide_int new_lb = wi::min (x: lh_lb, y: rh_lb, sgn: s);
2013	wide_int new_ub = wi::min (x: lh_ub, y: rh_ub, sgn: s);
2014	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub);
2015	}
2016
2017
2018	void
2019	operator_max::update_bitmask (irange &r, const irange &lh,
2020	const irange &rh) const
2021	{
2022	update_known_bitmask (r, code: MAX_EXPR, lh, rh);
2023	}
2024
2025	void
2026	operator_max::wi_fold (irange &r, tree type,
2027	const wide_int &lh_lb, const wide_int &lh_ub,
2028	const wide_int &rh_lb, const wide_int &rh_ub) const
2029	{
2030	signop s = TYPE_SIGN (type);
2031	wide_int new_lb = wi::max (x: lh_lb, y: rh_lb, sgn: s);
2032	wide_int new_ub = wi::max (x: lh_ub, y: rh_ub, sgn: s);
2033	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub);
2034	}
2035
2036
2037	// Calculate the cross product of two sets of ranges and return it.
2038	//
2039	// Multiplications, divisions and shifts are a bit tricky to handle,
2040	// depending on the mix of signs we have in the two ranges, we need to
2041	// operate on different values to get the minimum and maximum values
2042	// for the new range. One approach is to figure out all the
2043	// variations of range combinations and do the operations.
2044	//
2045	// However, this involves several calls to compare_values and it is
2046	// pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
2047	// MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
2048	// figure the smallest and largest values to form the new range.
2049
2050	void
2051	cross_product_operator::wi_cross_product (irange &r, tree type,
2052	const wide_int &lh_lb,
2053	const wide_int &lh_ub,
2054	const wide_int &rh_lb,
2055	const wide_int &rh_ub) const
2056	{
2057	wide_int cp1, cp2, cp3, cp4;
2058	// Default to varying.
2059	r.set_varying (type);
2060
2061	// Compute the 4 cross operations, bailing if we get an overflow we
2062	// can't handle.
2063	if (wi_op_overflows (r&: cp1, type, lh_lb, rh_lb))
2064	return;
2065	if (wi::eq_p (x: lh_lb, y: lh_ub))
2066	cp3 = cp1;
2067	else if (wi_op_overflows (r&: cp3, type, lh_ub, rh_lb))
2068	return;
2069	if (wi::eq_p (x: rh_lb, y: rh_ub))
2070	cp2 = cp1;
2071	else if (wi_op_overflows (r&: cp2, type, lh_lb, rh_ub))
2072	return;
2073	if (wi::eq_p (x: lh_lb, y: lh_ub))
2074	cp4 = cp2;
2075	else if (wi_op_overflows (r&: cp4, type, lh_ub, rh_ub))
2076	return;
2077
2078	// Order pairs.
2079	signop sign = TYPE_SIGN (type);
2080	if (wi::gt_p (x: cp1, y: cp2, sgn: sign))
2081	std::swap (a&: cp1, b&: cp2);
2082	if (wi::gt_p (x: cp3, y: cp4, sgn: sign))
2083	std::swap (a&: cp3, b&: cp4);
2084
2085	// Choose min and max from the ordered pairs.
2086	wide_int res_lb = wi::min (x: cp1, y: cp3, sgn: sign);
2087	wide_int res_ub = wi::max (x: cp2, y: cp4, sgn: sign);
2088	value_range_with_overflow (r, type, wmin: res_lb, wmax: res_ub);
2089	}
2090
2091
2092	void
2093	operator_mult::update_bitmask (irange &r, const irange &lh,
2094	const irange &rh) const
2095	{
2096	update_known_bitmask (r, code: MULT_EXPR, lh, rh);
2097	}
2098
2099	bool
2100	operator_mult::op1_range (irange &r, tree type,
2101	const irange &lhs, const irange &op2,
2102	relation_trio) const
2103	{
2104	if (lhs.undefined_p ())
2105	return false;
2106
2107	// We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
2108	// For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
2109	// for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
2110	if (TYPE_OVERFLOW_WRAPS (type))
2111	return false;
2112
2113	wide_int offset;
2114	if (op2.singleton_p (offset) && offset != 0)
2115	return range_op_handler (TRUNC_DIV_EXPR).fold_range (r, type, lh: lhs, rh: op2);
2116	return false;
2117	}
2118
2119	bool
2120	operator_mult::op2_range (irange &r, tree type,
2121	const irange &lhs, const irange &op1,
2122	relation_trio rel) const
2123	{
2124	return operator_mult::op1_range (r, type, lhs, op2: op1, rel.swap_op1_op2 ());
2125	}
2126
2127	bool
2128	operator_mult::wi_op_overflows (wide_int &res, tree type,
2129	const wide_int &w0, const wide_int &w1) const
2130	{
2131	wi::overflow_type overflow = wi::OVF_NONE;
2132	signop sign = TYPE_SIGN (type);
2133	res = wi::mul (x: w0, y: w1, sgn: sign, overflow: &overflow);
2134	if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2135	{
2136	// For multiplication, the sign of the overflow is given
2137	// by the comparison of the signs of the operands.
2138	if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2139	res = wi::max_value (w0.get_precision (), sign);
2140	else
2141	res = wi::min_value (w0.get_precision (), sign);
2142	return false;
2143	}
2144	return overflow;
2145	}
2146
2147	void
2148	operator_mult::wi_fold (irange &r, tree type,
2149	const wide_int &lh_lb, const wide_int &lh_ub,
2150	const wide_int &rh_lb, const wide_int &rh_ub) const
2151	{
2152	if (TYPE_OVERFLOW_UNDEFINED (type))
2153	{
2154	wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2155	return;
2156	}
2157
2158	// Multiply the ranges when overflow wraps. This is basically fancy
2159	// code so we don't drop to varying with an unsigned
2160	// [-3,-1]*[-3,-1].
2161	//
2162	// This test requires 2*prec bits if both operands are signed and
2163	// 2*prec + 2 bits if either is not. Therefore, extend the values
2164	// using the sign of the result to PREC2. From here on out,
2165	// everything is just signed math no matter what the input types
2166	// were.
2167
2168	signop sign = TYPE_SIGN (type);
2169	unsigned prec = TYPE_PRECISION (type);
2170	widest2_int min0 = widest2_int::from (x: lh_lb, sgn: sign);
2171	widest2_int max0 = widest2_int::from (x: lh_ub, sgn: sign);
2172	widest2_int min1 = widest2_int::from (x: rh_lb, sgn: sign);
2173	widest2_int max1 = widest2_int::from (x: rh_ub, sgn: sign);
2174	widest2_int sizem1 = wi::mask <widest2_int> (width: prec, negate_p: false);
2175	widest2_int size = sizem1 + 1;
2176
2177	// Canonicalize the intervals.
2178	if (sign == UNSIGNED)
2179	{
2180	if (wi::ltu_p (x: size, y: min0 + max0))
2181	{
2182	min0 -= size;
2183	max0 -= size;
2184	}
2185	if (wi::ltu_p (x: size, y: min1 + max1))
2186	{
2187	min1 -= size;
2188	max1 -= size;
2189	}
2190	}
2191
2192	// Sort the 4 products so that min is in prod0 and max is in
2193	// prod3.
2194	widest2_int prod0 = min0 * min1;
2195	widest2_int prod1 = min0 * max1;
2196	widest2_int prod2 = max0 * min1;
2197	widest2_int prod3 = max0 * max1;
2198
2199	// min0min1 > max0max1
2200	if (prod0 > prod3)
2201	std::swap (a&: prod0, b&: prod3);
2202
2203	// min0max1 > max0min1
2204	if (prod1 > prod2)
2205	std::swap (a&: prod1, b&: prod2);
2206
2207	if (prod0 > prod1)
2208	std::swap (a&: prod0, b&: prod1);
2209
2210	if (prod2 > prod3)
2211	std::swap (a&: prod2, b&: prod3);
2212
2213	// diff = max - min
2214	prod2 = prod3 - prod0;
2215	if (wi::geu_p (x: prod2, y: sizem1))
2216	{
2217	// Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2218	if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2219	&& wi::exact_log2 (rh_lb) != -1 && prec > 1)
2220	{
2221	r.set (type, rh_lb, wi::max_value (prec, sign));
2222	int_range<2> zero;
2223	zero.set_zero (type);
2224	r.union_ (zero);
2225	}
2226	else
2227	// The range covers all values.
2228	r.set_varying (type);
2229	}
2230	else
2231	{
2232	wide_int new_lb = wide_int::from (x: prod0, precision: prec, sgn: sign);
2233	wide_int new_ub = wide_int::from (x: prod3, precision: prec, sgn: sign);
2234	create_possibly_reversed_range (r, type, new_lb, new_ub);
2235	}
2236	}
2237
2238	class operator_widen_mult_signed : public range_operator
2239	{
2240	public:
2241	virtual void wi_fold (irange &r, tree type,
2242	const wide_int &lh_lb,
2243	const wide_int &lh_ub,
2244	const wide_int &rh_lb,
2245	const wide_int &rh_ub)
2246	const;
2247	} op_widen_mult_signed;
2248
2249	void
2250	operator_widen_mult_signed::wi_fold (irange &r, tree type,
2251	const wide_int &lh_lb,
2252	const wide_int &lh_ub,
2253	const wide_int &rh_lb,
2254	const wide_int &rh_ub) const
2255	{
2256	signop s = TYPE_SIGN (type);
2257
2258	wide_int lh_wlb = wide_int::from (x: lh_lb, precision: wi::get_precision (x: lh_lb) * 2, sgn: SIGNED);
2259	wide_int lh_wub = wide_int::from (x: lh_ub, precision: wi::get_precision (x: lh_ub) * 2, sgn: SIGNED);
2260	wide_int rh_wlb = wide_int::from (x: rh_lb, precision: wi::get_precision (x: rh_lb) * 2, sgn: s);
2261	wide_int rh_wub = wide_int::from (x: rh_ub, precision: wi::get_precision (x: rh_ub) * 2, sgn: s);
2262
2263	/* We don't expect a widening multiplication to be able to overflow but range
2264	calculations for multiplications are complicated. After widening the
2265	operands lets call the base class. */
2266	return op_mult.wi_fold (r, type, lh_lb: lh_wlb, lh_ub: lh_wub, rh_lb: rh_wlb, rh_ub: rh_wub);
2267	}
2268
2269
2270	class operator_widen_mult_unsigned : public range_operator
2271	{
2272	public:
2273	virtual void wi_fold (irange &r, tree type,
2274	const wide_int &lh_lb,
2275	const wide_int &lh_ub,
2276	const wide_int &rh_lb,
2277	const wide_int &rh_ub)
2278	const;
2279	} op_widen_mult_unsigned;
2280
2281	void
2282	operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2283	const wide_int &lh_lb,
2284	const wide_int &lh_ub,
2285	const wide_int &rh_lb,
2286	const wide_int &rh_ub) const
2287	{
2288	signop s = TYPE_SIGN (type);
2289
2290	wide_int lh_wlb = wide_int::from (x: lh_lb, precision: wi::get_precision (x: lh_lb) * 2, sgn: UNSIGNED);
2291	wide_int lh_wub = wide_int::from (x: lh_ub, precision: wi::get_precision (x: lh_ub) * 2, sgn: UNSIGNED);
2292	wide_int rh_wlb = wide_int::from (x: rh_lb, precision: wi::get_precision (x: rh_lb) * 2, sgn: s);
2293	wide_int rh_wub = wide_int::from (x: rh_ub, precision: wi::get_precision (x: rh_ub) * 2, sgn: s);
2294
2295	/* We don't expect a widening multiplication to be able to overflow but range
2296	calculations for multiplications are complicated. After widening the
2297	operands lets call the base class. */
2298	return op_mult.wi_fold (r, type, lh_lb: lh_wlb, lh_ub: lh_wub, rh_lb: rh_wlb, rh_ub: rh_wub);
2299	}
2300
2301	class operator_div : public cross_product_operator
2302	{
2303	public:
2304	operator_div (tree_code div_kind) { m_code = div_kind; }
2305	virtual void wi_fold (irange &r, tree type,
2306	const wide_int &lh_lb,
2307	const wide_int &lh_ub,
2308	const wide_int &rh_lb,
2309	const wide_int &rh_ub) const final override;
2310	virtual bool wi_op_overflows (wide_int &res, tree type,
2311	const wide_int &, const wide_int &)
2312	const final override;
2313	void update_bitmask (irange &r, const irange &lh, const irange &rh) const
2314	{ update_known_bitmask (r, code: m_code, lh, rh); }
2315	protected:
2316	tree_code m_code;
2317	};
2318
2319	static operator_div op_trunc_div (TRUNC_DIV_EXPR);
2320	static operator_div op_floor_div (FLOOR_DIV_EXPR);
2321	static operator_div op_round_div (ROUND_DIV_EXPR);
2322	static operator_div op_ceil_div (CEIL_DIV_EXPR);
2323
2324	bool
2325	operator_div::wi_op_overflows (wide_int &res, tree type,
2326	const wide_int &w0, const wide_int &w1) const
2327	{
2328	if (w1 == 0)
2329	return true;
2330
2331	wi::overflow_type overflow = wi::OVF_NONE;
2332	signop sign = TYPE_SIGN (type);
2333
2334	switch (m_code)
2335	{
2336	case EXACT_DIV_EXPR:
2337	case TRUNC_DIV_EXPR:
2338	res = wi::div_trunc (x: w0, y: w1, sgn: sign, overflow: &overflow);
2339	break;
2340	case FLOOR_DIV_EXPR:
2341	res = wi::div_floor (x: w0, y: w1, sgn: sign, overflow: &overflow);
2342	break;
2343	case ROUND_DIV_EXPR:
2344	res = wi::div_round (x: w0, y: w1, sgn: sign, overflow: &overflow);
2345	break;
2346	case CEIL_DIV_EXPR:
2347	res = wi::div_ceil (x: w0, y: w1, sgn: sign, overflow: &overflow);
2348	break;
2349	default:
2350	gcc_unreachable ();
2351	}
2352
2353	if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2354	{
2355	// For division, the only case is -INF / -1 = +INF.
2356	res = wi::max_value (w0.get_precision (), sign);
2357	return false;
2358	}
2359	return overflow;
2360	}
2361
2362	void
2363	operator_div::wi_fold (irange &r, tree type,
2364	const wide_int &lh_lb, const wide_int &lh_ub,
2365	const wide_int &rh_lb, const wide_int &rh_ub) const
2366	{
2367	const wide_int dividend_min = lh_lb;
2368	const wide_int dividend_max = lh_ub;
2369	const wide_int divisor_min = rh_lb;
2370	const wide_int divisor_max = rh_ub;
2371	signop sign = TYPE_SIGN (type);
2372	unsigned prec = TYPE_PRECISION (type);
2373	wide_int extra_min, extra_max;
2374
2375	// If we know we won't divide by zero, just do the division.
2376	if (!wi_includes_zero_p (type, wmin: divisor_min, wmax: divisor_max))
2377	{
2378	wi_cross_product (r, type, lh_lb: dividend_min, lh_ub: dividend_max,
2379	rh_lb: divisor_min, rh_ub: divisor_max);
2380	return;
2381	}
2382
2383	// If we're definitely dividing by zero, there's nothing to do.
2384	if (wi_zero_p (type, wmin: divisor_min, wmax: divisor_max))
2385	{
2386	r.set_undefined ();
2387	return;
2388	}
2389
2390	// Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2391	// skip any division by zero.
2392
2393	// First divide by the negative numbers, if any.
2394	if (wi::neg_p (x: divisor_min, sgn: sign))
2395	wi_cross_product (r, type, lh_lb: dividend_min, lh_ub: dividend_max,
2396	rh_lb: divisor_min, rh_ub: wi::minus_one (precision: prec));
2397	else
2398	r.set_undefined ();
2399
2400	// Then divide by the non-zero positive numbers, if any.
2401	if (wi::gt_p (x: divisor_max, y: wi::zero (precision: prec), sgn: sign))
2402	{
2403	int_range_max tmp;
2404	wi_cross_product (r&: tmp, type, lh_lb: dividend_min, lh_ub: dividend_max,
2405	rh_lb: wi::one (precision: prec), rh_ub: divisor_max);
2406	r.union_ (tmp);
2407	}
2408	// We shouldn't still have undefined here.
2409	gcc_checking_assert (!r.undefined_p ());
2410	}
2411
2412
2413	class operator_exact_divide : public operator_div
2414	{
2415	using range_operator::op1_range;
2416	public:
2417	operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2418	virtual bool op1_range (irange &r, tree type,
2419	const irange &lhs,
2420	const irange &op2,
2421	relation_trio) const;
2422
2423	} op_exact_div;
2424
2425	bool
2426	operator_exact_divide::op1_range (irange &r, tree type,
2427	const irange &lhs,
2428	const irange &op2,
2429	relation_trio) const
2430	{
2431	if (lhs.undefined_p ())
2432	return false;
2433	wide_int offset;
2434	// [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2435	// remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2436	// We wont bother trying to enumerate all the in between stuff :-P
2437	// TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2438	// the time however.
2439	// If op2 is a multiple of 2, we would be able to set some non-zero bits.
2440	if (op2.singleton_p (offset) && offset != 0)
2441	return range_op_handler (MULT_EXPR).fold_range (r, type, lh: lhs, rh: op2);
2442	return false;
2443	}
2444
2445
2446	class operator_lshift : public cross_product_operator
2447	{
2448	using range_operator::fold_range;
2449	using range_operator::op1_range;
2450	public:
2451	virtual bool op1_range (irange &r, tree type, const irange &lhs,
2452	const irange &op2, relation_trio rel = TRIO_VARYING)
2453	const final override;
2454	virtual bool fold_range (irange &r, tree type, const irange &op1,
2455	const irange &op2, relation_trio rel = TRIO_VARYING)
2456	const final override;
2457
2458	virtual void wi_fold (irange &r, tree type,
2459	const wide_int &lh_lb, const wide_int &lh_ub,
2460	const wide_int &rh_lb,
2461	const wide_int &rh_ub) const final override;
2462	virtual bool wi_op_overflows (wide_int &res,
2463	tree type,
2464	const wide_int &,
2465	const wide_int &) const final override;
2466	void update_bitmask (irange &r, const irange &lh,
2467	const irange &rh) const final override
2468	{ update_known_bitmask (r, code: LSHIFT_EXPR, lh, rh); }
2469	} op_lshift;
2470
2471	class operator_rshift : public cross_product_operator
2472	{
2473	using range_operator::fold_range;
2474	using range_operator::op1_range;
2475	using range_operator::lhs_op1_relation;
2476	public:
2477	virtual bool fold_range (irange &r, tree type, const irange &op1,
2478	const irange &op2, relation_trio rel = TRIO_VARYING)
2479	const final override;
2480	virtual void wi_fold (irange &r, tree type,
2481	const wide_int &lh_lb,
2482	const wide_int &lh_ub,
2483	const wide_int &rh_lb,
2484	const wide_int &rh_ub) const final override;
2485	virtual bool wi_op_overflows (wide_int &res,
2486	tree type,
2487	const wide_int &w0,
2488	const wide_int &w1) const final override;
2489	virtual bool op1_range (irange &, tree type, const irange &lhs,
2490	const irange &op2, relation_trio rel = TRIO_VARYING)
2491	const final override;
2492	virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2493	const irange &op2, relation_kind rel)
2494	const final override;
2495	void update_bitmask (irange &r, const irange &lh,
2496	const irange &rh) const final override
2497	{ update_known_bitmask (r, code: RSHIFT_EXPR, lh, rh); }
2498	} op_rshift;
2499
2500
2501	relation_kind
2502	operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2503	const irange &op1,
2504	const irange &op2,
2505	relation_kind) const
2506	{
2507	// If both operands range are >= 0, then the LHS <= op1.
2508	if (!op1.undefined_p () && !op2.undefined_p ()
2509	&& wi::ge_p (x: op1.lower_bound (), y: 0, TYPE_SIGN (op1.type ()))
2510	&& wi::ge_p (x: op2.lower_bound (), y: 0, TYPE_SIGN (op2.type ())))
2511	return VREL_LE;
2512	return VREL_VARYING;
2513	}
2514
2515	bool
2516	operator_lshift::fold_range (irange &r, tree type,
2517	const irange &op1,
2518	const irange &op2,
2519	relation_trio rel) const
2520	{
2521	int_range_max shift_range;
2522	if (!get_shift_range (r&: shift_range, type, op: op2))
2523	{
2524	if (op2.undefined_p ())
2525	r.set_undefined ();
2526	else
2527	r.set_zero (type);
2528	return true;
2529	}
2530
2531	// Transform left shifts by constants into multiplies.
2532	if (shift_range.singleton_p ())
2533	{
2534	unsigned shift = shift_range.lower_bound ().to_uhwi ();
2535	wide_int tmp = wi::set_bit_in_zero (bit: shift, TYPE_PRECISION (type));
2536	int_range<1> mult (type, tmp, tmp);
2537
2538	// Force wrapping multiplication.
2539	bool saved_flag_wrapv = flag_wrapv;
2540	bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2541	flag_wrapv = 1;
2542	flag_wrapv_pointer = 1;
2543	bool b = op_mult.fold_range (r, type, lh: op1, rh: mult);
2544	flag_wrapv = saved_flag_wrapv;
2545	flag_wrapv_pointer = saved_flag_wrapv_pointer;
2546	return b;
2547	}
2548	else
2549	// Otherwise, invoke the generic fold routine.
2550	return range_operator::fold_range (r, type, lh: op1, rh: shift_range, trio: rel);
2551	}
2552
2553	void
2554	operator_lshift::wi_fold (irange &r, tree type,
2555	const wide_int &lh_lb, const wide_int &lh_ub,
2556	const wide_int &rh_lb, const wide_int &rh_ub) const
2557	{
2558	signop sign = TYPE_SIGN (type);
2559	unsigned prec = TYPE_PRECISION (type);
2560	int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2561	int bound_shift = overflow_pos - rh_ub.to_shwi ();
2562	// If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2563	// overflow. However, for that to happen, rh.max needs to be zero,
2564	// which means rh is a singleton range of zero, which means we simply return
2565	// [lh_lb, lh_ub] as the range.
2566	if (wi::eq_p (x: rh_ub, y: rh_lb) && wi::eq_p (x: rh_ub, y: 0))
2567	{
2568	r = int_range<2> (type, lh_lb, lh_ub);
2569	return;
2570	}
2571
2572	wide_int bound = wi::set_bit_in_zero (bit: bound_shift, precision: prec);
2573	wide_int complement = ~(bound - 1);
2574	wide_int low_bound, high_bound;
2575	bool in_bounds = false;
2576
2577	if (sign == UNSIGNED)
2578	{
2579	low_bound = bound;
2580	high_bound = complement;
2581	if (wi::ltu_p (x: lh_ub, y: low_bound))
2582	{
2583	// [5, 6] << [1, 2] == [10, 24].
2584	// We're shifting out only zeroes, the value increases
2585	// monotonically.
2586	in_bounds = true;
2587	}
2588	else if (wi::ltu_p (x: high_bound, y: lh_lb))
2589	{
2590	// [0xffffff00, 0xffffffff] << [1, 2]
2591	// == [0xfffffc00, 0xfffffffe].
2592	// We're shifting out only ones, the value decreases
2593	// monotonically.
2594	in_bounds = true;
2595	}
2596	}
2597	else
2598	{
2599	// [-1, 1] << [1, 2] == [-4, 4]
2600	low_bound = complement;
2601	high_bound = bound;
2602	if (wi::lts_p (x: lh_ub, y: high_bound)
2603	&& wi::lts_p (x: low_bound, y: lh_lb))
2604	{
2605	// For non-negative numbers, we're shifting out only zeroes,
2606	// the value increases monotonically. For negative numbers,
2607	// we're shifting out only ones, the value decreases
2608	// monotonically.
2609	in_bounds = true;
2610	}
2611	}
2612
2613	if (in_bounds)
2614	wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2615	else
2616	r.set_varying (type);
2617	}
2618
2619	bool
2620	operator_lshift::wi_op_overflows (wide_int &res, tree type,
2621	const wide_int &w0, const wide_int &w1) const
2622	{
2623	signop sign = TYPE_SIGN (type);
2624	if (wi::neg_p (x: w1))
2625	{
2626	// It's unclear from the C standard whether shifts can overflow.
2627	// The following code ignores overflow; perhaps a C standard
2628	// interpretation ruling is needed.
2629	res = wi::rshift (x: w0, y: -w1, sgn: sign);
2630	}
2631	else
2632	res = wi::lshift (x: w0, y: w1);
2633	return false;
2634	}
2635
2636	bool
2637	operator_lshift::op1_range (irange &r,
2638	tree type,
2639	const irange &lhs,
2640	const irange &op2,
2641	relation_trio) const
2642	{
2643	if (lhs.undefined_p ())
2644	return false;
2645
2646	if (!contains_zero_p (r: lhs))
2647	r.set_nonzero (type);
2648	else
2649	r.set_varying (type);
2650
2651	wide_int shift;
2652	if (op2.singleton_p (shift))
2653	{
2654	if (wi::lt_p (x: shift, y: 0, sgn: SIGNED))
2655	return false;
2656	if (wi::ge_p (x: shift, y: wi::uhwi (TYPE_PRECISION (type),
2657	TYPE_PRECISION (op2.type ())),
2658	sgn: UNSIGNED))
2659	return false;
2660	if (shift == 0)
2661	{
2662	r.intersect (lhs);
2663	return true;
2664	}
2665
2666	// Work completely in unsigned mode to start.
2667	tree utype = type;
2668	int_range_max tmp_range;
2669	if (TYPE_SIGN (type) == SIGNED)
2670	{
2671	int_range_max tmp = lhs;
2672	utype = unsigned_type_for (type);
2673	range_cast (r&: tmp, type: utype);
2674	op_rshift.fold_range (r&: tmp_range, type: utype, op1: tmp, op2);
2675	}
2676	else
2677	op_rshift.fold_range (r&: tmp_range, type: utype, op1: lhs, op2);
2678
2679	// Start with ranges which can produce the LHS by right shifting the
2680	// result by the shift amount.
2681	// ie [0x08, 0xF0] = op1 << 2 will start with
2682	// [00001000, 11110000] = op1 << 2
2683	// [0x02, 0x4C] aka [00000010, 00111100]
2684
2685	// Then create a range from the LB with the least significant upper bit
2686	// set, to the upper bound with all the bits set.
2687	// This would be [0x42, 0xFC] aka [01000010, 11111100].
2688
2689	// Ideally we do this for each subrange, but just lump them all for now.
2690	unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2691	wide_int up_mask = wi::mask (width: low_bits, negate_p: true, TYPE_PRECISION (utype));
2692	wide_int new_ub = wi::bit_or (x: up_mask, y: tmp_range.upper_bound ());
2693	wide_int new_lb = wi::set_bit (x: tmp_range.lower_bound (), bit: low_bits);
2694	int_range<2> fill_range (utype, new_lb, new_ub);
2695	tmp_range.union_ (fill_range);
2696
2697	if (utype != type)
2698	range_cast (r&: tmp_range, type);
2699
2700	r.intersect (tmp_range);
2701	return true;
2702	}
2703
2704	return !r.varying_p ();
2705	}
2706
2707	bool
2708	operator_rshift::op1_range (irange &r,
2709	tree type,
2710	const irange &lhs,
2711	const irange &op2,
2712	relation_trio) const
2713	{
2714	if (lhs.undefined_p ())
2715	return false;
2716	wide_int shift;
2717	if (op2.singleton_p (shift))
2718	{
2719	// Ignore nonsensical shifts.
2720	unsigned prec = TYPE_PRECISION (type);
2721	if (wi::ge_p (x: shift,
2722	y: wi::uhwi (val: prec, TYPE_PRECISION (op2.type ())),
2723	sgn: UNSIGNED))
2724	return false;
2725	if (shift == 0)
2726	{
2727	r = lhs;
2728	return true;
2729	}
2730
2731	// Folding the original operation may discard some impossible
2732	// ranges from the LHS.
2733	int_range_max lhs_refined;
2734	op_rshift.fold_range (r&: lhs_refined, type, op1: int_range<1> (type), op2);
2735	lhs_refined.intersect (lhs);
2736	if (lhs_refined.undefined_p ())
2737	{
2738	r.set_undefined ();
2739	return true;
2740	}
2741	int_range_max shift_range (op2.type (), shift, shift);
2742	int_range_max lb, ub;
2743	op_lshift.fold_range (r&: lb, type, op1: lhs_refined, op2: shift_range);
2744	// LHS
2745	// 0000 0111 = OP1 >> 3
2746	//
2747	// OP1 is anything from 0011 1000 to 0011 1111. That is, a
2748	// range from LHS<<3 plus a mask of the 3 bits we shifted on the
2749	// right hand side (0x07).
2750	wide_int mask = wi::bit_not (x: wi::lshift (x: wi::minus_one (precision: prec), y: shift));
2751	int_range_max mask_range (type,
2752	wi::zero (TYPE_PRECISION (type)),
2753	mask);
2754	op_plus.fold_range (r&: ub, type, lh: lb, rh: mask_range);
2755	r = lb;
2756	r.union_ (ub);
2757	if (!contains_zero_p (r: lhs_refined))
2758	{
2759	mask_range.invert ();
2760	r.intersect (mask_range);
2761	}
2762	return true;
2763	}
2764	return false;
2765	}
2766
2767	bool
2768	operator_rshift::wi_op_overflows (wide_int &res,
2769	tree type,
2770	const wide_int &w0,
2771	const wide_int &w1) const
2772	{
2773	signop sign = TYPE_SIGN (type);
2774	if (wi::neg_p (x: w1))
2775	res = wi::lshift (x: w0, y: -w1);
2776	else
2777	{
2778	// It's unclear from the C standard whether shifts can overflow.
2779	// The following code ignores overflow; perhaps a C standard
2780	// interpretation ruling is needed.
2781	res = wi::rshift (x: w0, y: w1, sgn: sign);
2782	}
2783	return false;
2784	}
2785
2786	bool
2787	operator_rshift::fold_range (irange &r, tree type,
2788	const irange &op1,
2789	const irange &op2,
2790	relation_trio rel) const
2791	{
2792	int_range_max shift;
2793	if (!get_shift_range (r&: shift, type, op: op2))
2794	{
2795	if (op2.undefined_p ())
2796	r.set_undefined ();
2797	else
2798	r.set_zero (type);
2799	return true;
2800	}
2801
2802	return range_operator::fold_range (r, type, lh: op1, rh: shift, trio: rel);
2803	}
2804
2805	void
2806	operator_rshift::wi_fold (irange &r, tree type,
2807	const wide_int &lh_lb, const wide_int &lh_ub,
2808	const wide_int &rh_lb, const wide_int &rh_ub) const
2809	{
2810	wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2811	}
2812
2813
2814	// Add a partial equivalence between the LHS and op1 for casts.
2815
2816	relation_kind
2817	operator_cast::lhs_op1_relation (const irange &lhs,
2818	const irange &op1,
2819	const irange &op2 ATTRIBUTE_UNUSED,
2820	relation_kind) const
2821	{
2822	if (lhs.undefined_p () || op1.undefined_p ())
2823	return VREL_VARYING;
2824	unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
2825	unsigned op1_prec = TYPE_PRECISION (op1.type ());
2826	// If the result gets sign extended into a larger type check first if this
2827	// qualifies as a partial equivalence.
2828	if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
2829	{
2830	// If the result is sign extended, and the LHS is larger than op1,
2831	// check if op1's range can be negative as the sign extension will
2832	// cause the upper bits to be 1 instead of 0, invalidating the PE.
2833	int_range<3> negs = range_negatives (type: op1.type ());
2834	negs.intersect (op1);
2835	if (!negs.undefined_p ())
2836	return VREL_VARYING;
2837	}
2838
2839	unsigned prec = MIN (lhs_prec, op1_prec);
2840	return bits_to_pe (bits: prec);
2841	}
2842
2843	// Return TRUE if casting from INNER to OUTER is a truncating cast.
2844
2845	inline bool
2846	operator_cast::truncating_cast_p (const irange &inner,
2847	const irange &outer) const
2848	{
2849	return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
2850	}
2851
2852	// Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2853
2854	bool
2855	operator_cast::inside_domain_p (const wide_int &min,
2856	const wide_int &max,
2857	const irange &range) const
2858	{
2859	wide_int domain_min = irange_val_min (type: range.type ());
2860	wide_int domain_max = irange_val_max (type: range.type ());
2861	signop domain_sign = TYPE_SIGN (range.type ());
2862	return (wi::le_p (x: min, y: domain_max, sgn: domain_sign)
2863	&& wi::le_p (x: max, y: domain_max, sgn: domain_sign)
2864	&& wi::ge_p (x: min, y: domain_min, sgn: domain_sign)
2865	&& wi::ge_p (x: max, y: domain_min, sgn: domain_sign));
2866	}
2867
2868
2869	// Helper for fold_range which work on a pair at a time.
2870
2871	void
2872	operator_cast::fold_pair (irange &r, unsigned index,
2873	const irange &inner,
2874	const irange &outer) const
2875	{
2876	tree inner_type = inner.type ();
2877	tree outer_type = outer.type ();
2878	signop inner_sign = TYPE_SIGN (inner_type);
2879	unsigned outer_prec = TYPE_PRECISION (outer_type);
2880
2881	// check to see if casting from INNER to OUTER is a conversion that
2882	// fits in the resulting OUTER type.
2883	wide_int inner_lb = inner.lower_bound (pair: index);
2884	wide_int inner_ub = inner.upper_bound (pair: index);
2885	if (truncating_cast_p (inner, outer))
2886	{
2887	// We may be able to accommodate a truncating cast if the
2888	// resulting range can be represented in the target type...
2889	if (wi::rshift (x: wi::sub (x: inner_ub, y: inner_lb),
2890	y: wi::uhwi (val: outer_prec, TYPE_PRECISION (inner.type ())),
2891	sgn: inner_sign) != 0)
2892	{
2893	r.set_varying (outer_type);
2894	return;
2895	}
2896	}
2897	// ...but we must still verify that the final range fits in the
2898	// domain. This catches -fstrict-enum restrictions where the domain
2899	// range is smaller than what fits in the underlying type.
2900	wide_int min = wide_int::from (x: inner_lb, precision: outer_prec, sgn: inner_sign);
2901	wide_int max = wide_int::from (x: inner_ub, precision: outer_prec, sgn: inner_sign);
2902	if (inside_domain_p (min, max, range: outer))
2903	create_possibly_reversed_range (r, type: outer_type, new_lb: min, new_ub: max);
2904	else
2905	r.set_varying (outer_type);
2906	}
2907
2908
2909	bool
2910	operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
2911	const irange &inner,
2912	const irange &outer,
2913	relation_trio) const
2914	{
2915	if (empty_range_varying (r, type, op1: inner, op2: outer))
2916	return true;
2917
2918	gcc_checking_assert (outer.varying_p ());
2919	gcc_checking_assert (inner.num_pairs () > 0);
2920
2921	// Avoid a temporary by folding the first pair directly into the result.
2922	fold_pair (r, index: 0, inner, outer);
2923
2924	// Then process any additional pairs by unioning with their results.
2925	for (unsigned x = 1; x < inner.num_pairs (); ++x)
2926	{
2927	int_range_max tmp;
2928	fold_pair (r&: tmp, index: x, inner, outer);
2929	r.union_ (tmp);
2930	if (r.varying_p ())
2931	return true;
2932	}
2933
2934	update_bitmask (r, lh: inner, rh: outer);
2935	return true;
2936	}
2937
2938	void
2939	operator_cast::update_bitmask (irange &r, const irange &lh,
2940	const irange &rh) const
2941	{
2942	update_known_bitmask (r, code: CONVERT_EXPR, lh, rh);
2943	}
2944
2945	bool
2946	operator_cast::op1_range (irange &r, tree type,
2947	const irange &lhs,
2948	const irange &op2,
2949	relation_trio) const
2950	{
2951	if (lhs.undefined_p ())
2952	return false;
2953	tree lhs_type = lhs.type ();
2954	gcc_checking_assert (types_compatible_p (op2.type(), type));
2955
2956	// If we are calculating a pointer, shortcut to what we really care about.
2957	if (POINTER_TYPE_P (type))
2958	{
2959	// Conversion from other pointers or a constant (including 0/NULL)
2960	// are straightforward.
2961	if (POINTER_TYPE_P (lhs.type ())
2962	|| (lhs.singleton_p ()
2963	&& TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
2964	{
2965	r = lhs;
2966	range_cast (r, type);
2967	}
2968	else
2969	{
2970	// If the LHS is not a pointer nor a singleton, then it is
2971	// either VARYING or non-zero.
2972	if (!lhs.undefined_p () && !contains_zero_p (r: lhs))
2973	r.set_nonzero (type);
2974	else
2975	r.set_varying (type);
2976	}
2977	r.intersect (op2);
2978	return true;
2979	}
2980
2981	if (truncating_cast_p (inner: op2, outer: lhs))
2982	{
2983	if (lhs.varying_p ())
2984	r.set_varying (type);
2985	else
2986	{
2987	// We want to insert the LHS as an unsigned value since it
2988	// would not trigger the signed bit of the larger type.
2989	int_range_max converted_lhs = lhs;
2990	range_cast (r&: converted_lhs, type: unsigned_type_for (lhs_type));
2991	range_cast (r&: converted_lhs, type);
2992	// Start by building the positive signed outer range for the type.
2993	wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
2994	TYPE_PRECISION (type));
2995	create_possibly_reversed_range (r, type, new_lb: lim,
2996	new_ub: wi::max_value (TYPE_PRECISION (type),
2997	SIGNED));
2998	// For the signed part, we need to simply union the 2 ranges now.
2999	r.union_ (converted_lhs);
3000
3001	// Create maximal negative number outside of LHS bits.
3002	lim = wi::mask (TYPE_PRECISION (lhs_type), negate_p: true,
3003	TYPE_PRECISION (type));
3004	// Add this to the unsigned LHS range(s).
3005	int_range_max lim_range (type, lim, lim);
3006	int_range_max lhs_neg;
3007	range_op_handler (PLUS_EXPR).fold_range (r&: lhs_neg, type,
3008	lh: converted_lhs, rh: lim_range);
3009	// lhs_neg now has all the negative versions of the LHS.
3010	// Now union in all the values from SIGNED MIN (0x80000) to
3011	// lim-1 in order to fill in all the ranges with the upper
3012	// bits set.
3013
3014	// PR 97317. If the lhs has only 1 bit less precision than the rhs,
3015	// we don't need to create a range from min to lim-1
3016	// calculate neg range traps trying to create [lim, lim - 1].
3017	wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3018	if (lim != min_val)
3019	{
3020	int_range_max neg (type,
3021	wi::min_value (TYPE_PRECISION (type),
3022	SIGNED),
3023	lim - 1);
3024	lhs_neg.union_ (neg);
3025	}
3026	// And finally, munge the signed and unsigned portions.
3027	r.union_ (lhs_neg);
3028	}
3029	// And intersect with any known value passed in the extra operand.
3030	r.intersect (op2);
3031	return true;
3032	}
3033
3034	int_range_max tmp;
3035	if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3036	tmp = lhs;
3037	else
3038	{
3039	// The cast is not truncating, and the range is restricted to
3040	// the range of the RHS by this assignment.
3041	//
3042	// Cast the range of the RHS to the type of the LHS.
3043	fold_range (r&: tmp, type: lhs_type, inner: int_range<1> (type), outer: int_range<1> (lhs_type));
3044	// Intersect this with the LHS range will produce the range,
3045	// which will be cast to the RHS type before returning.
3046	tmp.intersect (lhs);
3047	}
3048
3049	// Cast the calculated range to the type of the RHS.
3050	fold_range (r, type, inner: tmp, outer: int_range<1> (type));
3051	return true;
3052	}
3053
3054
3055	class operator_logical_and : public range_operator
3056	{
3057	using range_operator::fold_range;
3058	using range_operator::op1_range;
3059	using range_operator::op2_range;
3060	public:
3061	virtual bool fold_range (irange &r, tree type,
3062	const irange &lh,
3063	const irange &rh,
3064	relation_trio rel = TRIO_VARYING) const;
3065	virtual bool op1_range (irange &r, tree type,
3066	const irange &lhs,
3067	const irange &op2,
3068	relation_trio rel = TRIO_VARYING) const;
3069	virtual bool op2_range (irange &r, tree type,
3070	const irange &lhs,
3071	const irange &op1,
3072	relation_trio rel = TRIO_VARYING) const;
3073	} op_logical_and;
3074
3075
3076	bool
3077	operator_logical_and::fold_range (irange &r, tree type,
3078	const irange &lh,
3079	const irange &rh,
3080	relation_trio) const
3081	{
3082	if (empty_range_varying (r, type, op1: lh, op2: rh))
3083	return true;
3084
3085	// 0 && anything is 0.
3086	if ((wi::eq_p (x: lh.lower_bound (), y: 0) && wi::eq_p (x: lh.upper_bound (), y: 0))
3087	|| (wi::eq_p (x: lh.lower_bound (), y: 0) && wi::eq_p (x: rh.upper_bound (), y: 0)))
3088	r = range_false (type);
3089	else if (contains_zero_p (r: lh) || contains_zero_p (r: rh))
3090	// To reach this point, there must be a logical 1 on each side, and
3091	// the only remaining question is whether there is a zero or not.
3092	r = range_true_and_false (type);
3093	else
3094	r = range_true (type);
3095	return true;
3096	}
3097
3098	bool
3099	operator_logical_and::op1_range (irange &r, tree type,
3100	const irange &lhs,
3101	const irange &op2 ATTRIBUTE_UNUSED,
3102	relation_trio) const
3103	{
3104	switch (get_bool_state (r, lhs, val_type: type))
3105	{
3106	case BRS_TRUE:
3107	// A true result means both sides of the AND must be true.
3108	r = range_true (type);
3109	break;
3110	default:
3111	// Any other result means only one side has to be false, the
3112	// other side can be anything. So we cannot be sure of any
3113	// result here.
3114	r = range_true_and_false (type);
3115	break;
3116	}
3117	return true;
3118	}
3119
3120	bool
3121	operator_logical_and::op2_range (irange &r, tree type,
3122	const irange &lhs,
3123	const irange &op1,
3124	relation_trio) const
3125	{
3126	return operator_logical_and::op1_range (r, type, lhs, op2: op1);
3127	}
3128
3129
3130	void
3131	operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3132	const irange &rh) const
3133	{
3134	update_known_bitmask (r, code: BIT_AND_EXPR, lh, rh);
3135	}
3136
3137	// Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3138	// by considering the number of leading redundant sign bit copies.
3139	// clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3140	// [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3141	static bool
3142	wi_optimize_signed_bitwise_op (irange &r, tree type,
3143	const wide_int &lh_lb, const wide_int &lh_ub,
3144	const wide_int &rh_lb, const wide_int &rh_ub)
3145	{
3146	int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3147	int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3148	int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3149	if (new_clrsb == 0)
3150	return false;
3151	int type_prec = TYPE_PRECISION (type);
3152	int rprec = (type_prec - new_clrsb) - 1;
3153	value_range_with_overflow (r, type,
3154	wmin: wi::mask (width: rprec, negate_p: true, precision: type_prec),
3155	wmax: wi::mask (width: rprec, negate_p: false, precision: type_prec));
3156	return true;
3157	}
3158
3159	// An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3160	// the LHS and op1.
3161
3162	relation_kind
3163	operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3164	const irange &op1,
3165	const irange &op2,
3166	relation_kind) const
3167	{
3168	if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3169	return VREL_VARYING;
3170	if (!op2.singleton_p ())
3171	return VREL_VARYING;
3172	// if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3173	int prec1 = TYPE_PRECISION (op1.type ());
3174	int prec2 = TYPE_PRECISION (op2.type ());
3175	int mask_prec = 0;
3176	wide_int mask = op2.lower_bound ();
3177	if (wi::eq_p (x: mask, y: wi::mask (width: 8, negate_p: false, precision: prec2)))
3178	mask_prec = 8;
3179	else if (wi::eq_p (x: mask, y: wi::mask (width: 16, negate_p: false, precision: prec2)))
3180	mask_prec = 16;
3181	else if (wi::eq_p (x: mask, y: wi::mask (width: 32, negate_p: false, precision: prec2)))
3182	mask_prec = 32;
3183	else if (wi::eq_p (x: mask, y: wi::mask (width: 64, negate_p: false, precision: prec2)))
3184	mask_prec = 64;
3185	return bits_to_pe (MIN (prec1, mask_prec));
3186	}
3187
3188	// Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3189	// possible. Basically, see if we can optimize:
3190	//
3191	// [LB, UB] op Z
3192	// into:
3193	// [LB op Z, UB op Z]
3194	//
3195	// If the optimization was successful, accumulate the range in R and
3196	// return TRUE.
3197
3198	static bool
3199	wi_optimize_and_or (irange &r,
3200	enum tree_code code,
3201	tree type,
3202	const wide_int &lh_lb, const wide_int &lh_ub,
3203	const wide_int &rh_lb, const wide_int &rh_ub)
3204	{
3205	// Calculate the singleton mask among the ranges, if any.
3206	wide_int lower_bound, upper_bound, mask;
3207	if (wi::eq_p (x: rh_lb, y: rh_ub))
3208	{
3209	mask = rh_lb;
3210	lower_bound = lh_lb;
3211	upper_bound = lh_ub;
3212	}
3213	else if (wi::eq_p (x: lh_lb, y: lh_ub))
3214	{
3215	mask = lh_lb;
3216	lower_bound = rh_lb;
3217	upper_bound = rh_ub;
3218	}
3219	else
3220	return false;
3221
3222	// If Z is a constant which (for op | its bitwise not) has n
3223	// consecutive least significant bits cleared followed by m 1
3224	// consecutive bits set immediately above it and either
3225	// m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3226	//
3227	// The least significant n bits of all the values in the range are
3228	// cleared or set, the m bits above it are preserved and any bits
3229	// above these are required to be the same for all values in the
3230	// range.
3231	wide_int w = mask;
3232	int m = 0, n = 0;
3233	if (code == BIT_IOR_EXPR)
3234	w = ~w;
3235	if (wi::eq_p (x: w, y: 0))
3236	n = w.get_precision ();
3237	else
3238	{
3239	n = wi::ctz (w);
3240	w = ~(w | wi::mask (width: n, negate_p: false, precision: w.get_precision ()));
3241	if (wi::eq_p (x: w, y: 0))
3242	m = w.get_precision () - n;
3243	else
3244	m = wi::ctz (w) - n;
3245	}
3246	wide_int new_mask = wi::mask (width: m + n, negate_p: true, precision: w.get_precision ());
3247	if ((new_mask & lower_bound) != (new_mask & upper_bound))
3248	return false;
3249
3250	wide_int res_lb, res_ub;
3251	if (code == BIT_AND_EXPR)
3252	{
3253	res_lb = wi::bit_and (x: lower_bound, y: mask);
3254	res_ub = wi::bit_and (x: upper_bound, y: mask);
3255	}
3256	else if (code == BIT_IOR_EXPR)
3257	{
3258	res_lb = wi::bit_or (x: lower_bound, y: mask);
3259	res_ub = wi::bit_or (x: upper_bound, y: mask);
3260	}
3261	else
3262	gcc_unreachable ();
3263	value_range_with_overflow (r, type, wmin: res_lb, wmax: res_ub);
3264
3265	// Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3266	if (code == BIT_IOR_EXPR && wi::ne_p (x: mask, y: 0))
3267	{
3268	int_range<2> tmp;
3269	tmp.set_nonzero (type);
3270	r.intersect (tmp);
3271	}
3272	return true;
3273	}
3274
3275	// For range [LB, UB] compute two wide_int bit masks.
3276	//
3277	// In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3278	// for all numbers in the range the bit is 0, otherwise it might be 0
3279	// or 1.
3280	//
3281	// In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3282	// for all numbers in the range the bit is 1, otherwise it might be 0
3283	// or 1.
3284
3285	void
3286	wi_set_zero_nonzero_bits (tree type,
3287	const wide_int &lb, const wide_int &ub,
3288	wide_int &maybe_nonzero,
3289	wide_int &mustbe_nonzero)
3290	{
3291	signop sign = TYPE_SIGN (type);
3292
3293	if (wi::eq_p (x: lb, y: ub))
3294	maybe_nonzero = mustbe_nonzero = lb;
3295	else if (wi::ge_p (x: lb, y: 0, sgn: sign) || wi::lt_p (x: ub, y: 0, sgn: sign))
3296	{
3297	wide_int xor_mask = lb ^ ub;
3298	maybe_nonzero = lb | ub;
3299	mustbe_nonzero = lb & ub;
3300	if (xor_mask != 0)
3301	{
3302	wide_int mask = wi::mask (width: wi::floor_log2 (xor_mask), negate_p: false,
3303	precision: maybe_nonzero.get_precision ());
3304	maybe_nonzero = maybe_nonzero | mask;
3305	mustbe_nonzero = wi::bit_and_not (x: mustbe_nonzero, y: mask);
3306	}
3307	}
3308	else
3309	{
3310	maybe_nonzero = wi::minus_one (precision: lb.get_precision ());
3311	mustbe_nonzero = wi::zero (precision: lb.get_precision ());
3312	}
3313	}
3314
3315	void
3316	operator_bitwise_and::wi_fold (irange &r, tree type,
3317	const wide_int &lh_lb,
3318	const wide_int &lh_ub,
3319	const wide_int &rh_lb,
3320	const wide_int &rh_ub) const
3321	{
3322	if (wi_optimize_and_or (r, code: BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3323	return;
3324
3325	wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3326	wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3327	wi_set_zero_nonzero_bits (type, lb: lh_lb, ub: lh_ub,
3328	maybe_nonzero&: maybe_nonzero_lh, mustbe_nonzero&: mustbe_nonzero_lh);
3329	wi_set_zero_nonzero_bits (type, lb: rh_lb, ub: rh_ub,
3330	maybe_nonzero&: maybe_nonzero_rh, mustbe_nonzero&: mustbe_nonzero_rh);
3331
3332	wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3333	wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3334	signop sign = TYPE_SIGN (type);
3335	unsigned prec = TYPE_PRECISION (type);
3336	// If both input ranges contain only negative values, we can
3337	// truncate the result range maximum to the minimum of the
3338	// input range maxima.
3339	if (wi::lt_p (x: lh_ub, y: 0, sgn: sign) && wi::lt_p (x: rh_ub, y: 0, sgn: sign))
3340	{
3341	new_ub = wi::min (x: new_ub, y: lh_ub, sgn: sign);
3342	new_ub = wi::min (x: new_ub, y: rh_ub, sgn: sign);
3343	}
3344	// If either input range contains only non-negative values
3345	// we can truncate the result range maximum to the respective
3346	// maximum of the input range.
3347	if (wi::ge_p (x: lh_lb, y: 0, sgn: sign))
3348	new_ub = wi::min (x: new_ub, y: lh_ub, sgn: sign);
3349	if (wi::ge_p (x: rh_lb, y: 0, sgn: sign))
3350	new_ub = wi::min (x: new_ub, y: rh_ub, sgn: sign);
3351	// PR68217: In case of signed & sign-bit-CST should
3352	// result in [-INF, 0] instead of [-INF, INF].
3353	if (wi::gt_p (x: new_lb, y: new_ub, sgn: sign))
3354	{
3355	wide_int sign_bit = wi::set_bit_in_zero (bit: prec - 1, precision: prec);
3356	if (sign == SIGNED
3357	&& ((wi::eq_p (x: lh_lb, y: lh_ub)
3358	&& !wi::cmps (x: lh_lb, y: sign_bit))
3359	|| (wi::eq_p (x: rh_lb, y: rh_ub)
3360	&& !wi::cmps (x: rh_lb, y: sign_bit))))
3361	{
3362	new_lb = wi::min_value (prec, sign);
3363	new_ub = wi::zero (precision: prec);
3364	}
3365	}
3366	// If the limits got swapped around, return varying.
3367	if (wi::gt_p (x: new_lb, y: new_ub,sgn: sign))
3368	{
3369	if (sign == SIGNED
3370	&& wi_optimize_signed_bitwise_op (r, type,
3371	lh_lb, lh_ub,
3372	rh_lb, rh_ub))
3373	return;
3374	r.set_varying (type);
3375	}
3376	else
3377	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub);
3378	}
3379
3380	static void
3381	set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3382	{
3383	if (lhs.undefined_p () || contains_zero_p (r: lhs))
3384	r.set_varying (type);
3385	else
3386	r.set_nonzero (type);
3387	}
3388
3389	/* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3390	(otherwise return VAL). VAL and MASK must be zero-extended for
3391	precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3392	(to transform signed values into unsigned) and at the end xor
3393	SGNBIT back. */
3394
3395	wide_int
3396	masked_increment (const wide_int &val_in, const wide_int &mask,
3397	const wide_int &sgnbit, unsigned int prec)
3398	{
3399	wide_int bit = wi::one (precision: prec), res;
3400	unsigned int i;
3401
3402	wide_int val = val_in ^ sgnbit;
3403	for (i = 0; i < prec; i++, bit += bit)
3404	{
3405	res = mask;
3406	if ((res & bit) == 0)
3407	continue;
3408	res = bit - 1;
3409	res = wi::bit_and_not (x: val + bit, y: res);
3410	res &= mask;
3411	if (wi::gtu_p (x: res, y: val))
3412	return res ^ sgnbit;
3413	}
3414	return val ^ sgnbit;
3415	}
3416
3417	// This was shamelessly stolen from register_edge_assert_for_2 and
3418	// adjusted to work with iranges.
3419
3420	void
3421	operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3422	const irange &lhs,
3423	const irange &op2) const
3424	{
3425	if (!op2.singleton_p ())
3426	{
3427	set_nonzero_range_from_mask (r, type, lhs);
3428	return;
3429	}
3430	unsigned int nprec = TYPE_PRECISION (type);
3431	wide_int cst2v = op2.lower_bound ();
3432	bool cst2n = wi::neg_p (x: cst2v, TYPE_SIGN (type));
3433	wide_int sgnbit;
3434	if (cst2n)
3435	sgnbit = wi::set_bit_in_zero (bit: nprec - 1, precision: nprec);
3436	else
3437	sgnbit = wi::zero (precision: nprec);
3438
3439	// Solve [lhs.lower_bound (), +INF] = x & MASK.
3440	//
3441	// Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3442	// maximum unsigned value is ~0. For signed comparison, if CST2
3443	// doesn't have the most significant bit set, handle it similarly. If
3444	// CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3445	wide_int valv = lhs.lower_bound ();
3446	wide_int minv = valv & cst2v, maxv;
3447	bool we_know_nothing = false;
3448	if (minv != valv)
3449	{
3450	// If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3451	minv = masked_increment (val_in: valv, mask: cst2v, sgnbit, prec: nprec);
3452	if (minv == valv)
3453	{
3454	// If we can't determine anything on this bound, fall
3455	// through and conservatively solve for the other end point.
3456	we_know_nothing = true;
3457	}
3458	}
3459	maxv = wi::mask (width: nprec - (cst2n ? 1 : 0), negate_p: false, precision: nprec);
3460	if (we_know_nothing)
3461	r.set_varying (type);
3462	else
3463	create_possibly_reversed_range (r, type, new_lb: minv, new_ub: maxv);
3464
3465	// Solve [-INF, lhs.upper_bound ()] = x & MASK.
3466	//
3467	// Minimum unsigned value for <= is 0 and maximum unsigned value is
3468	// VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3469	// VAL2 where
3470	// VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3471	// as maximum.
3472	// For signed comparison, if CST2 doesn't have most significant bit
3473	// set, handle it similarly. If CST2 has MSB set, the maximum is
3474	// the same and minimum is INT_MIN.
3475	valv = lhs.upper_bound ();
3476	minv = valv & cst2v;
3477	if (minv == valv)
3478	maxv = valv;
3479	else
3480	{
3481	maxv = masked_increment (val_in: valv, mask: cst2v, sgnbit, prec: nprec);
3482	if (maxv == valv)
3483	{
3484	// If we couldn't determine anything on either bound, return
3485	// undefined.
3486	if (we_know_nothing)
3487	r.set_undefined ();
3488	return;
3489	}
3490	maxv -= 1;
3491	}
3492	maxv |= ~cst2v;
3493	minv = sgnbit;
3494	int_range<2> upper_bits;
3495	create_possibly_reversed_range (r&: upper_bits, type, new_lb: minv, new_ub: maxv);
3496	r.intersect (upper_bits);
3497	}
3498
3499	bool
3500	operator_bitwise_and::op1_range (irange &r, tree type,
3501	const irange &lhs,
3502	const irange &op2,
3503	relation_trio) const
3504	{
3505	if (lhs.undefined_p ())
3506	return false;
3507	if (types_compatible_p (type1: type, boolean_type_node))
3508	return op_logical_and.op1_range (r, type, lhs, op2);
3509
3510	r.set_undefined ();
3511	for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3512	{
3513	int_range_max chunk (lhs.type (),
3514	lhs.lower_bound (pair: i),
3515	lhs.upper_bound (pair: i));
3516	int_range_max res;
3517	simple_op1_range_solver (r&: res, type, lhs: chunk, op2);
3518	r.union_ (res);
3519	}
3520	if (r.undefined_p ())
3521	set_nonzero_range_from_mask (r, type, lhs);
3522
3523	// For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3524	wide_int mask;
3525	if (lhs == op2 && lhs.singleton_p (mask))
3526	{
3527	r.update_bitmask (irange_bitmask (mask, ~mask));
3528	return true;
3529	}
3530
3531	// For 0 = op1 & MASK, op1 is ~MASK.
3532	if (lhs.zero_p () && op2.singleton_p ())
3533	{
3534	wide_int nz = wi::bit_not (x: op2.get_nonzero_bits ());
3535	int_range<2> tmp (type);
3536	tmp.set_nonzero_bits (nz);
3537	r.intersect (tmp);
3538	}
3539	return true;
3540	}
3541
3542	bool
3543	operator_bitwise_and::op2_range (irange &r, tree type,
3544	const irange &lhs,
3545	const irange &op1,
3546	relation_trio) const
3547	{
3548	return operator_bitwise_and::op1_range (r, type, lhs, op2: op1);
3549	}
3550
3551
3552	class operator_logical_or : public range_operator
3553	{
3554	using range_operator::fold_range;
3555	using range_operator::op1_range;
3556	using range_operator::op2_range;
3557	public:
3558	virtual bool fold_range (irange &r, tree type,
3559	const irange &lh,
3560	const irange &rh,
3561	relation_trio rel = TRIO_VARYING) const;
3562	virtual bool op1_range (irange &r, tree type,
3563	const irange &lhs,
3564	const irange &op2,
3565	relation_trio rel = TRIO_VARYING) const;
3566	virtual bool op2_range (irange &r, tree type,
3567	const irange &lhs,
3568	const irange &op1,
3569	relation_trio rel = TRIO_VARYING) const;
3570	} op_logical_or;
3571
3572	bool
3573	operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3574	const irange &lh,
3575	const irange &rh,
3576	relation_trio) const
3577	{
3578	if (empty_range_varying (r, type, op1: lh, op2: rh))
3579	return true;
3580
3581	r = lh;
3582	r.union_ (rh);
3583	return true;
3584	}
3585
3586	bool
3587	operator_logical_or::op1_range (irange &r, tree type,
3588	const irange &lhs,
3589	const irange &op2 ATTRIBUTE_UNUSED,
3590	relation_trio) const
3591	{
3592	switch (get_bool_state (r, lhs, val_type: type))
3593	{
3594	case BRS_FALSE:
3595	// A false result means both sides of the OR must be false.
3596	r = range_false (type);
3597	break;
3598	default:
3599	// Any other result means only one side has to be true, the
3600	// other side can be anything. so we can't be sure of any result
3601	// here.
3602	r = range_true_and_false (type);
3603	break;
3604	}
3605	return true;
3606	}
3607
3608	bool
3609	operator_logical_or::op2_range (irange &r, tree type,
3610	const irange &lhs,
3611	const irange &op1,
3612	relation_trio) const
3613	{
3614	return operator_logical_or::op1_range (r, type, lhs, op2: op1);
3615	}
3616
3617
3618	void
3619	operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
3620	const irange &rh) const
3621	{
3622	update_known_bitmask (r, code: BIT_IOR_EXPR, lh, rh);
3623	}
3624
3625	void
3626	operator_bitwise_or::wi_fold (irange &r, tree type,
3627	const wide_int &lh_lb,
3628	const wide_int &lh_ub,
3629	const wide_int &rh_lb,
3630	const wide_int &rh_ub) const
3631	{
3632	if (wi_optimize_and_or (r, code: BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3633	return;
3634
3635	wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3636	wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3637	wi_set_zero_nonzero_bits (type, lb: lh_lb, ub: lh_ub,
3638	maybe_nonzero&: maybe_nonzero_lh, mustbe_nonzero&: mustbe_nonzero_lh);
3639	wi_set_zero_nonzero_bits (type, lb: rh_lb, ub: rh_ub,
3640	maybe_nonzero&: maybe_nonzero_rh, mustbe_nonzero&: mustbe_nonzero_rh);
3641	wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
3642	wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
3643	signop sign = TYPE_SIGN (type);
3644	// If the input ranges contain only positive values we can
3645	// truncate the minimum of the result range to the maximum
3646	// of the input range minima.
3647	if (wi::ge_p (x: lh_lb, y: 0, sgn: sign)
3648	&& wi::ge_p (x: rh_lb, y: 0, sgn: sign))
3649	{
3650	new_lb = wi::max (x: new_lb, y: lh_lb, sgn: sign);
3651	new_lb = wi::max (x: new_lb, y: rh_lb, sgn: sign);
3652	}
3653	// If either input range contains only negative values
3654	// we can truncate the minimum of the result range to the
3655	// respective minimum range.
3656	if (wi::lt_p (x: lh_ub, y: 0, sgn: sign))
3657	new_lb = wi::max (x: new_lb, y: lh_lb, sgn: sign);
3658	if (wi::lt_p (x: rh_ub, y: 0, sgn: sign))
3659	new_lb = wi::max (x: new_lb, y: rh_lb, sgn: sign);
3660	// If the limits got swapped around, return a conservative range.
3661	if (wi::gt_p (x: new_lb, y: new_ub, sgn: sign))
3662	{
3663	// Make sure that nonzero|X is nonzero.
3664	if (wi::gt_p (x: lh_lb, y: 0, sgn: sign)
3665	|| wi::gt_p (x: rh_lb, y: 0, sgn: sign)
3666	|| wi::lt_p (x: lh_ub, y: 0, sgn: sign)
3667	|| wi::lt_p (x: rh_ub, y: 0, sgn: sign))
3668	r.set_nonzero (type);
3669	else if (sign == SIGNED
3670	&& wi_optimize_signed_bitwise_op (r, type,
3671	lh_lb, lh_ub,
3672	rh_lb, rh_ub))
3673	return;
3674	else
3675	r.set_varying (type);
3676	return;
3677	}
3678	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub);
3679	}
3680
3681	bool
3682	operator_bitwise_or::op1_range (irange &r, tree type,
3683	const irange &lhs,
3684	const irange &op2,
3685	relation_trio) const
3686	{
3687	if (lhs.undefined_p ())
3688	return false;
3689	// If this is really a logical wi_fold, call that.
3690	if (types_compatible_p (type1: type, boolean_type_node))
3691	return op_logical_or.op1_range (r, type, lhs, op2);
3692
3693	if (lhs.zero_p ())
3694	{
3695	r.set_zero (type);
3696	return true;
3697	}
3698	r.set_varying (type);
3699	return true;
3700	}
3701
3702	bool
3703	operator_bitwise_or::op2_range (irange &r, tree type,
3704	const irange &lhs,
3705	const irange &op1,
3706	relation_trio) const
3707	{
3708	return operator_bitwise_or::op1_range (r, type, lhs, op2: op1);
3709	}
3710
3711	void
3712	operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
3713	const irange &rh) const
3714	{
3715	update_known_bitmask (r, code: BIT_XOR_EXPR, lh, rh);
3716	}
3717
3718	void
3719	operator_bitwise_xor::wi_fold (irange &r, tree type,
3720	const wide_int &lh_lb,
3721	const wide_int &lh_ub,
3722	const wide_int &rh_lb,
3723	const wide_int &rh_ub) const
3724	{
3725	signop sign = TYPE_SIGN (type);
3726	wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3727	wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3728	wi_set_zero_nonzero_bits (type, lb: lh_lb, ub: lh_ub,
3729	maybe_nonzero&: maybe_nonzero_lh, mustbe_nonzero&: mustbe_nonzero_lh);
3730	wi_set_zero_nonzero_bits (type, lb: rh_lb, ub: rh_ub,
3731	maybe_nonzero&: maybe_nonzero_rh, mustbe_nonzero&: mustbe_nonzero_rh);
3732
3733	wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
3734	| ~(maybe_nonzero_lh | maybe_nonzero_rh));
3735	wide_int result_one_bits
3736	= (wi::bit_and_not (x: mustbe_nonzero_lh, y: maybe_nonzero_rh)
3737	| wi::bit_and_not (x: mustbe_nonzero_rh, y: maybe_nonzero_lh));
3738	wide_int new_ub = ~result_zero_bits;
3739	wide_int new_lb = result_one_bits;
3740
3741	// If the range has all positive or all negative values, the result
3742	// is better than VARYING.
3743	if (wi::lt_p (x: new_lb, y: 0, sgn: sign) || wi::ge_p (x: new_ub, y: 0, sgn: sign))
3744	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub);
3745	else if (sign == SIGNED
3746	&& wi_optimize_signed_bitwise_op (r, type,
3747	lh_lb, lh_ub,
3748	rh_lb, rh_ub))
3749	; /* Do nothing. */
3750	else
3751	r.set_varying (type);
3752
3753	/* Furthermore, XOR is non-zero if its arguments can't be equal. */
3754	if (wi::lt_p (x: lh_ub, y: rh_lb, sgn: sign)
3755	|| wi::lt_p (x: rh_ub, y: lh_lb, sgn: sign)
3756	|| wi::ne_p (x: result_one_bits, y: 0))
3757	{
3758	int_range<2> tmp;
3759	tmp.set_nonzero (type);
3760	r.intersect (tmp);
3761	}
3762	}
3763
3764	bool
3765	operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
3766	tree type,
3767	const irange &,
3768	const irange &,
3769	relation_kind rel) const
3770	{
3771	if (rel == VREL_VARYING)
3772	return false;
3773
3774	int_range<2> rel_range;
3775
3776	switch (rel)
3777	{
3778	case VREL_EQ:
3779	rel_range.set_zero (type);
3780	break;
3781	case VREL_NE:
3782	rel_range.set_nonzero (type);
3783	break;
3784	default:
3785	return false;
3786	}
3787
3788	lhs_range.intersect (rel_range);
3789	return true;
3790	}
3791
3792	bool
3793	operator_bitwise_xor::op1_range (irange &r, tree type,
3794	const irange &lhs,
3795	const irange &op2,
3796	relation_trio) const
3797	{
3798	if (lhs.undefined_p () || lhs.varying_p ())
3799	{
3800	r = lhs;
3801	return true;
3802	}
3803	if (types_compatible_p (type1: type, boolean_type_node))
3804	{
3805	switch (get_bool_state (r, lhs, val_type: type))
3806	{
3807	case BRS_TRUE:
3808	if (op2.varying_p ())
3809	r.set_varying (type);
3810	else if (op2.zero_p ())
3811	r = range_true (type);
3812	// See get_bool_state for the rationale
3813	else if (op2.undefined_p () || contains_zero_p (r: op2))
3814	r = range_true_and_false (type);
3815	else
3816	r = range_false (type);
3817	break;
3818	case BRS_FALSE:
3819	r = op2;
3820	break;
3821	default:
3822	break;
3823	}
3824	return true;
3825	}
3826	r.set_varying (type);
3827	return true;
3828	}
3829
3830	bool
3831	operator_bitwise_xor::op2_range (irange &r, tree type,
3832	const irange &lhs,
3833	const irange &op1,
3834	relation_trio) const
3835	{
3836	return operator_bitwise_xor::op1_range (r, type, lhs, op2: op1);
3837	}
3838
3839	class operator_trunc_mod : public range_operator
3840	{
3841	using range_operator::op1_range;
3842	using range_operator::op2_range;
3843	public:
3844	virtual void wi_fold (irange &r, tree type,
3845	const wide_int &lh_lb,
3846	const wide_int &lh_ub,
3847	const wide_int &rh_lb,
3848	const wide_int &rh_ub) const;
3849	virtual bool op1_range (irange &r, tree type,
3850	const irange &lhs,
3851	const irange &op2,
3852	relation_trio) const;
3853	virtual bool op2_range (irange &r, tree type,
3854	const irange &lhs,
3855	const irange &op1,
3856	relation_trio) const;
3857	void update_bitmask (irange &r, const irange &lh, const irange &rh) const
3858	{ update_known_bitmask (r, code: TRUNC_MOD_EXPR, lh, rh); }
3859	} op_trunc_mod;
3860
3861	void
3862	operator_trunc_mod::wi_fold (irange &r, tree type,
3863	const wide_int &lh_lb,
3864	const wide_int &lh_ub,
3865	const wide_int &rh_lb,
3866	const wide_int &rh_ub) const
3867	{
3868	wide_int new_lb, new_ub, tmp;
3869	signop sign = TYPE_SIGN (type);
3870	unsigned prec = TYPE_PRECISION (type);
3871
3872	// Mod 0 is undefined.
3873	if (wi_zero_p (type, wmin: rh_lb, wmax: rh_ub))
3874	{
3875	r.set_undefined ();
3876	return;
3877	}
3878
3879	// Check for constant and try to fold.
3880	if (lh_lb == lh_ub && rh_lb == rh_ub)
3881	{
3882	wi::overflow_type ov = wi::OVF_NONE;
3883	tmp = wi::mod_trunc (x: lh_lb, y: rh_lb, sgn: sign, overflow: &ov);
3884	if (ov == wi::OVF_NONE)
3885	{
3886	r = int_range<2> (type, tmp, tmp);
3887	return;
3888	}
3889	}
3890
3891	// ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3892	new_ub = rh_ub - 1;
3893	if (sign == SIGNED)
3894	{
3895	tmp = -1 - rh_lb;
3896	new_ub = wi::smax (x: new_ub, y: tmp);
3897	}
3898
3899	if (sign == UNSIGNED)
3900	new_lb = wi::zero (precision: prec);
3901	else
3902	{
3903	new_lb = -new_ub;
3904	tmp = lh_lb;
3905	if (wi::gts_p (x: tmp, y: 0))
3906	tmp = wi::zero (precision: prec);
3907	new_lb = wi::smax (x: new_lb, y: tmp);
3908	}
3909	tmp = lh_ub;
3910	if (sign == SIGNED && wi::neg_p (x: tmp))
3911	tmp = wi::zero (precision: prec);
3912	new_ub = wi::min (x: new_ub, y: tmp, sgn: sign);
3913
3914	value_range_with_overflow (r, type, wmin: new_lb, wmax: new_ub);
3915	}
3916
3917	bool
3918	operator_trunc_mod::op1_range (irange &r, tree type,
3919	const irange &lhs,
3920	const irange &,
3921	relation_trio) const
3922	{
3923	if (lhs.undefined_p ())
3924	return false;
3925	// PR 91029.
3926	signop sign = TYPE_SIGN (type);
3927	unsigned prec = TYPE_PRECISION (type);
3928	// (a % b) >= x && x > 0 , then a >= x.
3929	if (wi::gt_p (x: lhs.lower_bound (), y: 0, sgn: sign))
3930	{
3931	r = value_range (type, lhs.lower_bound (), wi::max_value (prec, sign));
3932	return true;
3933	}
3934	// (a % b) <= x && x < 0 , then a <= x.
3935	if (wi::lt_p (x: lhs.upper_bound (), y: 0, sgn: sign))
3936	{
3937	r = value_range (type, wi::min_value (prec, sign), lhs.upper_bound ());
3938	return true;
3939	}
3940	return false;
3941	}
3942
3943	bool
3944	operator_trunc_mod::op2_range (irange &r, tree type,
3945	const irange &lhs,
3946	const irange &,
3947	relation_trio) const
3948	{
3949	if (lhs.undefined_p ())
3950	return false;
3951	// PR 91029.
3952	signop sign = TYPE_SIGN (type);
3953	unsigned prec = TYPE_PRECISION (type);
3954	// (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3955	// or b > x for unsigned.
3956	if (wi::gt_p (x: lhs.lower_bound (), y: 0, sgn: sign))
3957	{
3958	if (sign == SIGNED)
3959	r = value_range (type, wi::neg (x: lhs.lower_bound ()),
3960	lhs.lower_bound (), VR_ANTI_RANGE);
3961	else if (wi::lt_p (x: lhs.lower_bound (), y: wi::max_value (prec, sign),
3962	sgn: sign))
3963	r = value_range (type, lhs.lower_bound () + 1,
3964	wi::max_value (prec, sign));
3965	else
3966	return false;
3967	return true;
3968	}
3969	// (a % b) <= x && x < 0 , then b is in ~[x, -x].
3970	if (wi::lt_p (x: lhs.upper_bound (), y: 0, sgn: sign))
3971	{
3972	if (wi::gt_p (x: lhs.upper_bound (), y: wi::min_value (prec, sign), sgn: sign))
3973	r = value_range (type, lhs.upper_bound (),
3974	wi::neg (x: lhs.upper_bound ()), VR_ANTI_RANGE);
3975	else
3976	return false;
3977	return true;
3978	}
3979	return false;
3980	}
3981
3982
3983	class operator_logical_not : public range_operator
3984	{
3985	using range_operator::fold_range;
3986	using range_operator::op1_range;
3987	public:
3988	virtual bool fold_range (irange &r, tree type,
3989	const irange &lh,
3990	const irange &rh,
3991	relation_trio rel = TRIO_VARYING) const;
3992	virtual bool op1_range (irange &r, tree type,
3993	const irange &lhs,
3994	const irange &op2,
3995	relation_trio rel = TRIO_VARYING) const;
3996	} op_logical_not;
3997
3998	// Folding a logical NOT, oddly enough, involves doing nothing on the
3999	// forward pass through. During the initial walk backwards, the
4000	// logical NOT reversed the desired outcome on the way back, so on the
4001	// way forward all we do is pass the range forward.
4002	//
4003	// b_2 = x_1 < 20
4004	// b_3 = !b_2
4005	// if (b_3)
4006	// to determine the TRUE branch, walking backward
4007	// if (b_3) if ([1,1])
4008	// b_3 = !b_2 [1,1] = ![0,0]
4009	// b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4010	// which is the result we are looking for.. so.. pass it through.
4011
4012	bool
4013	operator_logical_not::fold_range (irange &r, tree type,
4014	const irange &lh,
4015	const irange &rh ATTRIBUTE_UNUSED,
4016	relation_trio) const
4017	{
4018	if (empty_range_varying (r, type, op1: lh, op2: rh))
4019	return true;
4020
4021	r = lh;
4022	if (!lh.varying_p () && !lh.undefined_p ())
4023	r.invert ();
4024
4025	return true;
4026	}
4027
4028	bool
4029	operator_logical_not::op1_range (irange &r,
4030	tree type,
4031	const irange &lhs,
4032	const irange &op2,
4033	relation_trio) const
4034	{
4035	// Logical NOT is involutary...do it again.
4036	return fold_range (r, type, lh: lhs, rh: op2);
4037	}
4038
4039
4040	bool
4041	operator_bitwise_not::fold_range (irange &r, tree type,
4042	const irange &lh,
4043	const irange &rh,
4044	relation_trio) const
4045	{
4046	if (empty_range_varying (r, type, op1: lh, op2: rh))
4047	return true;
4048
4049	if (types_compatible_p (type1: type, boolean_type_node))
4050	return op_logical_not.fold_range (r, type, lh, rh);
4051
4052	// ~X is simply -1 - X.
4053	int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4054	wi::minus_one (TYPE_PRECISION (type)));
4055	return range_op_handler (MINUS_EXPR).fold_range (r, type, lh: minusone, rh: lh);
4056	}
4057
4058	bool
4059	operator_bitwise_not::op1_range (irange &r, tree type,
4060	const irange &lhs,
4061	const irange &op2,
4062	relation_trio) const
4063	{
4064	if (lhs.undefined_p ())
4065	return false;
4066	if (types_compatible_p (type1: type, boolean_type_node))
4067	return op_logical_not.op1_range (r, type, lhs, op2);
4068
4069	// ~X is -1 - X and since bitwise NOT is involutary...do it again.
4070	return fold_range (r, type, lh: lhs, rh: op2);
4071	}
4072
4073	void
4074	operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4075	const irange &rh) const
4076	{
4077	update_known_bitmask (r, code: BIT_NOT_EXPR, lh, rh);
4078	}
4079
4080
4081	bool
4082	operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4083	const irange &lh,
4084	const irange &rh ATTRIBUTE_UNUSED,
4085	relation_trio) const
4086	{
4087	r = lh;
4088	return true;
4089	}
4090
4091
4092	// Determine if there is a relationship between LHS and OP1.
4093
4094	relation_kind
4095	operator_identity::lhs_op1_relation (const irange &lhs,
4096	const irange &op1 ATTRIBUTE_UNUSED,
4097	const irange &op2 ATTRIBUTE_UNUSED,
4098	relation_kind) const
4099	{
4100	if (lhs.undefined_p ())
4101	return VREL_VARYING;
4102	// Simply a copy, so they are equivalent.
4103	return VREL_EQ;
4104	}
4105
4106	bool
4107	operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4108	const irange &lh,
4109	const irange &rh ATTRIBUTE_UNUSED,
4110	relation_trio) const
4111	{
4112	r = lh;
4113	return true;
4114	}
4115
4116	bool
4117	operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4118	const irange &lhs,
4119	const irange &op2 ATTRIBUTE_UNUSED,
4120	relation_trio) const
4121	{
4122	r = lhs;
4123	return true;
4124	}
4125
4126
4127	class operator_unknown : public range_operator
4128	{
4129	using range_operator::fold_range;
4130	public:
4131	virtual bool fold_range (irange &r, tree type,
4132	const irange &op1,
4133	const irange &op2,
4134	relation_trio rel = TRIO_VARYING) const;
4135	} op_unknown;
4136
4137	bool
4138	operator_unknown::fold_range (irange &r, tree type,
4139	const irange &lh ATTRIBUTE_UNUSED,
4140	const irange &rh ATTRIBUTE_UNUSED,
4141	relation_trio) const
4142	{
4143	r.set_varying (type);
4144	return true;
4145	}
4146
4147
4148	void
4149	operator_abs::wi_fold (irange &r, tree type,
4150	const wide_int &lh_lb, const wide_int &lh_ub,
4151	const wide_int &rh_lb ATTRIBUTE_UNUSED,
4152	const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4153	{
4154	wide_int min, max;
4155	signop sign = TYPE_SIGN (type);
4156	unsigned prec = TYPE_PRECISION (type);
4157
4158	// Pass through LH for the easy cases.
4159	if (sign == UNSIGNED || wi::ge_p (x: lh_lb, y: 0, sgn: sign))
4160	{
4161	r = int_range<1> (type, lh_lb, lh_ub);
4162	return;
4163	}
4164
4165	// -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4166	// a useful range.
4167	wide_int min_value = wi::min_value (prec, sign);
4168	wide_int max_value = wi::max_value (prec, sign);
4169	if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (x: lh_lb, y: min_value))
4170	{
4171	r.set_varying (type);
4172	return;
4173	}
4174
4175	// ABS_EXPR may flip the range around, if the original range
4176	// included negative values.
4177	if (wi::eq_p (x: lh_lb, y: min_value))
4178	{
4179	// ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4180	// returned [-MIN,-MIN] so this preserves that behavior. PR37078
4181	if (wi::eq_p (x: lh_ub, y: min_value))
4182	{
4183	r = int_range<1> (type, min_value, min_value);
4184	return;
4185	}
4186	min = max_value;
4187	}
4188	else
4189	min = wi::abs (x: lh_lb);
4190
4191	if (wi::eq_p (x: lh_ub, y: min_value))
4192	max = max_value;
4193	else
4194	max = wi::abs (x: lh_ub);
4195
4196	// If the range contains zero then we know that the minimum value in the
4197	// range will be zero.
4198	if (wi::le_p (x: lh_lb, y: 0, sgn: sign) && wi::ge_p (x: lh_ub, y: 0, sgn: sign))
4199	{
4200	if (wi::gt_p (x: min, y: max, sgn: sign))
4201	max = min;
4202	min = wi::zero (precision: prec);
4203	}
4204	else
4205	{
4206	// If the range was reversed, swap MIN and MAX.
4207	if (wi::gt_p (x: min, y: max, sgn: sign))
4208	std::swap (a&: min, b&: max);
4209	}
4210
4211	// If the new range has its limits swapped around (MIN > MAX), then
4212	// the operation caused one of them to wrap around. The only thing
4213	// we know is that the result is positive.
4214	if (wi::gt_p (x: min, y: max, sgn: sign))
4215	{
4216	min = wi::zero (precision: prec);
4217	max = max_value;
4218	}
4219	r = int_range<1> (type, min, max);
4220	}
4221
4222	bool
4223	operator_abs::op1_range (irange &r, tree type,
4224	const irange &lhs,
4225	const irange &op2,
4226	relation_trio) const
4227	{
4228	if (empty_range_varying (r, type, op1: lhs, op2))
4229	return true;
4230	if (TYPE_UNSIGNED (type))
4231	{
4232	r = lhs;
4233	return true;
4234	}
4235	// Start with the positives because negatives are an impossible result.
4236	int_range_max positives = range_positives (type);
4237	positives.intersect (lhs);
4238	r = positives;
4239	// Then add the negative of each pair:
4240	// ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4241	for (unsigned i = 0; i < positives.num_pairs (); ++i)
4242	r.union_ (int_range<1> (type,
4243	-positives.upper_bound (pair: i),
4244	-positives.lower_bound (pair: i)));
4245	// With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4246	// unrepresentable. Add -TYPE_MIN_VALUE in this case.
4247	wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4248	wide_int lb = lhs.lower_bound ();
4249	if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (x: lb, y: min_value))
4250	r.union_ (int_range<2> (type, lb, lb));
4251	return true;
4252	}
4253
4254	void
4255	operator_abs::update_bitmask (irange &r, const irange &lh,
4256	const irange &rh) const
4257	{
4258	update_known_bitmask (r, code: ABS_EXPR, lh, rh);
4259	}
4260
4261	class operator_absu : public range_operator
4262	{
4263	public:
4264	virtual void wi_fold (irange &r, tree type,
4265	const wide_int &lh_lb, const wide_int &lh_ub,
4266	const wide_int &rh_lb, const wide_int &rh_ub) const;
4267	virtual void update_bitmask (irange &r, const irange &lh,
4268	const irange &rh) const final override;
4269	} op_absu;
4270
4271	void
4272	operator_absu::wi_fold (irange &r, tree type,
4273	const wide_int &lh_lb, const wide_int &lh_ub,
4274	const wide_int &rh_lb ATTRIBUTE_UNUSED,
4275	const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4276	{
4277	wide_int new_lb, new_ub;
4278
4279	// Pass through VR0 the easy cases.
4280	if (wi::ges_p (x: lh_lb, y: 0))
4281	{
4282	new_lb = lh_lb;
4283	new_ub = lh_ub;
4284	}
4285	else
4286	{
4287	new_lb = wi::abs (x: lh_lb);
4288	new_ub = wi::abs (x: lh_ub);
4289
4290	// If the range contains zero then we know that the minimum
4291	// value in the range will be zero.
4292	if (wi::ges_p (x: lh_ub, y: 0))
4293	{
4294	if (wi::gtu_p (x: new_lb, y: new_ub))
4295	new_ub = new_lb;
4296	new_lb = wi::zero (TYPE_PRECISION (type));
4297	}
4298	else
4299	std::swap (a&: new_lb, b&: new_ub);
4300	}
4301
4302	gcc_checking_assert (TYPE_UNSIGNED (type));
4303	r = int_range<1> (type, new_lb, new_ub);
4304	}
4305
4306	void
4307	operator_absu::update_bitmask (irange &r, const irange &lh,
4308	const irange &rh) const
4309	{
4310	update_known_bitmask (r, code: ABSU_EXPR, lh, rh);
4311	}
4312
4313
4314	bool
4315	operator_negate::fold_range (irange &r, tree type,
4316	const irange &lh,
4317	const irange &rh,
4318	relation_trio) const
4319	{
4320	if (empty_range_varying (r, type, op1: lh, op2: rh))
4321	return true;
4322	// -X is simply 0 - X.
4323	return range_op_handler (MINUS_EXPR).fold_range (r, type,
4324	lh: range_zero (type), rh: lh);
4325	}
4326
4327	bool
4328	operator_negate::op1_range (irange &r, tree type,
4329	const irange &lhs,
4330	const irange &op2,
4331	relation_trio) const
4332	{
4333	// NEGATE is involutory.
4334	return fold_range (r, type, lh: lhs, rh: op2);
4335	}
4336
4337
4338	bool
4339	operator_addr_expr::fold_range (irange &r, tree type,
4340	const irange &lh,
4341	const irange &rh,
4342	relation_trio) const
4343	{
4344	if (empty_range_varying (r, type, op1: lh, op2: rh))
4345	return true;
4346
4347	// Return a non-null pointer of the LHS type (passed in op2).
4348	if (lh.zero_p ())
4349	r = range_zero (type);
4350	else if (lh.undefined_p () || contains_zero_p (r: lh))
4351	r.set_varying (type);
4352	else
4353	r.set_nonzero (type);
4354	return true;
4355	}
4356
4357	bool
4358	operator_addr_expr::op1_range (irange &r, tree type,
4359	const irange &lhs,
4360	const irange &op2,
4361	relation_trio) const
4362	{
4363	if (empty_range_varying (r, type, op1: lhs, op2))
4364	return true;
4365
4366	// Return a non-null pointer of the LHS type (passed in op2), but only
4367	// if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4368	// See PR 111009.
4369	if (!lhs.undefined_p () && !contains_zero_p (r: lhs) && TYPE_OVERFLOW_UNDEFINED (type))
4370	r.set_nonzero (type);
4371	else
4372	r.set_varying (type);
4373	return true;
4374	}
4375
4376	// Initialize any integral operators to the primary table
4377
4378	void
4379	range_op_table::initialize_integral_ops ()
4380	{
4381	set (code: TRUNC_DIV_EXPR, op&: op_trunc_div);
4382	set (code: FLOOR_DIV_EXPR, op&: op_floor_div);
4383	set (code: ROUND_DIV_EXPR, op&: op_round_div);
4384	set (code: CEIL_DIV_EXPR, op&: op_ceil_div);
4385	set (code: EXACT_DIV_EXPR, op&: op_exact_div);
4386	set (code: LSHIFT_EXPR, op&: op_lshift);
4387	set (code: RSHIFT_EXPR, op&: op_rshift);
4388	set (code: TRUTH_AND_EXPR, op&: op_logical_and);
4389	set (code: TRUTH_OR_EXPR, op&: op_logical_or);
4390	set (code: TRUNC_MOD_EXPR, op&: op_trunc_mod);
4391	set (code: TRUTH_NOT_EXPR, op&: op_logical_not);
4392	set (code: IMAGPART_EXPR, op&: op_unknown);
4393	set (code: REALPART_EXPR, op&: op_unknown);
4394	set (code: ABSU_EXPR, op&: op_absu);
4395	set (OP_WIDEN_MULT_SIGNED, op&: op_widen_mult_signed);
4396	set (OP_WIDEN_MULT_UNSIGNED, op&: op_widen_mult_unsigned);
4397	set (OP_WIDEN_PLUS_SIGNED, op&: op_widen_plus_signed);
4398	set (OP_WIDEN_PLUS_UNSIGNED, op&: op_widen_plus_unsigned);
4399
4400	}
4401
4402	bool
4403	operator_plus::overflow_free_p (const irange &lh, const irange &rh,
4404	relation_trio) const
4405	{
4406	if (lh.undefined_p () || rh.undefined_p ())
4407	return false;
4408
4409	tree type = lh.type ();
4410	if (TYPE_OVERFLOW_UNDEFINED (type))
4411	return true;
4412
4413	wi::overflow_type ovf;
4414	signop sgn = TYPE_SIGN (type);
4415	wide_int wmax0 = lh.upper_bound ();
4416	wide_int wmax1 = rh.upper_bound ();
4417	wi::add (x: wmax0, y: wmax1, sgn, overflow: &ovf);
4418	if (ovf != wi::OVF_NONE)
4419	return false;
4420
4421	if (TYPE_UNSIGNED (type))
4422	return true;
4423
4424	wide_int wmin0 = lh.lower_bound ();
4425	wide_int wmin1 = rh.lower_bound ();
4426	wi::add (x: wmin0, y: wmin1, sgn, overflow: &ovf);
4427	if (ovf != wi::OVF_NONE)
4428	return false;
4429
4430	return true;
4431	}
4432
4433	bool
4434	operator_minus::overflow_free_p (const irange &lh, const irange &rh,
4435	relation_trio) const
4436	{
4437	if (lh.undefined_p () || rh.undefined_p ())
4438	return false;
4439
4440	tree type = lh.type ();
4441	if (TYPE_OVERFLOW_UNDEFINED (type))
4442	return true;
4443
4444	wi::overflow_type ovf;
4445	signop sgn = TYPE_SIGN (type);
4446	wide_int wmin0 = lh.lower_bound ();
4447	wide_int wmax1 = rh.upper_bound ();
4448	wi::sub (x: wmin0, y: wmax1, sgn, overflow: &ovf);
4449	if (ovf != wi::OVF_NONE)
4450	return false;
4451
4452	if (TYPE_UNSIGNED (type))
4453	return true;
4454
4455	wide_int wmax0 = lh.upper_bound ();
4456	wide_int wmin1 = rh.lower_bound ();
4457	wi::sub (x: wmax0, y: wmin1, sgn, overflow: &ovf);
4458	if (ovf != wi::OVF_NONE)
4459	return false;
4460
4461	return true;
4462	}
4463
4464	bool
4465	operator_mult::overflow_free_p (const irange &lh, const irange &rh,
4466	relation_trio) const
4467	{
4468	if (lh.undefined_p () || rh.undefined_p ())
4469	return false;
4470
4471	tree type = lh.type ();
4472	if (TYPE_OVERFLOW_UNDEFINED (type))
4473	return true;
4474
4475	wi::overflow_type ovf;
4476	signop sgn = TYPE_SIGN (type);
4477	wide_int wmax0 = lh.upper_bound ();
4478	wide_int wmax1 = rh.upper_bound ();
4479	wi::mul (x: wmax0, y: wmax1, sgn, overflow: &ovf);
4480	if (ovf != wi::OVF_NONE)
4481	return false;
4482
4483	if (TYPE_UNSIGNED (type))
4484	return true;
4485
4486	wide_int wmin0 = lh.lower_bound ();
4487	wide_int wmin1 = rh.lower_bound ();
4488	wi::mul (x: wmin0, y: wmin1, sgn, overflow: &ovf);
4489	if (ovf != wi::OVF_NONE)
4490	return false;
4491
4492	wi::mul (x: wmin0, y: wmax1, sgn, overflow: &ovf);
4493	if (ovf != wi::OVF_NONE)
4494	return false;
4495
4496	wi::mul (x: wmax0, y: wmin1, sgn, overflow: &ovf);
4497	if (ovf != wi::OVF_NONE)
4498	return false;
4499
4500	return true;
4501	}
4502
4503	#if CHECKING_P
4504	#include "selftest.h"
4505
4506	namespace selftest
4507	{
4508	#define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
4509	#define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
4510	#define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
4511	#define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
4512	#define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
4513	#define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
4514
4515	static void
4516	range_op_cast_tests ()
4517	{
4518	int_range<2> r0, r1, r2, rold;
4519	r0.set_varying (integer_type_node);
4520	wide_int maxint = r0.upper_bound ();
4521
4522	// If a range is in any way outside of the range for the converted
4523	// to range, default to the range for the new type.
4524	r0.set_varying (short_integer_type_node);
4525	wide_int minshort = r0.lower_bound ();
4526	wide_int maxshort = r0.upper_bound ();
4527	if (TYPE_PRECISION (integer_type_node)
4528	> TYPE_PRECISION (short_integer_type_node))
4529	{
4530	r1 = int_range<1> (integer_type_node,
4531	wi::zero (TYPE_PRECISION (integer_type_node)),
4532	maxint);
4533	range_cast (r&: r1, short_integer_type_node);
4534	ASSERT_TRUE (r1.lower_bound () == minshort
4535	&& r1.upper_bound() == maxshort);
4536	}
4537
4538	// (unsigned char)[-5,-1] => [251,255].
4539	r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
4540	range_cast (r&: r0, unsigned_char_type_node);
4541	ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
4542	UCHAR (251), UCHAR (255)));
4543	range_cast (r&: r0, signed_char_type_node);
4544	ASSERT_TRUE (r0 == rold);
4545
4546	// (signed char)[15, 150] => [-128,-106][15,127].
4547	r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
4548	range_cast (r&: r0, signed_char_type_node);
4549	r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
4550	r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
4551	r1.union_ (r2);
4552	ASSERT_TRUE (r1 == r0);
4553	range_cast (r&: r0, unsigned_char_type_node);
4554	ASSERT_TRUE (r0 == rold);
4555
4556	// (unsigned char)[-5, 5] => [0,5][251,255].
4557	r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
4558	range_cast (r&: r0, unsigned_char_type_node);
4559	r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
4560	r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
4561	r1.union_ (r2);
4562	ASSERT_TRUE (r0 == r1);
4563	range_cast (r&: r0, signed_char_type_node);
4564	ASSERT_TRUE (r0 == rold);
4565
4566	// (unsigned char)[-5,5] => [0,5][251,255].
4567	r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
4568	range_cast (r&: r0, unsigned_char_type_node);
4569	r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
4570	r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
4571	ASSERT_TRUE (r0 == r1);
4572
4573	// (unsigned char)[5U,1974U] => [0,255].
4574	r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
4575	range_cast (r&: r0, unsigned_char_type_node);
4576	ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
4577	range_cast (r&: r0, integer_type_node);
4578	// Going to a wider range should not sign extend.
4579	ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
4580
4581	// (unsigned char)[-350,15] => [0,255].
4582	r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
4583	range_cast (r&: r0, unsigned_char_type_node);
4584	ASSERT_TRUE (r0 == (int_range<1>
4585	(unsigned_char_type_node,
4586	min_limit (unsigned_char_type_node),
4587	max_limit (unsigned_char_type_node))));
4588
4589	// Casting [-120,20] from signed char to unsigned short.
4590	// => [0, 20][0xff88, 0xffff].
4591	r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
4592	range_cast (r&: r0, short_unsigned_type_node);
4593	r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
4594	r2 = int_range<1> (short_unsigned_type_node,
4595	UINT16 (0xff88), UINT16 (0xffff));
4596	r1.union_ (r2);
4597	ASSERT_TRUE (r0 == r1);
4598	// A truncating cast back to signed char will work because [-120, 20]
4599	// is representable in signed char.
4600	range_cast (r&: r0, signed_char_type_node);
4601	ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
4602	SCHAR (-120), SCHAR (20)));
4603
4604	// unsigned char -> signed short
4605	// (signed short)[(unsigned char)25, (unsigned char)250]
4606	// => [(signed short)25, (signed short)250]
4607	r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
4608	range_cast (r&: r0, short_integer_type_node);
4609	r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
4610	ASSERT_TRUE (r0 == r1);
4611	range_cast (r&: r0, unsigned_char_type_node);
4612	ASSERT_TRUE (r0 == rold);
4613
4614	// Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
4615	r0 = int_range<1> (long_long_integer_type_node,
4616	min_limit (long_long_integer_type_node),
4617	max_limit (long_long_integer_type_node));
4618	range_cast (r&: r0, short_unsigned_type_node);
4619	r1 = int_range<1> (short_unsigned_type_node,
4620	min_limit (short_unsigned_type_node),
4621	max_limit (short_unsigned_type_node));
4622	ASSERT_TRUE (r0 == r1);
4623
4624	// Casting NONZERO to a narrower type will wrap/overflow so
4625	// it's just the entire range for the narrower type.
4626	//
4627	// "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4628	// is outside of the range of a smaller range, return the full
4629	// smaller range.
4630	if (TYPE_PRECISION (integer_type_node)
4631	> TYPE_PRECISION (short_integer_type_node))
4632	{
4633	r0 = range_nonzero (integer_type_node);
4634	range_cast (r&: r0, short_integer_type_node);
4635	r1 = int_range<1> (short_integer_type_node,
4636	min_limit (short_integer_type_node),
4637	max_limit (short_integer_type_node));
4638	ASSERT_TRUE (r0 == r1);
4639	}
4640
4641	// Casting NONZERO from a narrower signed to a wider signed.
4642	//
4643	// NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4644	// Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4645	r0 = range_nonzero (short_integer_type_node);
4646	range_cast (r&: r0, integer_type_node);
4647	r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
4648	r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
4649	r1.union_ (r2);
4650	ASSERT_TRUE (r0 == r1);
4651	}
4652
4653	static void
4654	range_op_lshift_tests ()
4655	{
4656	// Test that 0x808.... & 0x8.... still contains 0x8....
4657	// for a large set of numbers.
4658	{
4659	int_range_max res;
4660	tree big_type = long_long_unsigned_type_node;
4661	unsigned big_prec = TYPE_PRECISION (big_type);
4662	// big_num = 0x808,0000,0000,0000
4663	wide_int big_num = wi::lshift (x: wi::uhwi (val: 0x808, precision: big_prec),
4664	y: wi::uhwi (val: 48, precision: big_prec));
4665	op_bitwise_and.fold_range (r&: res, type: big_type,
4666	lh: int_range <1> (big_type),
4667	rh: int_range <1> (big_type, big_num, big_num));
4668	// val = 0x8,0000,0000,0000
4669	wide_int val = wi::lshift (x: wi::uhwi (val: 8, precision: big_prec),
4670	y: wi::uhwi (val: 48, precision: big_prec));
4671	ASSERT_TRUE (res.contains_p (val));
4672	}
4673
4674	if (TYPE_PRECISION (unsigned_type_node) > 31)
4675	{
4676	// unsigned VARYING = op1 << 1 should be VARYING.
4677	int_range<2> lhs (unsigned_type_node);
4678	int_range<2> shift (unsigned_type_node, INT (1), INT (1));
4679	int_range_max op1;
4680	op_lshift.op1_range (r&: op1, unsigned_type_node, lhs, op2: shift);
4681	ASSERT_TRUE (op1.varying_p ());
4682
4683	// 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4684	int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
4685	op_lshift.op1_range (r&: op1, unsigned_type_node, lhs: zero, op2: shift);
4686	ASSERT_TRUE (op1.num_pairs () == 2);
4687	// Remove the [0,0] range.
4688	op1.intersect (zero);
4689	ASSERT_TRUE (op1.num_pairs () == 1);
4690	// op1 << 1 should be [0x8000,0x8000] << 1,
4691	// which should result in [0,0].
4692	int_range_max result;
4693	op_lshift.fold_range (r&: result, unsigned_type_node, op1, op2: shift);
4694	ASSERT_TRUE (result == zero);
4695	}
4696	// signed VARYING = op1 << 1 should be VARYING.
4697	if (TYPE_PRECISION (integer_type_node) > 31)
4698	{
4699	// unsigned VARYING = op1 << 1 should be VARYING.
4700	int_range<2> lhs (integer_type_node);
4701	int_range<2> shift (integer_type_node, INT (1), INT (1));
4702	int_range_max op1;
4703	op_lshift.op1_range (r&: op1, integer_type_node, lhs, op2: shift);
4704	ASSERT_TRUE (op1.varying_p ());
4705
4706	// 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4707	int_range<2> zero (integer_type_node, INT (0), INT (0));
4708	op_lshift.op1_range (r&: op1, integer_type_node, lhs: zero, op2: shift);
4709	ASSERT_TRUE (op1.num_pairs () == 2);
4710	// Remove the [0,0] range.
4711	op1.intersect (zero);
4712	ASSERT_TRUE (op1.num_pairs () == 1);
4713	// op1 << 1 should be [0x8000,0x8000] << 1,
4714	// which should result in [0,0].
4715	int_range_max result;
4716	op_lshift.fold_range (r&: result, unsigned_type_node, op1, op2: shift);
4717	ASSERT_TRUE (result == zero);
4718	}
4719	}
4720
4721	static void
4722	range_op_rshift_tests ()
4723	{
4724	// unsigned: [3, MAX] = OP1 >> 1
4725	{
4726	int_range_max lhs (unsigned_type_node,
4727	UINT (3), max_limit (unsigned_type_node));
4728	int_range_max one (unsigned_type_node,
4729	wi::one (TYPE_PRECISION (unsigned_type_node)),
4730	wi::one (TYPE_PRECISION (unsigned_type_node)));
4731	int_range_max op1;
4732	op_rshift.op1_range (r&: op1, unsigned_type_node, lhs, op2: one);
4733	ASSERT_FALSE (op1.contains_p (UINT (3)));
4734	}
4735
4736	// signed: [3, MAX] = OP1 >> 1
4737	{
4738	int_range_max lhs (integer_type_node,
4739	INT (3), max_limit (integer_type_node));
4740	int_range_max one (integer_type_node, INT (1), INT (1));
4741	int_range_max op1;
4742	op_rshift.op1_range (r&: op1, integer_type_node, lhs, op2: one);
4743	ASSERT_FALSE (op1.contains_p (INT (-2)));
4744	}
4745
4746	// This is impossible, so OP1 should be [].
4747	// signed: [MIN, MIN] = OP1 >> 1
4748	{
4749	int_range_max lhs (integer_type_node,
4750	min_limit (integer_type_node),
4751	min_limit (integer_type_node));
4752	int_range_max one (integer_type_node, INT (1), INT (1));
4753	int_range_max op1;
4754	op_rshift.op1_range (r&: op1, integer_type_node, lhs, op2: one);
4755	ASSERT_TRUE (op1.undefined_p ());
4756	}
4757
4758	// signed: ~[-1] = OP1 >> 31
4759	if (TYPE_PRECISION (integer_type_node) > 31)
4760	{
4761	int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
4762	int_range_max shift (integer_type_node, INT (31), INT (31));
4763	int_range_max op1;
4764	op_rshift.op1_range (r&: op1, integer_type_node, lhs, op2: shift);
4765	int_range_max negatives = range_negatives (integer_type_node);
4766	negatives.intersect (op1);
4767	ASSERT_TRUE (negatives.undefined_p ());
4768	}
4769	}
4770
4771	static void
4772	range_op_bitwise_and_tests ()
4773	{
4774	int_range_max res;
4775	wide_int min = min_limit (integer_type_node);
4776	wide_int max = max_limit (integer_type_node);
4777	wide_int tiny = wi::add (x: min, y: wi::one (TYPE_PRECISION (integer_type_node)));
4778	int_range_max i1 (integer_type_node, tiny, max);
4779	int_range_max i2 (integer_type_node, INT (255), INT (255));
4780
4781	// [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4782	op_bitwise_and.op1_range (r&: res, integer_type_node, lhs: i1, op2: i2);
4783	ASSERT_TRUE (res == int_range<1> (integer_type_node));
4784
4785	// VARYING = OP1 & 255: OP1 is VARYING
4786	i1 = int_range<1> (integer_type_node);
4787	op_bitwise_and.op1_range (r&: res, integer_type_node, lhs: i1, op2: i2);
4788	ASSERT_TRUE (res == int_range<1> (integer_type_node));
4789
4790	// For 0 = x & MASK, x is ~MASK.
4791	{
4792	int_range<2> zero (integer_type_node, INT (0), INT (0));
4793	int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
4794	op_bitwise_and.op1_range (r&: res, integer_type_node, lhs: zero, op2: mask);
4795	wide_int inv = wi::shwi (val: ~7U, TYPE_PRECISION (integer_type_node));
4796	ASSERT_TRUE (res.get_nonzero_bits () == inv);
4797	}
4798
4799	// (NONZERO | X) is nonzero.
4800	i1.set_nonzero (integer_type_node);
4801	i2.set_varying (integer_type_node);
4802	op_bitwise_or.fold_range (r&: res, integer_type_node, lh: i1, rh: i2);
4803	ASSERT_TRUE (res.nonzero_p ());
4804
4805	// (NEGATIVE | X) is nonzero.
4806	i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
4807	i2.set_varying (integer_type_node);
4808	op_bitwise_or.fold_range (r&: res, integer_type_node, lh: i1, rh: i2);
4809	ASSERT_FALSE (res.contains_p (INT (0)));
4810	}
4811
4812	static void
4813	range_relational_tests ()
4814	{
4815	int_range<2> lhs (unsigned_char_type_node);
4816	int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
4817	int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
4818
4819	// Never wrapping additions mean LHS > OP1.
4820	relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4821	ASSERT_TRUE (code == VREL_GT);
4822
4823	// Most wrapping additions mean nothing...
4824	op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
4825	op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
4826	code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4827	ASSERT_TRUE (code == VREL_VARYING);
4828
4829	// However, always wrapping additions mean LHS < OP1.
4830	op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
4831	op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
4832	code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4833	ASSERT_TRUE (code == VREL_LT);
4834	}
4835
4836	void
4837	range_op_tests ()
4838	{
4839	range_op_rshift_tests ();
4840	range_op_lshift_tests ();
4841	range_op_bitwise_and_tests ();
4842	range_op_cast_tests ();
4843	range_relational_tests ();
4844
4845	extern void range_op_float_tests ();
4846	range_op_float_tests ();
4847	}
4848
4849	} // namespace selftest
4850
4851	#endif // CHECKING_P
4852