Move "(A & C) == D is false when D & ~C != 0" to match.pd

Move "(A & C) == D is false when D & ~C != 0" to match.pd

[Marc Glisse]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1306 bytes --]

Hello,

as asked, I am adding some replacement in match.pd instead of just 
deleting this (redundant with CCP). It is not clear how general the 
match.pd version needs to be. (for instance it could handle some casts in 
addition to what I have written)

The expansion results in a few non-canonical patterns (thus unreachable 
code), but avoiding them would make the code longer and less readable.

I wondered about naming with_possible_nonzero_bits INTEGER_CST_or_SSA_NAME 
instead.

I would like to rename get_nonzero_bits to get_possible_nonzero_bits or 
get_possibly_nonzero_bits, something more explicit, and introduce 
get_certain(ly)_nonzero_bits that would always return 0 for SSA_NAME for a 
start (but hopefully the next person who rewrites this stuff (merge CCP 
with VRP for instance?) will implement it). It would allow for more 
symmetry in the transformations and make the intent clearer.

Bootstrap+testsuite on powerpc64le-unknown-linux-gnu.

2017-05-22  Marc Glisse  <marc.glisse@inria.fr>

 	* fold-const.c (fold_binary_loc) [(A & C) == D]: Remove transformation.
 	* match.pd (X == C): Rewrite it here.
 	(with_possible_nonzero_bits, with_possible_nonzero_bits2,
 	with_certain_nonzero_bits2): New predicates.
 	* tree-ssanames.c (get_nonzero_bits): Handle INTEGER_CST.

-- 
Marc Glisse

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: TEXT/x-diff; name=bit.patch, Size: 4938 bytes --]

Index: fold-const.c
===================================================================
--- fold-const.c	(revision 248303)
+++ fold-const.c	(working copy)
@@ -10629,38 +10629,20 @@ fold_binary_loc (location_t loc,
 		 ((X >> C1) & C2) != 0 is rewritten as (X,false), and
 		 ((X >> C1) & C2) == 0 is rewritten as (X,true).  */
 	      else
 		return omit_one_operand_loc (loc, type,
 					 code == EQ_EXPR ? integer_one_node
 							 : integer_zero_node,
 					 arg000);
 	    }
 	}
 
-      /* If we have (A & C) == D where D & ~C != 0, convert this into 0.
-	 Similarly for NE_EXPR.  */
-      if (TREE_CODE (arg0) == BIT_AND_EXPR
-	  && TREE_CODE (arg1) == INTEGER_CST
-	  && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
-	{
-	  tree notc = fold_build1_loc (loc, BIT_NOT_EXPR,
-				   TREE_TYPE (TREE_OPERAND (arg0, 1)),
-				   TREE_OPERAND (arg0, 1));
-	  tree dandnotc
-	    = fold_build2_loc (loc, BIT_AND_EXPR, TREE_TYPE (arg0),
-			       fold_convert_loc (loc, TREE_TYPE (arg0), arg1),
-			       notc);
-	  tree rslt = code == EQ_EXPR ? integer_zero_node : integer_one_node;
-	  if (integer_nonzerop (dandnotc))
-	    return omit_one_operand_loc (loc, type, rslt, arg0);
-	}
-
       /* If this is a comparison of a field, we may be able to simplify it.  */
       if ((TREE_CODE (arg0) == COMPONENT_REF
 	   || TREE_CODE (arg0) == BIT_FIELD_REF)
 	  /* Handle the constant case even without -O
 	     to make sure the warnings are given.  */
 	  && (optimize || TREE_CODE (arg1) == INTEGER_CST))
 	{
 	  t1 = optimize_bit_field_compare (loc, code, type, arg0, arg1);
 	  if (t1)
 	    return t1;
Index: match.pd
===================================================================
--- match.pd	(revision 248303)
+++ match.pd	(working copy)
@@ -1090,20 +1090,47 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	   || TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))))
    (op @1 @0))))
 
 /* X == C - X can never be true if C is odd.  */
 (for cmp (eq ne)
  (simplify
   (cmp:c (convert? @0) (convert1? (minus INTEGER_CST@1 (convert2? @0))))
   (if (TREE_INT_CST_LOW (@1) & 1)
    { constant_boolean_node (cmp == NE_EXPR, type); })))
 
+/* Arguments on which one can call get_nonzero_bits to get the bits
+   possibly set.  */
+(match with_possible_nonzero_bits
+ INTEGER_CST@0)
+(match with_possible_nonzero_bits
+ SSA_NAME@0
+ (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) || POINTER_TYPE_P (TREE_TYPE (@0)))))
+/* Slightly extended version, do not make it recursive to keep it cheap.  */
+(match (with_possible_nonzero_bits2 @0)
+ with_possible_nonzero_bits@0)
+(match (with_possible_nonzero_bits2 @0)
+ (bit_and:c with_possible_nonzero_bits@0 @2))
+
+/* Same for bits that are known to be set, but we do not have
+   an equivalent to get_nonzero_bits yet.  */
+(match (with_certain_nonzero_bits2 @0)
+ INTEGER_CST@0)
+(match (with_certain_nonzero_bits2 @0)
+ (bit_ior @1 INTEGER_CST@0))
+
+/* X == C (or X & Z == Y | C) is impossible if ~nonzero(X) & C != 0.  */
+(for cmp (eq ne)
+ (simplify
+  (cmp:c (with_possible_nonzero_bits2 @0) (with_certain_nonzero_bits2 @1))
+  (if ((~get_nonzero_bits (@0) & @1) != 0)
+   { constant_boolean_node (cmp == NE_EXPR, type); })))
+
 /* ((X inner_op C0) outer_op C1)
    With X being a tree where value_range has reasoned certain bits to always be
    zero throughout its computed value range,
    inner_op = {|,^}, outer_op = {|,^} and inner_op != outer_op
    where zero_mask has 1's for all bits that are sure to be 0 in
    and 0's otherwise.
    if (inner_op == '^') C0 &= ~C1;
    if ((C0 & ~zero_mask) == 0) then emit (X outer_op (C0 outer_op C1)
    if ((C1 & ~zero_mask) == 0) then emit (X inner_op (C0 outer_op C1)
 */
