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