[PATCH] add VRP for bitwise OR and AND

Daniel Berlin dannyb@google.com
Mon Aug 7 18:04:00 GMT 2006


Denis Vlasenko wrote:
> This patch adds value range propagation for (a&b), (a|b) operations.
> 
> tree-vrp.c.diff is the patch itself, test_vrp.c is a test program.
>  
> Differences in *.vrp (-fdump-tree-vrp output) and assembly generated
> with stock 4.1.1 and with patched one out of test program test_vrp.c
> are below the sig.
> 
> I am not familiar with gcc internals, so please review carefully before 
> applying. For example, I construct integer contants like this:
> 
>   tmp = build_int_cst (NULL_TREE, 1);
> 
> while Andrew Pinski does it like this:
> 
>   max = build_int_cst (TREE_TYPE (expr), 1);

Both of you are wrong for the specific case of "1", it should be
integer_one_node.  Zero should be integer_zero_node.

Other than that, if you pass NULL as the type, it will assume you mean
"integer_type_node".

When working with oring/etc where it may matter what the size of the
type of the variable is, you should use the type of the original operand.

If it doesn't matter, feel free to pass NULL.

> 
> Why? Is there a FAQ on this somewhere?
> 
> And, more broadly, I do some arithmetic on compile time constants here:
> 
>   tree xored, shift, always1;
>   int xor_hi;
>   always1 = 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);
>   shift = build_int_cst (NULL_TREE, xor_hi+1);
>   always1 = vrp_int_const_binop(RSHIFT_EXPR, always1, shift);
>   always1 = vrp_int_const_binop(LSHIFT_EXPR, always1, shift);
> 
> Well, it works, but do I really need to do it that complex?
> Can I just directly express it in C? 
In general, no, because the host and target may be different, and have
different integer sizes, etc.

For operations where this doesn't matter, you can do it as non-trees, of
course.



> That would be much
> faster/simpler:
> 
>   ...
>   xor_hi++;
>   always1 = (always1 >> xor_hi) << xor_hi;
> 
> And, btw, is it okay to reuse "tree" variables like I did
> wiht always1 in that piece of code? 
Yes

> Do I need to "free"
> them somehow?

No :)

> 
> I can attempt adding VRP for shifts after I will get
> some cluebatting on this one.
> 
> Meanwhile I'll rediff/retest it against gcc-4.1-20060804.
> 
> Andrew, please do not hesitate to point me to any
> stupid mistakes in my code. I *am* unfamiliar with gcc
> internals.
> --
> vda

You need a changelog before this patch could be reviewed, and it needs
to be against gcc's current svn sources, not 4.1.1.



> ------------------------------------------------------------------------
> 
> --- gcc-4.1.1/gcc/tree-vrp.c.orig	2006-08-06 16:07:03.000000000 +0200
> +++ gcc-4.1.1/gcc/tree-vrp.c	2006-08-06 21:44:24.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;
> @@ -1182,6 +1182,63 @@ vrp_int_const_binop (enum tree_code code
>  }
>  
>  

So, why did you make this non-inline?
> +/* Example: let's say operand has:
> +max = 01010010101001010010
> +min = 01010010100000010010
> +We can infer that these bits will be set
> +in any possible value of the operand:
> +      01010010100000000000
> +*/
> +static tree


Comments should be wrapped to 76 chars (you seem to have wrapped it much
earlier), and end with a period and two spaces. The end character should
not go on a different line.

Comments before functions should explain what the function does, in
terms of it's arguments, and what it returns.

find_bits0 and find_bits1 are not really good function names that tell
you what they do.

