Attachment 12067 Details for Bug 28632 – New version of the patch. 4.1.1 bootstraps with it.

[patch] New version of the patch. 4.1.1 bootstraps with it.

v3.diff (text/plain), 6.45 KB, created by Denis Vlasenko on 2006-08-11 14:17:42 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Denis Vlasenko

Created: 2006-08-11 14:17:42 UTC

Size: 6.45 KB

patch

obsolete

>--- tree-vrp.c.org	2006-05-02 21:44:46.000000000 +0200
>+++ tree-vrp.c	2006-08-11 10:18:25.000000000 +0200
>@@ -1086,7 +1086,7 @@ extract_range_from_ssa_name (value_range
>    are not using wrapping arithmetic, then adjust the result to be
>    -INF or +INF depending on CODE, VAL1 and VAL2.  */
> 
>-static inline tree
>+static tree
> vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
> {
>   tree res;
>@@ -1181,6 +1181,65 @@ vrp_int_const_binop (enum tree_code code
>   return res;
> }
> 
>+/* Combines MIN and MAX as follows:
>+   MIN =   01010010101001010010
>+   MAX =   01010010100000010010
>+   result: 01010010100000000000.  */
>+static tree
>+find_common_set_bits (tree min, tree max)
>+{
>+  tree xored, shift, result;
>+  int xor_hi;
>+
>+  result = vrp_int_const_binop (BIT_AND_EXPR, min, max);
>+  xored = vrp_int_const_binop (BIT_XOR_EXPR, min, max);
>+  xor_hi = tree_floor_log2 (xored);
>+  /* if min!=max */
>+  if (xor_hi >= 0)
>+    {
>+      shift = build_int_cst (NULL_TREE, xor_hi+1);
>+      result = vrp_int_const_binop (RSHIFT_EXPR, result, shift);
>+      result = vrp_int_const_binop (LSHIFT_EXPR, result, shift);
>+    }
>+  return result;
>+}
>+
>+/* Combines MIN and MAX as follows:
>+   MAX =   01010010101001010010
>+   MIN =   01010010100000010010
>+   result: 01010010101111111111.  */
>+
>+static tree
>+find_common_unset_bits (tree min, tree max)
>+{
>+  tree xored, shift, result, one, mask;
>+  int xor_hi;
>+
>+  result = vrp_int_const_binop (BIT_IOR_EXPR, min, max);
>+  xored = vrp_int_const_binop (BIT_XOR_EXPR, min, max);
>+  xor_hi = tree_floor_log2 (xored);
>+  /* if min!=max and difference is not in lowest bit only */
>+  if (xor_hi > 0)
>+    {
>+      shift = build_int_cst (NULL_TREE, xor_hi);
>+      one = build_int_cst (TREE_TYPE (max), 1);
>+      mask = vrp_int_const_binop (LSHIFT_EXPR, one, shift);
>+      mask = vrp_int_const_binop (MINUS_EXPR, mask, one);
>+      result = vrp_int_const_binop (BIT_IOR_EXPR, result, mask);
>+    }
>+  return result;
>+}
>+
>+static int
>+integer_nonnegative_range (value_range_t *vr, tree type)
>+{
>+  if (vr->type == VR_RANGE
>+      && TREE_CODE (vr->min) == INTEGER_CST
>+      && tree_expr_nonnegative_p (vr->min)
>+      && TREE_CODE (vr->max) == INTEGER_CST)
>+    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.  */
>@@ -1191,6 +1250,8 @@ extract_range_from_binary_expr (value_ra
>   enum tree_code code = TREE_CODE (expr);
>   tree op0, op1, min, max;
>   int cmp;
>+  tree common_set0, common_set1;
>+  tree common_unset0, common_unset1;
>   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
>   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
> 
>@@ -1206,6 +1267,8 @@ extract_range_from_binary_expr (value_ra
>       && code != ROUND_DIV_EXPR
>       && code != MIN_EXPR
>       && code != MAX_EXPR
>+      && code != BIT_AND_EXPR
>+      && code != BIT_IOR_EXPR
>       && code != TRUTH_ANDIF_EXPR
>       && code != TRUTH_ORIF_EXPR
>       && code != TRUTH_AND_EXPR
>@@ -1234,6 +1297,89 @@ 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, TREE_TYPE (op0)))
>+        {
>+          if (integer_nonnegative_range (&vr1, TREE_TYPE (op1)))
>+            {
>+              common_set0 = find_common_set_bits (vr0.max, vr0.min);
>+              common_set1 = find_common_set_bits (vr1.max, vr1.min);
>+              common_unset0 = find_common_unset_bits (vr0.max, vr0.min);
>+              common_unset1 = find_common_unset_bits (vr1.max, vr1.min);
>+              min = vrp_int_const_binop (BIT_AND_EXPR,
>+                      common_set0, common_set1);
>+              /* For example, max(010x & 10xx) = 0001 */
>+              max = vrp_int_const_binop (BIT_AND_EXPR,
>+                      common_unset0, common_unset1);
>+              set_value_range (vr, VR_RANGE, min, max, NULL);
>+              return;
>+            }
>+          else
>+            {
>+              min = build_int_cst (TREE_TYPE (op0), 0);
>+              /* We positively sure that result of (op0 & op1) can't be
>+                 larger than vr0.max.  */
>+              max = vr0.max;
>+              set_value_range (vr, VR_RANGE, min, max, NULL);
>+              return;
>+            }
>+        }
>+      if (integer_nonnegative_range (&vr1, TREE_TYPE (op1)))
>+        {
>+          min = build_int_cst (TREE_TYPE (op1), 0);
>+          max = vr1.max;
>+          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, TREE_TYPE (op0)))
>+        {
>+          if (integer_nonnegative_range (&vr1, TREE_TYPE (op1)))
>+            {
>+              common_set0 = find_common_set_bits (vr0.max, vr0.min);
>+              common_set1 = find_common_set_bits (vr1.max, vr1.min);
>+              common_unset0 = find_common_unset_bits (vr0.max, vr0.min);
>+              common_unset1 = find_common_unset_bits (vr1.max, vr1.min);
>+              /* For example, min(101x | 01xx) = 1110 */
>+              min = vrp_int_const_binop (BIT_IOR_EXPR,
>+                      common_set0, common_set1);
>+              max = vrp_int_const_binop (BIT_IOR_EXPR,
>+                      common_unset0, common_unset1);
>+              set_value_range (vr, VR_RANGE, min, max, NULL);
>+              return;
>+            }
>+          if (TYPE_UNSIGNED (TREE_TYPE (op1)))
>+            {
>+              min = vr0.min;
>+              max = TYPE_MAX_VALUE (TREE_TYPE (op1));
>+              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 [MIN,-1]..[vr0.min,+MAX].  */
>+          set_value_range_to_varying (vr);
>+          return;
>+        }
>+      if (integer_nonnegative_range (&vr1, TREE_TYPE (op1))
>+          && TYPE_UNSIGNED (TREE_TYPE (op0)))
>+        {
>+          min = vr1.min;
>+          max = TYPE_MAX_VALUE (TREE_TYPE (op0));
>+          set_value_range (vr, VR_RANGE, min, max, NULL);
>+          return;
>+        }
>+      /* TODO: signed type has antirange.  */
>+      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)
>     {

Actions: View | Diff

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