Index: tree-ssanames.c
===================================================================
--- tree-ssanames.c	(revision 248303)
+++ tree-ssanames.c	(working copy)
@@ -420,25 +420,28 @@ set_nonzero_bits (tree name, const wide_
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   if (SSA_NAME_RANGE_INFO (name) == NULL)
     set_range_info (name, VR_RANGE,
 		    TYPE_MIN_VALUE (TREE_TYPE (name)),
 		    TYPE_MAX_VALUE (TREE_TYPE (name)));
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
   ri->set_nonzero_bits (mask);
 }
 
 /* Return a widest_int with potentially non-zero bits in SSA_NAME
-   NAME, or -1 if unknown.  */
+   NAME, the constant for INTEGER_CST, or -1 if unknown.  */
 
 wide_int
 get_nonzero_bits (const_tree name)
 {
+  if (TREE_CODE (name) == INTEGER_CST)
+    return name;
+
   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
   if (POINTER_TYPE_P (TREE_TYPE (name)))
     {
       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
       if (pi && pi->align)
 	return wi::shwi (-(HOST_WIDE_INT) pi->align
 			 | (HOST_WIDE_INT) pi->misalign, precision);
       return wi::shwi (-1, precision);
     }
 

Re: Move "(A & C) == D is false when D & ~C != 0" to match.pd

[Richard Biener]

On Sat, May 20, 2017 at 8:27 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> as asked, I am adding some replacement in match.pd instead of just deleting
> this (redundant with CCP). It is not clear how general the match.pd version
> needs to be. (for instance it could handle some casts in addition to what I
> have written)
>
> The expansion results in a few non-canonical patterns (thus unreachable
> code), but avoiding them would make the code longer and less readable.
>
> I wondered about naming with_possible_nonzero_bits INTEGER_CST_or_SSA_NAME
> instead.
>
> I would like to rename get_nonzero_bits to get_possible_nonzero_bits or
> get_possibly_nonzero_bits, something more explicit, and introduce
> get_certain(ly)_nonzero_bits that would always return 0 for SSA_NAME for a
> start (but hopefully the next person who rewrites this stuff (merge CCP with
> VRP for instance?) will implement it). It would allow for more symmetry in
> the transformations and make the intent clearer.

I think get_nonzero_bits and its behavior is modeled after nonzero_bits on RTL.

> Bootstrap+testsuite on powerpc64le-unknown-linux-gnu.

Ok.

Thanks,
Richard.

> 2017-05-22  Marc Glisse  <marc.glisse@inria.fr>
>
>         * fold-const.c (fold_binary_loc) [(A & C) == D]: Remove
> transformation.
>         * match.pd (X == C): Rewrite it here.
>         (with_possible_nonzero_bits, with_possible_nonzero_bits2,
>         with_certain_nonzero_bits2): New predicates.
>         * tree-ssanames.c (get_nonzero_bits): Handle INTEGER_CST.
>
> --
> Marc Glisse

Re: Move "(A & C) == D is false when D & ~C != 0" to match.pd

[H.J. Lu]

On Sat, May 20, 2017 at 11:27 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> as asked, I am adding some replacement in match.pd instead of just deleting
> this (redundant with CCP). It is not clear how general the match.pd version
> needs to be. (for instance it could handle some casts in addition to what I
> have written)
>
> The expansion results in a few non-canonical patterns (thus unreachable
> code), but avoiding them would make the code longer and less readable.
>
> I wondered about naming with_possible_nonzero_bits INTEGER_CST_or_SSA_NAME
> instead.
>
> I would like to rename get_nonzero_bits to get_possible_nonzero_bits or
> get_possibly_nonzero_bits, something more explicit, and introduce
> get_certain(ly)_nonzero_bits that would always return 0 for SSA_NAME for a
> start (but hopefully the next person who rewrites this stuff (merge CCP with
> VRP for instance?) will implement it). It would allow for more symmetry in
> the transformations and make the intent clearer.
>
> Bootstrap+testsuite on powerpc64le-unknown-linux-gnu.
>
> 2017-05-22  Marc Glisse  <marc.glisse@inria.fr>
>
>         * fold-const.c (fold_binary_loc) [(A & C) == D]: Remove
> transformation.
>         * match.pd (X == C): Rewrite it here.
>         (with_possible_nonzero_bits, with_possible_nonzero_bits2,
>         with_certain_nonzero_bits2): New predicates.
>         * tree-ssanames.c (get_nonzero_bits): Handle INTEGER_CST.
>
> --
> Marc Glisse

This caused:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80894


-- 
H.J.