[thirdparty/gcc.git] / gcc / wide-int-range.h

/* Support routines for range operations on wide ints.
   Copyright (C) 2018-2019 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_WIDE_INT_RANGE_H
#define GCC_WIDE_INT_RANGE_H

extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
					  enum tree_code code, signop sign,
					  const wide_int &, const wide_int &,
					  const wide_int &, const wide_int &,
					  bool overflow_undefined);
extern bool wide_int_range_mult_wrapping (wide_int &res_lb,
					  wide_int &res_ub,
					  signop sign,
					  unsigned prec,
					  const wide_int &min0_,
					  const wide_int &max0_,
					  const wide_int &min1_,
					  const wide_int &max1_);
extern bool wide_int_range_multiplicative_op (wide_int &res_lb,
					      wide_int &res_ub,
					      enum tree_code code,
					      signop sign,
					      unsigned prec,
					      const wide_int &vr0_lb,
					      const wide_int &vr0_ub,
					      const wide_int &vr1_lb,
					      const wide_int &vr1_ub,
					      bool overflow_undefined);
extern bool wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
				   signop sign, unsigned prec,
				   const wide_int &, const wide_int &,
				   const wide_int &, const wide_int &,
				   bool overflow_undefined);
extern void wide_int_range_set_zero_nonzero_bits (signop,
						  const wide_int &lb,
						  const wide_int &ub,
						  wide_int &may_be_nonzero,
						  wide_int &must_be_nonzero);
extern bool wide_int_range_optimize_bit_op (wide_int &res_lb, wide_int &res_ub,
					    enum tree_code code,
					    signop sign,
					    const wide_int &vr0_lb,
					    const wide_int &vr0_ub,
					    const wide_int &vr1_lb,
					    const wide_int &vr1_ub);
extern bool wide_int_range_get_mask_and_bounds (wide_int &mask,
						wide_int &lower_bound,
						wide_int &upper_bound,
						const wide_int &vr0_min,
						const wide_int &vr0_max,
						const wide_int &vr1_min,
						const wide_int &vr1_max);
extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
				    signop sign,
				    unsigned prec,
				    const wide_int &must_be_nonzero0,
				    const wide_int &may_be_nonzero0,
				    const wide_int &must_be_nonzero1,
				    const wide_int &may_be_nonzero1);
extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
				    signop sign,
				    const wide_int &vr0_min,
				    const wide_int &vr0_max,
				    const wide_int &vr1_min,
				    const wide_int &vr1_max,
				    const wide_int &must_be_nonzero0,
				    const wide_int &may_be_nonzero0,
				    const wide_int &must_be_nonzero1,
				    const wide_int &may_be_nonzero1);
extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
				    signop sign,
				    unsigned prec,
				    const wide_int &vr0_min,
				    const wide_int &vr0_max,
				    const wide_int &vr1_min,
				    const wide_int &vr1_max,
				    const wide_int &must_be_nonzero0,
				    const wide_int &may_be_nonzero0,
				    const wide_int &must_be_nonzero1,
				    const wide_int &may_be_nonzero1);
extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
				      signop sign,
				      unsigned prec,
				      const wide_int &vr0_min,
				      const wide_int &vr0_max,
				      const wide_int &vr1_min,
				      const wide_int &vr1_max);
extern bool wide_int_range_abs (wide_int &min, wide_int &max,
				signop sign, unsigned prec,
				const wide_int &vr0_min,
				const wide_int &vr0_max,
				bool overflow_undefined);
extern bool wide_int_range_convert (wide_int &min, wide_int &max,
				    signop inner_sign,
				    unsigned inner_prec,
				    signop outer_sign,
				    unsigned outer_prec,
				    const wide_int &vr0_min,
				    const wide_int &vr0_max);
extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
				enum tree_code code,
				signop sign, unsigned prec,
				const wide_int &dividend_min,
				const wide_int &dividend_max,
				const wide_int &divisor_min,
				const wide_int &divisor_max,
				bool overflow_undefined,
				bool &extra_range_p,
				wide_int &extra_min, wide_int &extra_max);

/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior,
   interpreting MIN and MAX according to SIGN.  */

inline bool
wide_int_range_shift_undefined_p (signop sign, unsigned prec,
				  const wide_int &min, const wide_int &max)
{
  /* ?? Note: The original comment said this only applied to
     RSHIFT_EXPR, but it was being applied to both left and right
     shifts.  */

  /* Shifting by any values outside [0..prec-1], gets undefined
     behavior from the shift operation.  We cannot even trust
     SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
     shifts, and the operation at the tree level may be widened.  */
  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
}

