Attachment 16009 Details for Bug 28632 – Updated patch against current svn

[patch] Updated patch against current svn

1.patch (text/plain), 8.29 KB, created by Denis Vlasenko on 2008-08-04 11:25:40 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Denis Vlasenko

Created: 2008-08-04 11:25:40 UTC

Size: 8.29 KB

patch

obsolete

>diff -d -urpN gcc-4.4.svn.0/gcc/tree-vrp.c gcc-4.4.svn.1/gcc/tree-vrp.c
>--- gcc-4.4.svn.0/gcc/tree-vrp.c	2008-08-01 15:47:26.000000000 +0200
>+++ gcc-4.4.svn.1/gcc/tree-vrp.c	2008-08-04 12:30:54.000000000 +0200
>@@ -1995,6 +1995,80 @@ vrp_int_const_binop (enum tree_code code
>   return res;
> }
> 
>+/* 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;
>+}
> 
> /* Extract range information from a binary expression EXPR based on
>    the ranges of each of its operands and the expression code.  */
>@@ -2007,6 +2081,8 @@ extract_range_from_binary_expr (value_ra
>   enum value_range_type type;
>   tree min, max;
>   int cmp;
>+  tree always_set0, always_set1;
>+  tree maybe_set0, maybe_set1;
>   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
>   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
> 
>@@ -2025,6 +2101,7 @@ extract_range_from_binary_expr (value_ra
>       && code != MIN_EXPR
>       && code != MAX_EXPR
>       && code != BIT_AND_EXPR
>+      && code != BIT_IOR_EXPR
>       && code != TRUTH_AND_EXPR
>       && code != TRUTH_OR_EXPR)
>     {
>@@ -2048,6 +2125,104 @@ extract_range_from_binary_expr (value_ra
>   else
>     set_value_range_to_varying (&vr1);
> 
>+  /* 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;
>+    }
>+
>   /* If either range is UNDEFINED, so is the result.  */
>   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
>     {
>@@ -2059,12 +2234,8 @@ extract_range_from_binary_expr (value_ra
>   type = vr0.type;
> 
>   /* Refuse to operate on VARYING ranges, ranges of different kinds
>-     and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
>-     because we may be able to derive a useful range even if one of
>-     the operands is VR_VARYING or symbolic range.  TODO, we may be
>-     able to derive anti-ranges in some cases.  */
>-  if (code != BIT_AND_EXPR
>-      && code != TRUTH_AND_EXPR
>+     and symbolic ranges.  */
>+  if (code != TRUTH_AND_EXPR
>       && code != TRUTH_OR_EXPR
>       && (vr0.type == VR_VARYING
> 	  || vr1.type == VR_VARYING
>@@ -2342,33 +2513,6 @@ extract_range_from_binary_expr (value_ra
>       min = vrp_int_const_binop (code, vr0.min, vr1.max);
>       max = vrp_int_const_binop (code, vr0.max, vr1.min);
>     }
>-  else if (code == BIT_AND_EXPR)
>-    {
>-      if (vr0.type == VR_RANGE
>-	  && vr0.min == vr0.max
>-	  && TREE_CODE (vr0.max) == INTEGER_CST
>-	  && !TREE_OVERFLOW (vr0.max)
>-	  && tree_int_cst_sgn (vr0.max) >= 0)
>-	{
>-	  min = build_int_cst (expr_type, 0);
>-	  max = vr0.max;
>-	}
>-      else if (vr1.type == VR_RANGE
>-	       && vr1.min == vr1.max
>-	       && TREE_CODE (vr1.max) == INTEGER_CST
>-	       && !TREE_OVERFLOW (vr1.max)
>-	       && tree_int_cst_sgn (vr1.max) >= 0)
>-	{
>-	  type = VR_RANGE;
>-	  min = build_int_cst (expr_type, 0);
>-	  max = vr1.max;
>-	}
>-      else
>-	{
>-	  set_value_range_to_varying (vr);
>-	  return;
>-	}
>-    }
>   else
>     gcc_unreachable ();
>

Actions: View | Diff

Attachments on bug 28632: 12035 | 12036 | 12067 | 16009 | 16010 | 16011 | 16012 | 16050 | 16113 | 16114 | 18044 | 21156 | 21162