This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] add VRP for bitwise OR and AND: v3


Third version of the patch.

Please review and consider applying.

I did the testing with 4.1.1, because gcc-4.2-20060805
does not build for me (I reported the issue separately).
The changes from 4.2-snapshot are minor, I don't think
it makes any real difference.

It looks like operands of binary | and & are already
casted to the integers or same signedness and width,
which removed some unneeded complexity from the patch.

gcc-4.1.1 bootstraps with this patch.
With the patch, it optimizes out all calls to BADn()
functions in this code:

//signed also works
typedef unsigned number;
int main(number a,number b,number c) {
    number r;
    //VRP won't realize that a and b have ranges
    //if(a<0x0100 || a>0x0101) return 1;        // 010x
    //if(b<0x1000 || b>0x1011) return 1;        // 10xx
    //this works:
    if(a<0x0100) return 1;  // 010x
    if(a>0x0101) return 1;  // 010x
    if(b<0x1000) return 1;  // 10xx
    if(b>0x1011) return 1;  // 10xx
    if (a & 0x1000) BAD0();
    r = a & b;
    if(r>0x0001) BAD1();
    r = a | b;
    if(r<0x1100) BAD2();
    r = a & c;
    if(r>0x0101) BAD4();
    return r;
}

On Wednesday 09 August 2006 20:09, Daniel Berlin wrote:
> Just some comments on the code itself for now (again, you will
> eventually need a changelog before this patch can be truly reviewed, i
> would suggest you submit it with the next iteration of this patch, just

Does this mean that patch has to include changes to gcc/ChangeLog file?
Or what? Anyway:

* tree-vrp.c: deinline vrp_int_const_binop, it is too large for that
* tree-vrp.c (extract_range_from_binary_expr): add value range propagation
  for bitwise and/or
--
vda
--- 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)
     {

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]