/* Combines MIN and MAX as follows:

   MIN =   01010010101001010010

   MAX =   01010010100000010010

   result: 01010010100000000000

   This tells us which bits are always 1 for any X in [MIN, MAX].  */

static tree

bits_always_set (tree min, tree max)

{

  tree xored, shift, result;

  int xor_hi;

  result = int_const_binop (BIT_AND_EXPR, min, max, 0);

  /* Result may have lower common bits set, need to clear those.  */

  /* Find bit position of highest differing bit.  */

  xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);

  xor_hi = tree_floor_log2 (xored);

  /* Is there such bit?  */

  if (xor_hi >= 0)

    {

      shift = build_int_cst (NULL_TREE, xor_hi + 1);

      /* Shift right, then left, clearing this bit and all lower bits too.  */

      result = int_const_binop (RSHIFT_EXPR, result, shift, 0);

      result = int_const_binop (LSHIFT_EXPR, result, shift, 0);

    }

  return result;

}

/* Combines MIN and MAX as follows:

   MAX =   01010010101001010010

   MIN =   01010010100000010010

   result: 01010010101111111111.

   Zeros tell us which bits are always 0 for any X in [MIN, MAX].

   Conversely, ones show which bits can be set.  */

static tree

bits_maybe_set (tree min, tree max)

{

  tree xored, shift, result, one, mask;

  int xor_hi;

  result = int_const_binop (BIT_IOR_EXPR, min, max, 0);

  /* Find bit position of highest differing bit.  */

  xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);

  xor_hi = tree_floor_log2 (xored);

  /* Is there such bit and it's not bit 0?  */

  if (xor_hi > 0)

    {

      /* Build a 0000001111 mask.  */

      shift = build_int_cst (NULL_TREE, xor_hi);

      one = build_int_cst (TREE_TYPE (max), 1);

      mask = int_const_binop (LSHIFT_EXPR, one, shift, 0);

      mask = int_const_binop (MINUS_EXPR, mask, one, 0);

      /* OR it to the result.  */

      result = int_const_binop (BIT_IOR_EXPR, result, mask, 0);

    }

  return result;

}

static int

integer_nonnegative_range (value_range_t *vr)

{

  if (vr->type == VR_RANGE

      && TREE_CODE (vr->min) == INTEGER_CST

      && TREE_CODE (vr->max) == INTEGER_CST

      && tree_int_cst_sgn (vr->min) >= 0

      && tree_int_cst_sgn (vr->max) >= 0

      && !TREE_OVERFLOW (vr->max))

    {

      return 1;

    }

  return 0;

}

  tree always_set0, always_set1;

  tree maybe_set0, maybe_set1;

      && code != BIT_IOR_EXPR

  /* Bitwise ops.  */

  /* Width and signedness of operands is always the same here.  */

  if (code == BIT_AND_EXPR)

    {

      if (integer_nonnegative_range (&vr0))

	{

	  if (integer_nonnegative_range (&vr1))

	    {

	      /* In always_setX, ones indicate "always set" bits.  */

	      always_set0 = bits_always_set (vr0.min, vr0.max);

	      always_set1 = bits_always_set (vr1.min, vr1.max);

	      /* In maybe_setX, ZEROES indicate "always unset" bits,

	         ones indicate bits which are "maybe set".  */

	      maybe_set0 = bits_maybe_set (vr0.min, vr0.max);

	      maybe_set1 = bits_maybe_set (vr1.min, vr1.max);

	      /* If bit is always set in a AND in b,

	         it will be set in (a & b).  */

	      min = int_const_binop (BIT_AND_EXPR,

				     always_set0, always_set1, 0);

	      /* If bit is maybe set in a AND in b,

	         it may be set in (a & b).

	         Example: max(010x & 10xx) = 0001

	         (maybe_set0 = 0101, maybe_set1 = 1011).  */

	      max = int_const_binop (BIT_AND_EXPR, maybe_set0, maybe_set1, 0);

	      set_value_range (vr, VR_RANGE, min, max, NULL);

	      return;

	    }

	  /* Only op0 has nonnegative range.

	     We positively sure that result of (op0 & op1) can't be

	     larger than vr0.max.  */

	  max = vr0.max;

	  min = build_int_cst (expr_type, 0);

	  set_value_range (vr, VR_RANGE, min, max, NULL);

	  return;

	}

      if (integer_nonnegative_range (&vr1))

	{

	  /* Only op1 has nonnegative range.  */

	  max = vr1.max;

	  min = build_int_cst (expr_type, 0);

	  set_value_range (vr, VR_RANGE, min, max, NULL);

	  return;

	}

      set_value_range_to_varying (vr);

      return;

    }

  if (code == BIT_IOR_EXPR)

    {

      if (integer_nonnegative_range (&vr0))

	{

	  if (integer_nonnegative_range (&vr1))

	    {

	      always_set0 = bits_always_set (vr0.min, vr0.max);

	      always_set1 = bits_always_set (vr1.min, vr1.max);

	      maybe_set0 = bits_maybe_set (vr0.min, vr0.max);

	      maybe_set1 = bits_maybe_set (vr1.min, vr1.max);

	      /* If bit is always set in a OR in b,

	         it will be set in (a | b).  */

	      min = int_const_binop (BIT_IOR_EXPR,

				     always_set0, always_set1, 0);

	      /* If bit is maybe set in a OR in b,

	         it may be set in (a | b).

	         Example: max(101x | 01xx) = 1111.  */

	      max = int_const_binop (BIT_IOR_EXPR, maybe_set0, maybe_set1, 0);

	      set_value_range (vr, VR_RANGE, min, max, NULL);

	      return;

	    }

	  /* Only op0 has nonnegative range.  If result is unsigned,

	     we still can derive that (op0|op1) >= op0.min.  */

	  if (TYPE_UNSIGNED (expr_type))

	    {

	      min = vr0.min;

	      max = TYPE_MAX_VALUE (expr_type);

	      set_value_range (vr, VR_RANGE, min, max, NULL);

	      set_value_range (vr, VR_RANGE, min, max, NULL);

	      return;

	    }

	  /* TODO: signed type has antirange because (op0|op1) never falls

	     into [0..vr0.min-1]. antirange is [-inf,-1]..[vr0.min,+inf].  */

	  set_value_range_to_varying (vr);

	  return;

	}

      if (integer_nonnegative_range (&vr1))

	{

	  /* Only op1 has nonnegative range.  */

	  if (TYPE_UNSIGNED (expr_type))

	    {

	      min = vr1.min;

	      max = TYPE_MAX_VALUE (expr_type);

	      set_value_range (vr, VR_RANGE, min, max, NULL);

	      return;

	    }

	}

      set_value_range_to_varying (vr);

      return;

    }