Attachment 16011 Details for Bug 28632 – The instrumented version of the patch

[patch] The instrumented version of the patch

1working2.patch (text/plain), 13.26 KB, created by Denis Vlasenko on 2008-08-04 11:34:53 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Denis Vlasenko

Created: 2008-08-04 11:34:53 UTC

Size: 13.26 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-03 02:46:29.000000000 +0200
>@@ -1995,6 +1995,143 @@ vrp_int_const_binop (enum tree_code code
>   return res;
> }
> 
>+#define VDA_DEBUG 0
>+
>+#if VDA_DEBUG
>+static FILE *vda_file;
>+#endif
>+
>+/* 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);
>+    }
>+#if VDA_DEBUG
>+  if (vda_file)
>+    {
>+      tree res_type = TREE_TYPE (result);
>+      fprintf (vda_file, "// %s(", "bits_always_set");
>+      print_generic_expr (vda_file, min, 0);
>+      fprintf (vda_file, ",");
>+      print_generic_expr (vda_file, max, 0);
>+      fprintf (vda_file, ")=[%c%ld]", TYPE_UNSIGNED (res_type) ? 'u' : 's',
>+	       tree_to_double_int (TYPE_SIZE (res_type)).low);
>+      print_generic_expr (vda_file, result, 0);
>+      fprintf (vda_file, "\n");
>+    }
>+#endif
>+  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);
>+    }
>+#if VDA_DEBUG
>+  if (vda_file)
>+    {
>+      tree res_type = TREE_TYPE (result);
>+      fprintf (vda_file, "// %s(", "bits_maybe_set");
>+      print_generic_expr (vda_file, min, 0);
>+      fprintf (vda_file, ",");
>+      print_generic_expr (vda_file, max, 0);
>+      fprintf (vda_file, ")=[%c%ld]", TYPE_UNSIGNED (res_type) ? 'u' : 's',
>+	       tree_to_double_int (TYPE_SIZE (res_type)).low);
>+      print_generic_expr (vda_file, result, 0);
>+      fprintf (vda_file, "\n");
>+    }
>+#endif
>+  return result;
>+}
>+
>+#if !VDA_DEBUG
>+/* Only vr is used if not debugging.  */
>+#define integer_nonnegative_range(vr, val, vall) integer_nonnegative_range(vr)
>+#endif
>+static int
>+integer_nonnegative_range (value_range_t *vr, tree val, char vall)
>+{
>+  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))
>+    {
>+#if VDA_DEBUG
>+      if (vda_file)
>+	{
>+	  tree val_type = TREE_TYPE (val);
>+	  fprintf (vda_file, "// %c %s(", vall, "integer_nonnegative_range");
>+	  print_generic_expr (vda_file, val_type, 0);
>+	  fprintf (vda_file, "[%c%ld],[",
>+		   TYPE_UNSIGNED (val_type) ? 'u' : 's',
>+		   tree_to_double_int (TYPE_SIZE (val_type)).low);
>+	  print_generic_expr (vda_file, vr->min, 0);
>+	  fprintf (vda_file, ",");
>+	  print_generic_expr (vda_file, vr->max, 0);
>+	  fprintf (vda_file, "])=1\n");
>+	}
>+#endif
>+      return 1;
>+    }
>+#if VDA_DEBUG
>+  if (vda_file)
>+    {
>+      fprintf (vda_file, "// %c %s(", vall, "integer_nonnegative_range");
>+      print_generic_expr (vda_file, TREE_TYPE (val), 0);
>+      fprintf (vda_file, " ");
>+      print_generic_expr (vda_file, val, 0);
>+      fprintf (vda_file, ")=0\n");
>+    }
>+#endif
>+  return 0;
>+}
> 
> /* Extract range information from a binary expression EXPR based on
>    the ranges of each of its operands and the expression code.  */
>@@ -2007,9 +2144,21 @@ 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 };
> 
>+#if VDA_DEBUG
>+  static int inited;
>+  if (!inited)
>+    {
>+      if (getenv ("VDA_DEBUG"))
>+	vda_file = fopen (getenv ("VDA_DEBUG"), "a");
>+      inited = 1;
>+    }
>+#endif
>+
>   /* Not all binary expressions can be applied to ranges in a
>      meaningful way.  Handle only arithmetic operations.  */
>   if (code != PLUS_EXPR
>@@ -2025,6 +2174,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)
>     {
>@@ -2032,6 +2182,16 @@ extract_range_from_binary_expr (value_ra
>       return;
>     }
> 
>+#if VDA_DEBUG
>+  if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
>+    if (vda_file)
>+      fprintf (vda_file, "// %s(%s)[%c%ld]\n",
>+	       "extract_range_from_binary_expr",
>+	       code == BIT_AND_EXPR ? "AND" : "OR",
>+	       TYPE_UNSIGNED (expr_type) ? 'u' : 's',
>+	       tree_to_double_int (TYPE_SIZE (expr_type)).low);
>+#endif
>+
>   /* Get value ranges for each operand.  For constant operands, create
>      a new value range with the operand to simplify processing.  */
>   if (TREE_CODE (op0) == SSA_NAME)
>@@ -2048,6 +2208,182 @@ 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, op0, 'a'))
>+	{
>+	  if (integer_nonnegative_range (&vr1, op1, 'b'))
>+	    {
>+	      /* 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);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  fprintf (vda_file, " if (a & b) < ");
>+		  print_generic_expr (vda_file, min, 0);
>+		  fprintf (vda_file, " || (a & b) > ");
>+		  print_generic_expr (vda_file, max, 0);
>+		  fprintf (vda_file, " err();\n");
>+		}
>+#endif
>+	      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);
>+#if VDA_DEBUG
>+	  if (vda_file)
>+	    {
>+	      fprintf (vda_file, " if (a & b) < ");
>+	      print_generic_expr (vda_file, min, 0);
>+	      fprintf (vda_file, " || (a & b) > ");
>+	      print_generic_expr (vda_file, max, 0);
>+	      fprintf (vda_file, " err();\n");
>+	    }
>+#endif
>+	  set_value_range (vr, VR_RANGE, min, max, NULL);
>+	  return;
>+	}
>+      if (integer_nonnegative_range (&vr1, op1, 'b'))
>+	{
>+	  /* Only op1 has nonnegative range.  */
>+	  max = vr1.max;
>+	  min = build_int_cst (expr_type, 0);
>+#if VDA_DEBUG
>+	  if (vda_file)
>+	    {
>+	      fprintf (vda_file, " if (a & b) < ");
>+	      print_generic_expr (vda_file, min, 0);
>+	      fprintf (vda_file, " || (a & b) > ");
>+	      print_generic_expr (vda_file, max, 0);
>+	      fprintf (vda_file, " err();\n");
>+	    }
>+#endif
>+	  set_value_range (vr, VR_RANGE, min, max, NULL);
>+	  return;
>+	}
>+#if VDA_DEBUG
>+      if (vda_file)
>+	fprintf (vda_file, " # AND: none is >= 0\n");
>+#endif
>+      set_value_range_to_varying (vr);
>+      return;
>+    }
>+
>+  if (code == BIT_IOR_EXPR)
>+    {
>+      if (integer_nonnegative_range (&vr0, op0, 'a'))
>+	{
>+	  if (integer_nonnegative_range (&vr1, op1, 'b'))
>+	    {
>+	      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);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  fprintf (vda_file, " if (a | b) < ");
>+		  print_generic_expr (vda_file, min, 0);
>+		  fprintf (vda_file, " || (a | b) > ");
>+		  print_generic_expr (vda_file, max, 0);
>+		  fprintf (vda_file, " err();\n");
>+		}
>+#endif
>+	      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);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  fprintf (vda_file, " if (a | b) < ");
>+		  print_generic_expr (vda_file, min, 0);
>+		  fprintf (vda_file, " || (a | b) > ");
>+		  print_generic_expr (vda_file, max, 0);
>+		  fprintf (vda_file, " err();\n");
>+		}
>+#endif
>+	      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].  */
>+#if VDA_DEBUG
>+	  if (vda_file)
>+	    fprintf (vda_file, " # OR: op0 >= 0, type is signed\n");
>+#endif
>+	  set_value_range_to_varying (vr);
>+	  return;
>+	}
>+      if (integer_nonnegative_range (&vr1, op1, 'b'))
>+	{
>+	  /* 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);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  fprintf (vda_file, " if (a | b) < ");
>+		  print_generic_expr (vda_file, min, 0);
>+		  fprintf (vda_file, " || (a | b) > ");
>+		  print_generic_expr (vda_file, max, 0);
>+		  fprintf (vda_file, " err();\n");
>+		}
>+#endif
>+	      return;
>+	    }
>+#if VDA_DEBUG
>+	  if (vda_file)
>+	    fprintf (vda_file, " # OR: op1 >= 0, type is signed\n");
>+	  set_value_range_to_varying (vr);
>+	  return;
>+#endif
>+	}
>+#if VDA_DEBUG
>+      if (vda_file)
>+	fprintf (vda_file, " # OR: none is >= 0\n");
>+#endif
>+      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 +2395,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 +2674,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