/* Calculate MIN/MAX_EXPR of two ranges and store the result in [MIN, MAX].  */

inline bool
wide_int_range_min_max (wide_int &min, wide_int &max,
			tree_code code,
			signop sign, unsigned prec,
			const wide_int &vr0_min, const wide_int &vr0_max,
			const wide_int &vr1_min, const wide_int &vr1_max)
{
  wi::overflow_type overflow;
  wide_int_binop (min, code, vr0_min, vr1_min, sign, &overflow);
  wide_int_binop (max, code, vr0_max, vr1_max, sign, &overflow);
  /* If the new range covers the entire domain, that's really no range
     at all.  */
  if (min == wi::min_value (prec, sign)
      && max == wi::max_value (prec, sign))
    return false;
  return true;
}

/* Return TRUE if 0 is within [WMIN, WMAX].  */

inline bool
wide_int_range_includes_zero_p (const wide_int &wmin, const wide_int &wmax,
				signop sign)
{
  return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign);
}

/* Return TRUE if [WMIN, WMAX] is the singleton 0.  */

inline bool
wide_int_range_zero_p (const wide_int &wmin, const wide_int &wmax,
		       unsigned prec)
{
  return wmin == wmax && wi::eq_p (wmin, wi::zero (prec));
}

#endif /* GCC_WIDE_INT_RANGE_H */
Commit	Line	Data
5c9c1e7c	1	/* Support routines for range operations on wide ints.
fbd26352	2	Copyright (C) 2018-2019 Free Software Foundation, Inc.
5c9c1e7c	3
	4	This file is part of GCC.
	5
	6	GCC is free software; you can redistribute it and/or modify
	7	it under the terms of the GNU General Public License as published by
	8	the Free Software Foundation; either version 3, or (at your option)
	9	any later version.
	10
	11	GCC is distributed in the hope that it will be useful,
	12	but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	GNU General Public License for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with GCC; see the file COPYING3. If not see
	18	<http://www.gnu.org/licenses/>. */
	19
	20	#ifndef GCC_WIDE_INT_RANGE_H
	21	#define GCC_WIDE_INT_RANGE_H
	22
	23	extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
	24	enum tree_code code, signop sign,
	25	const wide_int &, const wide_int &,
	26	const wide_int &, const wide_int &,
	27	bool overflow_undefined);
	28	extern bool wide_int_range_mult_wrapping (wide_int &res_lb,
	29	wide_int &res_ub,
	30	signop sign,
	31	unsigned prec,
	32	const wide_int &min0_,
	33	const wide_int &max0_,
	34	const wide_int &min1_,
	35	const wide_int &max1_);
	36	extern bool wide_int_range_multiplicative_op (wide_int &res_lb,
	37	wide_int &res_ub,
	38	enum tree_code code,
	39	signop sign,
	40	unsigned prec,
	41	const wide_int &vr0_lb,
	42	const wide_int &vr0_ub,
	43	const wide_int &vr1_lb,
	44	const wide_int &vr1_ub,
2e73c0cf	45	bool overflow_undefined);
5c9c1e7c	46	extern bool wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
	47	signop sign, unsigned prec,
	48	const wide_int &, const wide_int &,
	49	const wide_int &, const wide_int &,
2e73c0cf	50	bool overflow_undefined);
5c9c1e7c	51	extern void wide_int_range_set_zero_nonzero_bits (signop,
	52	const wide_int &lb,
	53	const wide_int &ub,
	54	wide_int &may_be_nonzero,
	55	wide_int &must_be_nonzero);
f0c8c617	56	extern bool wide_int_range_optimize_bit_op (wide_int &res_lb, wide_int &res_ub,
	57	enum tree_code code,
	58	signop sign,
	59	const wide_int &vr0_lb,
	60	const wide_int &vr0_ub,
	61	const wide_int &vr1_lb,
	62	const wide_int &vr1_ub);
	63	extern bool wide_int_range_get_mask_and_bounds (wide_int &mask,
	64	wide_int &lower_bound,
	65	wide_int &upper_bound,
	66	const wide_int &vr0_min,
	67	const wide_int &vr0_max,
	68	const wide_int &vr1_min,
	69	const wide_int &vr1_max);
