Attachment 16113 Details for Bug 28632 – Updated doubleint-based patch. DOES NOT PASS TESTSUITE.

[patch] Updated doubleint-based patch. DOES NOT PASS TESTSUITE.

bug28632_doubleint_based.patch (text/plain), 13.84 KB, created by Denis Vlasenko on 2008-08-20 14:57:31 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Denis Vlasenko

Created: 2008-08-20 14:57:31 UTC

Size: 13.84 KB

patch

obsolete

>--- gcc-4.4.svn.0/gcc/tree-vrp.c	2008-08-01 15:47:26.000000000 +0200
>+++ gcc-4.4.svn.5/gcc/tree-vrp.c	2008-08-20 14:48:28.000000000 +0200
>@@ -1995,6 +1995,154 @@ vrp_int_const_binop (enum tree_code code
>   return res;
> }
> 
>+#define VDA_DEBUG 1
>+
>+#if VDA_DEBUG
>+static FILE *vda_file;
>+#endif
>+
>+/* Combines MIN and MAX as follows:
>+   MAX =   01010010101001010010
>+   MIN =   01010010100000010010
>+   result: 01010010100000000000
>+   This tells us which bits are always 1 for any X in [MIN, MAX].  */
>+
>+static double_int
>+bits_always_set (double_int min_di, double_int max_di)
>+{
>+  double_int xored_di, result_di;
>+  int bitpos;
>+
>+  result_di.low = min_di.low & max_di.low;
>+  result_di.high = min_di.high & max_di.high;
>+
>+  /* Result may have lower common bits set, need to clear those.  */
>+  /* Find bit position of highest differing bit.  */
>+  xored_di.low = min_di.low ^ max_di.low;
>+  xored_di.high = min_di.high ^ max_di.high;
>+  /* Is there such bit?  */
>+  if (xored_di.high)
>+    {
>+      /* Clear all bits below it (the bit itself is already 0).  */
>+      bitpos = floor_log2 (xored_di.high);
>+      result_di.low = 0;
>+      result_di.high &= ~(((unsigned HOST_WIDE_INT)1 << bitpos) - 1);
>+    }
>+  else if (xored_di.low)
>+    {
>+      bitpos = floor_log2 (xored_di.low);
>+      result_di.low &= ~(((unsigned HOST_WIDE_INT)1 << bitpos) - 1);
>+    }
>+#if VDA_DEBUG
>+  if (vda_file)
>+    {
>+      fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx\n", "bits_always_set", min_di.low, max_di.low, result_di.low);
>+    }
>+#endif
>+  return result_di;
>+}
>+
>+/* Combines MIN and MAX as follows:
>+   MAX =   01010010101001010010
>+   MIN =   01010010100000010010
>+   result: 01010010101111111111.
>+   Zeros are bits which are always 0 for any X in [MIN, MAX].
>+   Conversely, ones are bits can be set.  */
>+
>+static double_int
>+bits_maybe_set (double_int min_di, double_int max_di)
>+{
>+  double_int xored_di, result_di;
>+  int bitpos;
>+
>+  result_di.low = min_di.low | max_di.low;
>+  result_di.high = min_di.high | max_di.high;
>+
>+  /* Find bit position of highest differing bit.  */
>+  xored_di.low = min_di.low ^ max_di.low;
>+  xored_di.high = min_di.high ^ max_di.high;
>+  if (xored_di.high)
>+    {
>+      bitpos = floor_log2 (xored_di.high);
>+      /* Build a 0000001111 mask, OR it to the result.  */
>+      result_di.low = ALL_ONES;
>+      result_di.high |= ((unsigned HOST_WIDE_INT)1 << bitpos) - 1;
>+#if VDA_DEBUG
>+      if (vda_file)
>+	{
>+	  fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @a [%016lx:%d]\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low, xored_di.low, bitpos);
>+	}
>+#endif
>+    }
>+  else if (xored_di.low & (ALL_ONES - 1))
>+    {
>+      bitpos = floor_log2 (xored_di.low);
>+      result_di.low |= ((unsigned HOST_WIDE_INT)1 << bitpos) - 1;
>+#if VDA_DEBUG
>+      if (vda_file)
>+	{
>+	  fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @b [%016lx:%d]\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low, xored_di.low, bitpos);
>+	}
>+#endif
>+    }
>+#if VDA_DEBUG
>+  else if (vda_file)
>+    {
>+      fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @c\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low);
>+    }
>+#endif
>+  return result_di;
>+}
>+
>+/* Are both ends of this range known, are integers, and >= 0?  */
>+
>+#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)
>+	{ /* 'if ((uNN)a >= 0 && (uNN)a <= 27030)" */
>+	  tree val_type = TREE_TYPE (val);
>+	  fprintf (vda_file, "if ((%c%ld)%c >= ",
>+		   TYPE_UNSIGNED (val_type) ? 'u' : 's',
>+		   tree_to_double_int (TYPE_SIZE (val_type)).low,
>+		   vall
>+		  );
>+	  print_generic_expr (vda_file, vr->min, 0);
>+	  fprintf (vda_file, " && (%c%ld)%c <= ",
>+		   TYPE_UNSIGNED (val_type) ? 'u' : 's',
>+		   tree_to_double_int (TYPE_SIZE (val_type)).low,
>+		   vall
>+		  );
>+	  print_generic_expr (vda_file, vr->max, 0);
>+	  fprintf (vda_file, ")\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.  */
>@@ -2010,6 +2158,17 @@ extract_range_from_binary_expr (value_ra
>   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
>+  char typebuf[16];
>+  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 +2184,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 +2192,19 @@ extract_range_from_binary_expr (value_ra
>       return;
>     }
> 
>+#if VDA_DEBUG
>+  if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
>+    if (vda_file)
>+      {
>+	sprintf (typebuf, "%c%ld",
>+		 TYPE_UNSIGNED (expr_type) ? 'u' : 's',
>+		 tree_to_double_int (TYPE_SIZE (expr_type)).low);
>+	fprintf (vda_file, "// %s(%s)[%s]\n",
>+		 "extract_range_from_binary_expr",
>+		 code == BIT_AND_EXPR ? "AND" : "OR", typebuf);
>+      }
>+#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 +2221,185 @@ 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 || code == BIT_IOR_EXPR)
>+    {
>+#if VDA_DEBUG
>+      char opc = (code == BIT_AND_EXPR ? '&' : '|');
>+#endif
>+      if (integer_nonnegative_range (&vr0, op0, 'a'))
>+	{
>+	  if (integer_nonnegative_range (&vr1, op1, 'b'))
>+	    {
>+	      double_int always_set0, always_set1;
>+	      double_int maybe_set0, maybe_set1;
>+	      double_int min_di, max_di;
>+
>+	      /* In always_setX, ones indicate "always set" bits.  */
>+	      /* In maybe_setX, ZEROES indicate "always unset" bits,
>+	         ones indicate bits which are "maybe set".  */
>+	      min_di = tree_to_double_int (vr0.min);
>+	      max_di = tree_to_double_int (vr0.max);
>+	      always_set0 = bits_always_set (min_di, max_di);
>+	      maybe_set0 = bits_maybe_set (min_di, max_di);
>+	      min_di = tree_to_double_int (vr1.min);
>+	      max_di = tree_to_double_int (vr1.max);
>+	      always_set1 = bits_always_set (min_di, max_di);
>+	      maybe_set1 = bits_maybe_set (min_di, max_di);
>+	      if (code == BIT_AND_EXPR)
>+	        {
>+	          /* If bit is always set in a AND in b,
>+	             it will be set in (a & b).  */
>+	          min_di.low = always_set0.low & always_set1.low;
>+	          min_di.high = always_set0.high & always_set1.high;
>+	      	  /* 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_di.low = maybe_set0.low & maybe_set1.low;
>+	          max_di.high = maybe_set0.high & maybe_set1.high;
>+	        }
>+	      else
>+	        {
>+	          min_di.low = always_set0.low | always_set1.low;
>+	          min_di.high = always_set0.high | always_set1.high;
>+	          max_di.low = maybe_set0.low | maybe_set1.low;
>+	          max_di.high = maybe_set0.high | maybe_set1.high;
>+	        }
>+	      min = double_int_to_tree (expr_type, min_di);
>+	      max = double_int_to_tree (expr_type, max_di);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{ /* "if ((a & b) < 0x0000000000000000 || (a & b) > 0x0000000000000001) err();" */
>+		  double_int m = tree_to_double_int (max);
>+		  if (!m.high)
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.low);
>+		  else
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.high, m.low);
>+		}
>+#endif
>+	      set_value_range (vr, VR_RANGE, min, max, NULL);
>+	      return;
>+	    }
>+	  /* Only op0 has nonnegative range.  */
>+	  if (code == BIT_AND_EXPR)
>+	    {
>+	      /* We positively sure that (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);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  double_int m = tree_to_double_int (max);
>+		  if (!m.high)
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.low);
>+		  else
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.high, m.low);
>+		}
>+#endif
>+	      return;
>+	    }
>+	  if (TYPE_UNSIGNED (expr_type))
>+	    {
>+	      /* If result is unsigned,
>+	         we still can derive that (op0 | op1) >= op0.min.  */
>+	      min = vr0.min;
>+	      max = TYPE_MAX_VALUE (expr_type);
>+	      set_value_range (vr, VR_RANGE, min, max, NULL);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  double_int m = tree_to_double_int (max);
>+		  if (!m.high)
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.low);
>+		  else
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.high, m.low);
>+		}
>+#endif
>+	      return;
>+	    }
>+#if VDA_DEBUG
>+	  if (vda_file)
>+	    fprintf (vda_file, " ((void)0); // %c: op0 >= 0, type is signed\n", opc);
>+#endif
>+	  set_value_range_to_varying (vr);
>+	  return;
>+	}
>+      if (integer_nonnegative_range (&vr1, op1, 'b'))
>+	{
>+	  /* Only op1 has nonnegative range.  */
>+	  if (code == BIT_AND_EXPR)
>+	    {
>+	      max = vr1.max;
>+	      min = build_int_cst (expr_type, 0);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  double_int m = tree_to_double_int (max);
>+		  if (!m.high)
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.low);
>+		  else
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.high, m.low);
>+	        }
>+#endif
>+	      set_value_range (vr, VR_RANGE, min, max, NULL);
>+	      return;
>+	    }
>+	  if (TYPE_UNSIGNED (expr_type))
>+	    {
>+	      min = vr1.min;
>+	      max = TYPE_MAX_VALUE (expr_type);
>+#if VDA_DEBUG
>+	      if (vda_file)
>+		{
>+		  double_int m = tree_to_double_int (max);
>+		  if (!m.high)
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.low);
>+		  else
>+		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
>+			typebuf, opc, tree_to_double_int (min).low,
>+			typebuf, opc, m.high, m.low);
>+		}
>+#endif
>+	      set_value_range (vr, VR_RANGE, min, max, NULL);
>+	      return;
>+	    }
>+#if VDA_DEBUG
>+	  if (vda_file)
>+	    fprintf (vda_file, " ((void)0); // %c: op1 >= 0, type is signed\n", opc);
>+	  set_value_range_to_varying (vr);
>+	  return;
>+#endif
>+	}
>+#if VDA_DEBUG
>+      if (vda_file)
>+	fprintf (vda_file, " ((void)0); // %c: none is >= 0\n", opc);
>+#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 +2411,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 +2690,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