> +find_bits1 (tree min, tree max)
> +{
> +  tree xored, shift, always1;
> +  int xor_hi;
> +
> +  always1 = 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(xor_hi >= 0) /* if min!=max */


Comment should be above the if.

> +    {
> +      shift = build_int_cst (NULL_TREE, xor_hi+1);
> +      always1 = vrp_int_const_binop(RSHIFT_EXPR, always1, shift);
> +      always1 = vrp_int_const_binop(LSHIFT_EXPR, always1, shift);
> +    }
> +  return always1;
> +}
> +/* Example: let's say operand has:
> +max = 01010010101001010010
> +min = 01010010100000010010
> +We can infer that these bits will be unset
> +in any possible value of the operand:
> +      01010010101111111111
> +*/
> +static tree
> +find_bits0 (tree min, tree max)
> +{
> +  tree xored, always0, tmp;
> +  int xor_hi;
> +
> +  always0 = 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(xor_hi > 0) /* if min!=max and difference is not in lowest bit only */

same comment placement.

> +    {
> +      tmp = build_int_cst (NULL_TREE, xor_hi);
> +      always0 = vrp_int_const_binop(RSHIFT_EXPR, always0, tmp);
> +      /* Too ugly for words */
> +      tmp = build_int_cst (NULL_TREE, 1);
> +      do
> +        {
> +          always0 = vrp_int_const_binop(LSHIFT_EXPR, always0, tmp);
> +          always0 = vrp_int_const_binop(PLUS_EXPR, always0, tmp);
> +          xor_hi--;
> +        }
> +      while(xor_hi);
> +    }
> +  return always0;
> +}
> +
>  /* Extract range information from a binary expression EXPR based on
>     the ranges of each of its operands and the expression code.  */
>  
> @@ -1206,6 +1263,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 +1293,72 @@ extract_range_from_binary_expr (value_ra
>    else
>      set_value_range_to_varying (&vr1);
>  
> +  /* Bitwise ops */
> +  if (code == BIT_AND_EXPR)
> +    {
> +      if (vr0.type == VR_RANGE || vr1.type == VR_RANGE)
> +        {
> +          if(vr0.type == VR_RANGE)
> +            {
> +              if(vr1.type == VR_RANGE)
> +                {
> +                  tree always1_0, always1_1;
> +                  always1_0 = find_bits1(vr0.min, vr0.max);
> +                  always1_1 = find_bits1(vr1.min, vr1.max);
> +                  min = vrp_int_const_binop(BIT_AND_EXPR, always1_0, always1_1);
> +                  max = vrp_int_const_binop(MIN_EXPR, vr0.max, vr1.max);
> +                }
> +              else
> +                {
> +                  min = build_int_cst(TREE_TYPE(vr0.min), 0);
> +                  max = vr0.max;
> +                }
> +              set_value_range (vr, vr0.type, min, max, NULL);
> +            }
> +          else
> +            {
> +              min = build_int_cst(TREE_TYPE(vr1.min), 0);
> +              max = vr1.max;
> +              set_value_range (vr, vr1.type, min, max, NULL);
> +            }
> +          return;
> +        }
> +      set_value_range_to_varying (vr);
> +      return;
> +    }
> +  if (code == BIT_IOR_EXPR)
> +    {
> +      if (vr0.type == VR_RANGE || vr1.type == VR_RANGE)
> +        {
> +          if(vr0.type == VR_RANGE)
> +            {
> +              if(vr1.type == VR_RANGE)
> +                {
> +                  tree always0_0, always0_1;
> +                  always0_0 = find_bits0(vr0.min, vr0.max);
> +                  always0_1 = find_bits0(vr1.min, vr1.max);
> +                  min = vrp_int_const_binop(MAX_EXPR, vr0.min, vr1.min);
> +                  max = vrp_int_const_binop(BIT_IOR_EXPR, always0_0, always0_1);
> +                }
> +              else
> +                {
> +                  min = vr0.min;
> +                  max = TYPE_MAX_VALUE(TREE_TYPE(vr0.max));
> +                }
> +              set_value_range (vr, vr0.type, min, max, NULL);
> +            }
> +          else
> +            {
> +              min = vr1.min;
> +              max = TYPE_MAX_VALUE(TREE_TYPE(vr1.max));
> +              set_value_range (vr, vr1.type, 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)
>      {
> @@ -1244,9 +1369,8 @@ extract_range_from_binary_expr (value_ra
>    /* Refuse to operate on VARYING ranges, ranges of different kinds
>       and symbolic ranges.  TODO, we may be able to derive anti-ranges
>       in some cases.  */
> -  if (vr0.type == VR_VARYING
> -      || vr1.type == VR_VARYING
> -      || vr0.type != vr1.type
> +  if (vr0.type != vr1.type
> +      || vr0.type == VR_VARYING
>        || symbolic_range_p (&vr0)
>        || symbolic_range_p (&vr1))
>      {
> 
> 
> ------------------------------------------------------------------------
> 
> /*
> gcc -O2 -fdump-tree-vrp -S -fomit-frame-pointer -falign-functions=1 -falign-jumps=1 test_vrp.c
> */
> void v4(unsigned a, unsigned b) {
>   if (a < 0x1000) return;
>   if (a > 0x1000) return;
>   if (b < 0x0110) return;
>   if ((a|b) >= 0x01000) f(); //always
>   if ((a|b) >= 0x10000) g(); //not always
> 
> }
> void u4 (unsigned n) {
>   if (n > 0x10111) return;
>   if (n < 0x10101) return;
>   //if (n & 0x01000) h(); //never, but VRP so far is not able to figure it out
>   if (n & 0x00100) f(); //always
>   if (n & 0x00001) g(); //not always
> }



You should turn this into a tree-ssa test that scans to ensure the
result you want is produced.
Look at testsuite/gcc.dg/tree-ssa/*.c and how they work.



More information about the Gcc-patches mailing list