5c9c1e7c	70	extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
	71	signop sign,
	72	unsigned prec,
	73	const wide_int &must_be_nonzero0,
	74	const wide_int &may_be_nonzero0,
	75	const wide_int &must_be_nonzero1,
	76	const wide_int &may_be_nonzero1);
	77	extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
	78	signop sign,
	79	const wide_int &vr0_min,
	80	const wide_int &vr0_max,
	81	const wide_int &vr1_min,
	82	const wide_int &vr1_max,
	83	const wide_int &must_be_nonzero0,
	84	const wide_int &may_be_nonzero0,
	85	const wide_int &must_be_nonzero1,
	86	const wide_int &may_be_nonzero1);
	87	extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
	88	signop sign,
	89	unsigned prec,
	90	const wide_int &vr0_min,
	91	const wide_int &vr0_max,
	92	const wide_int &vr1_min,
	93	const wide_int &vr1_max,
	94	const wide_int &must_be_nonzero0,
	95	const wide_int &may_be_nonzero0,
	96	const wide_int &must_be_nonzero1,
	97	const wide_int &may_be_nonzero1);
	98	extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
	99	signop sign,
	100	unsigned prec,
	101	const wide_int &vr0_min,
	102	const wide_int &vr0_max,
	103	const wide_int &vr1_min,
	104	const wide_int &vr1_max);
9e4ef9ee	105	extern bool wide_int_range_abs (wide_int &min, wide_int &max,
	106	signop sign, unsigned prec,
	107	const wide_int &vr0_min,
	108	const wide_int &vr0_max,
	109	bool overflow_undefined);
ed81b3ca	110	extern bool wide_int_range_convert (wide_int &min, wide_int &max,
	111	signop inner_sign,
	112	unsigned inner_prec,
	113	signop outer_sign,
	114	unsigned outer_prec,
	115	const wide_int &vr0_min,
	116	const wide_int &vr0_max);
dcea420d	117	extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
	118	enum tree_code code,
	119	signop sign, unsigned prec,
	120	const wide_int &dividend_min,
	121	const wide_int &dividend_max,
	122	const wide_int &divisor_min,
	123	const wide_int &divisor_max,
	124	bool overflow_undefined,
dcea420d	125	bool &extra_range_p,
dcea420d	126	wide_int &extra_min, wide_int &extra_max);
5c9c1e7c	127
f1eca10f	128	/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior,
f1eca10f	129	interpreting MIN and MAX according to SIGN. */
5c9c1e7c	130
5c9c1e7c	131	inline bool
f1eca10f	132	wide_int_range_shift_undefined_p (signop sign, unsigned prec,
5c9c1e7c	133	const wide_int &min, const wide_int &max)
	134	{
	135	/* ?? Note: The original comment said this only applied to
	136	RSHIFT_EXPR, but it was being applied to both left and right
	137	shifts. */
	138
	139	/* Shifting by any values outside [0..prec-1], gets undefined
	140	behavior from the shift operation. We cannot even trust
	141	SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
	142	shifts, and the operation at the tree level may be widened. */
f1eca10f	143	return wi::lt_p (min, 0, sign) \|\| wi::ge_p (max, prec, sign);
5c9c1e7c	144	}
5c9c1e7c	145
9e4ef9ee	146	/* Calculate MIN/MAX_EXPR of two ranges and store the result in [MIN, MAX]. */
	147
	148	inline bool
	149	wide_int_range_min_max (wide_int &min, wide_int &max,
	150	tree_code code,
	151	signop sign, unsigned prec,
	152	const wide_int &vr0_min, const wide_int &vr0_max,
	153	const wide_int &vr1_min, const wide_int &vr1_max)
	154	{
	155	wi::overflow_type overflow;
	156	wide_int_binop (min, code, vr0_min, vr1_min, sign, &overflow);
	157	wide_int_binop (max, code, vr0_max, vr1_max, sign, &overflow);
	158	/* If the new range covers the entire domain, that's really no range
	159	at all. */
	160	if (min == wi::min_value (prec, sign)
	161	&& max == wi::max_value (prec, sign))
	162	return false;
	163	return true;
	164	}
	165
dcea420d	166	/* Return TRUE if 0 is within [WMIN, WMAX]. */
	167
	168	inline bool
	169	wide_int_range_includes_zero_p (const wide_int &wmin, const wide_int &wmax,
	170	signop sign)
	171	{
	172	return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign);
	173	}
	174
	175	/* Return TRUE if [WMIN, WMAX] is the singleton 0. */
	176
	177	inline bool
	178	wide_int_range_zero_p (const wide_int &wmin, const wide_int &wmax,
	179	unsigned prec)
	180	{
	181	return wmin == wmax && wi::eq_p (wmin, wi::zero (prec));
	182	}
	183
5c9c1e7c	184	#endif /* GCC_WIDE_INT_RANGE_H */