PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Ollie Wild]

[-- Attachment #1: Type: text/plain, Size: 1081 bytes --]

This patch adds support for folding BIT_AND_EXPR's with pointer
operands derived from ADDR_EXPR's.

If a BIT_AND_EXPR contains (a) a pointer operand derived from an
ADDR_EXPR and (b) an INTEGER_CST operand whose value is smaller than
the alignment of the addressed object, then it is possible to fold the
expression into a single INTEGER_CST.  This is important to the C++
front end because (on some architectures) this construct appears in
pointers to non-virtual member functions.  This patch allows
dereferencing of these objects to be simplified into simple function
calls where the referenced member function is known.

Tested with a full bootstrap and testsuite on i686-pc-linux-gnu.

Ollie


2007-09-10  Ollie Wild  <aaw@google.com>

      fold-const.c (fold_binary): Fold BIT_AND_EXPR's with a pointer operand.
      (get_pointer_modulus_and_residue): New function.
      (get_lvalue_alignment): New function.

2007-09-10  Ollie Wild  <aaw@google.com>

      gcc.dg/fold-bitand-1.c: New test.
      gcc.dg/fold-bitand-2.c: New test.
      gcc.dg/fold-bitand-3.c: New test.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fold-bitand.patch --]
[-- Type: text/x-patch; name="fold-bitand.patch", Size: 5643 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index a6fb08b..8fb6798 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9383,6 +9383,67 @@ fold_mult_zconjz (tree type, tree expr)
 }
 
 
+/* Subroutine of get_pointer_modulus_and_residue.  Computes the MODULUS and
+   RESIDUE of the storage for the supplied lvalue expression.  MODULUS is
+   a power of 2.  */
+
+static void
+get_lvalue_alignment (tree expr, unsigned int *modulus, unsigned int *residue)
+{
+  *modulus = 1;
+  *residue = 0;
+
+  if (DECL_P (expr))
+    *modulus = DECL_ALIGN_UNIT (expr);
+  else if (TREE_CODE (expr) == COMPONENT_REF)
+    {
+      tree field = TREE_OPERAND (expr, 1);
+
+      get_lvalue_alignment (TREE_OPERAND (expr, 0), modulus, residue);
+      *residue += TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field))
+		  + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
+		  / BITS_PER_UNIT;
+    }
+}
+
+
+/* Subroutine of fold_binary.  Computes the MODULUS and RESIDUE of a pointer
+   expression.  MODULUS is a power of 2.  */
+
+static void
+get_pointer_modulus_and_residue (tree expr, unsigned int *modulus,
+				 unsigned int *residue)
+{
+  *modulus = 1;
+  *residue = 0;
+
+  switch (TREE_CODE (expr))
+    {
+    case ADDR_EXPR:
+      get_lvalue_alignment (TREE_OPERAND (expr, 0), modulus, residue);
+      break;
+
+    case POINTER_PLUS_EXPR:
+      {
+	tree op1 = TREE_OPERAND (expr, 1);
+
+	if (TREE_CODE (op1) == INTEGER_CST)
+	  {
+	    tree op0 = TREE_OPERAND (expr, 0);
+
+	    STRIP_NOPS (op0);
+	    get_pointer_modulus_and_residue (op0, modulus, residue);
+	    *residue += TREE_INT_CST_LOW (op1);
+	  }
+      }
+      break;
+
+      default:
+	break;
+    }
+}
+
+
 /* Fold a binary expression of code CODE and type TYPE with operands
    OP0 and OP1.  Return the folded expression if folding is
    successful.  Otherwise, return NULL_TREE.  */
@@ -10912,6 +10973,24 @@ fold_binary (enum tree_code code, tree type, tree op0, tree op1)
 				      TREE_OPERAND (arg1, 0)));
 	}
 
+      /* If arg0 is derived from the address of an object or function, we may
+	 be able to fold this expression using the object or function's
+	 alignment.  */
+      if (POINTER_TYPE_P (TREE_TYPE (arg0)) &&
+	  TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0)
+	{
+	  unsigned int modulus, residue;
+	  unsigned HOST_WIDE_INT low = TREE_INT_CST_LOW (arg1);
+
+	  get_pointer_modulus_and_residue (arg0, &modulus, &residue);
+
+	  /* This works because modulus is a power of 2.  If this weren't the
+	     case, we'd have to replace it by its greatest power-of-2
+	     divisor: modulus & -modulus.  */
+	  if (low < modulus)
+	    return build_int_cst (type, residue & low);
+	}
+
       goto associate;
 
     case RDIV_EXPR:
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-1.c b/gcc/testsuite/gcc.dg/fold-bitand-1.c
new file mode 100644
index 0000000..cd9ed64
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-1.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c1 __attribute__ ((aligned (1)));
+char c2 __attribute__ ((aligned (2)));
+char c4 __attribute__ ((aligned (4)));
+char c8 __attribute__ ((aligned (8)));
+
+unsigned f1(void)
+{
+  return 3 & (unsigned)&c1;
+}
+
+unsigned f2(void)
+{
+  return 3 & (unsigned)&c2;
+}
+
+unsigned f3(void)
+{
+  return 3 & (unsigned)&c4;
+}
+
+unsigned f4(void)
+{
+  return 3 & (unsigned)&c8;
+}
+
+/* { dg-final { scan-tree-dump-times "\&c1 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c2 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c4 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c8 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-2.c b/gcc/testsuite/gcc.dg/fold-bitand-2.c
new file mode 100644
index 0000000..edd6ba1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-2.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+struct {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+} s __attribute__ ((aligned (4)));
+
+unsigned f1 (void)
+{
+  return 3 & (unsigned)&s.c1;
+}
+
+unsigned f2 (void)
+{
+  return 3 & (unsigned)&s.c2;
+}
+
+unsigned f3 (void)
+{
+  return 3 & (unsigned)&s.c3;
+}
+
+unsigned f4 (void)
+{
+  return 3 & (unsigned)&s.c4;
+}
+
+unsigned f5 (void)
+{
+  return 4 & (unsigned)&s.c1;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 4" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 2" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 3" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-3.c b/gcc/testsuite/gcc.dg/fold-bitand-3.c
new file mode 100644
index 0000000..e6b8e9a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-3.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c[4] __attribute__ ((aligned (4)));
+
+struct S {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+};
+
+int f1 (void)
+{
+  return 3 & (unsigned long)&c[1];
+}
+
+int f2 (void)
+{
+  return 3 & (unsigned long)&((struct S *)&c)->c2;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Richard Guenther]

On 9/11/07, Ollie Wild <aaw@google.com> wrote:
> This patch adds support for folding BIT_AND_EXPR's with pointer
> operands derived from ADDR_EXPR's.
>
> If a BIT_AND_EXPR contains (a) a pointer operand derived from an
> ADDR_EXPR and (b) an INTEGER_CST operand whose value is smaller than
> the alignment of the addressed object, then it is possible to fold the
> expression into a single INTEGER_CST.  This is important to the C++
> front end because (on some architectures) this construct appears in
> pointers to non-virtual member functions.  This patch allows
> dereferencing of these objects to be simplified into simple function
> calls where the referenced member function is known.

Can you consolidate your get_lvalue_alignment with
builtins.c:get_pointer_alignment?
It seems to have more sophisticated handling of ADDR_EXPRs.

Thanks,
Richard.

>
> Tested with a full bootstrap and testsuite on i686-pc-linux-gnu.
>
> Ollie
>
>
> 2007-09-10  Ollie Wild  <aaw@google.com>
>
>       fold-const.c (fold_binary): Fold BIT_AND_EXPR's with a pointer operand.
>       (get_pointer_modulus_and_residue): New function.
>       (get_lvalue_alignment): New function.
>
> 2007-09-10  Ollie Wild  <aaw@google.com>
>
>       gcc.dg/fold-bitand-1.c: New test.
>       gcc.dg/fold-bitand-2.c: New test.
>       gcc.dg/fold-bitand-3.c: New test.
>
>

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Ollie Wild]

[-- Attachment #1: Type: text/plain, Size: 1688 bytes --]

On 9/11/07, Richard Guenther <richard.guenther@gmail.com> wrote:
>
> Can you consolidate your get_lvalue_alignment with
> builtins.c:get_pointer_alignment?
> It seems to have more sophisticated handling of ADDR_EXPRs.

I don't think it makes sense to merge these two functions, as
get_lvalue_alignment tries to calculate the largest modulus yielding a
constant residue, whereas get_pointer_alignment seeks the smallest
modulus yielding a zero residue.  Furthermore, get_pointer_alignment
utilizes TYPE_ALIGN, which is merely suggestive on some architectures
and hence unsuitable for constant folding.

That said, the get_inner_reference function which
get_pointer_alignment uses for offset calculations is perfect.  I've
attached a new patch which adds calls to get_inner_reference for
offset calculations and handles MULT_EXPR operands of
POINTER_PLUS_EXPR.  The latter allows it to handle code like
(unsigned)&a[i] & 3, where the array index is variable.

In theory, I could also handle MULT_EXPR's returned from
get_inner_reference.  However, it isn't clear to me how to generate
such an expression, and I refuse to write code I can't test.  If
someone knows how to write a simple test program for this scenario,
please let me know.

Tested with a full bootstrap and testsuite on i686-pc-linux-gnu.

Ollie

2007-09-17  Ollie Wild  <aaw@google.com>

      fold-const.c (fold_binary): Fold BIT_AND_EXPR's with a pointer operand.
      (get_pointer_modulus_and_residue): New function.

2007-09-07  Ollie Wild  <aaw@google.com>

      gcc.dg/fold-bitand-1.c: New test.
      gcc.dg/fold-bitand-2.c: New test.
      gcc.dg/fold-bitand-3.c: New test.
      gcc.dg/fold-bitand-4.c: New test.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fold-bitand.patch --]
[-- Type: text/x-patch; name="fold-bitand.patch", Size: 7440 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index fb664fe..09f65a2 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9384,6 +9384,97 @@ fold_mult_zconjz (tree type, tree expr)
 }
 
 
+/* Subroutine of fold_binary.  Computes the MODULUS and RESIDUE of a pointer
+   expression.  MODULUS is a power of 2.  */
+
+static void
+get_pointer_modulus_and_residue (tree expr, unsigned HOST_WIDE_INT *modulus,
+				 unsigned HOST_WIDE_INT *residue)
+{
+  switch (TREE_CODE (expr))
+    {
+    case ADDR_EXPR:
+      *residue = 0;
+
+      expr = TREE_OPERAND (expr, 0);
+      if (handled_component_p (expr))
+	{
+	  HOST_WIDE_INT bitsize, bitpos;
+	  tree offset;
+	  enum machine_mode mode;
+	  int unsignedp, volatilep;
+
+	  expr = get_inner_reference (expr, &bitsize, &bitpos, &offset,
+				      &mode, &unsignedp, &volatilep, false);
+	  *residue = bitpos / BITS_PER_UNIT;
+	  if (offset)
+	    {
+	      if (TREE_CODE (offset) == INTEGER_CST)
+		*residue += TREE_INT_CST_LOW (offset);
+	      else
+		expr = NULL;
+	    }
+	}
+
+      if (expr && DECL_P (expr))
+	*modulus = DECL_ALIGN_UNIT (expr);
+      else
+	*modulus = 1;
+
+      break;
+
+    case POINTER_PLUS_EXPR:
+      {
+	tree op0, op1;
+	
+	op0 = TREE_OPERAND (expr, 0);
+	STRIP_NOPS (op0);
+	get_pointer_modulus_and_residue (op0, modulus, residue);
+
+	op1 = TREE_OPERAND (expr, 1);
+	STRIP_NOPS (op1);
+	switch (TREE_CODE (op1))
+	  {
+	  case INTEGER_CST:
+	    *residue += TREE_INT_CST_LOW (op1);
+	    break;
+
+	  case MULT_EXPR:
+	    op1 = TREE_OPERAND (op1, 1);
+	    STRIP_NOPS (op1);
+	    if (TREE_CODE (op1) == INTEGER_CST)
+	      {
+		unsigned HOST_WIDE_INT align;
+		
+		/* Compute the greatest power-of-2 divisor of op1.  */
+		align = TREE_INT_CST_LOW (op1);
+		align &= -align;
+
+		/* If align is non-zero and less than *modulus, replace
+		   *modulus with align., If align is 0, then either op1 is 0
+		   or the greatest power-of-2 divisor of op1 doesn't fit in an
+		   unsigned HOST_WIDE_INT.  In either case, no additional
+		   constraint is imposed.  */
+		if (align)
+		  *modulus = MIN (*modulus, align);
+	      }
+	    break;
+
+	  default:
+	    *modulus = 1;
+	    *residue = 0;
+	  }
+      }
+      break;
+
+    default:
+      *modulus = 1;
+      *residue = 0;
+      break;
+    }
+}
+
+
 /* Fold a binary expression of code CODE and type TYPE with operands
    OP0 and OP1.  Return the folded expression if folding is
    successful.  Otherwise, return NULL_TREE.  */
@@ -10913,6 +11004,24 @@ fold_binary (enum tree_code code, tree type, tree op0, tree op1)
 				      TREE_OPERAND (arg1, 0)));
 	}
 
+      /* If arg0 is derived from the address of an object or function, we may
+	 be able to fold this expression using the object or function's
+	 alignment.  */
+      if (POINTER_TYPE_P (TREE_TYPE (arg0)) &&
+	  TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0)
+	{
+	  unsigned HOST_WIDE_INT modulus, residue;
+	  unsigned HOST_WIDE_INT low = TREE_INT_CST_LOW (arg1);
+
+	  get_pointer_modulus_and_residue (arg0, &modulus, &residue);
+
+	  /* This works because modulus is a power of 2.  If this weren't the
+	     case, we'd have to replace it by its greatest power-of-2
+	     divisor: modulus & -modulus.  */
+	  if (low < modulus)
+	    return build_int_cst (type, residue & low);
+	}
+
       goto associate;
 
     case RDIV_EXPR:
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-1.c b/gcc/testsuite/gcc.dg/fold-bitand-1.c
new file mode 100644
index 0000000..cd9ed64
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-1.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c1 __attribute__ ((aligned (1)));
+char c2 __attribute__ ((aligned (2)));
+char c4 __attribute__ ((aligned (4)));
+char c8 __attribute__ ((aligned (8)));
+
+unsigned f1(void)
+{
+  return 3 & (unsigned)&c1;
+}
+
+unsigned f2(void)
+{
+  return 3 & (unsigned)&c2;
+}
+
+unsigned f3(void)
+{
+  return 3 & (unsigned)&c4;
+}
+
+unsigned f4(void)
+{
+  return 3 & (unsigned)&c8;
+}
+
+/* { dg-final { scan-tree-dump-times "\&c1 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c2 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c4 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c8 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-2.c b/gcc/testsuite/gcc.dg/fold-bitand-2.c
new file mode 100644
index 0000000..edd6ba1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-2.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+struct {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+} s __attribute__ ((aligned (4)));
+
+unsigned f1 (void)
+{
+  return 3 & (unsigned)&s.c1;
+}
+
+unsigned f2 (void)
+{
+  return 3 & (unsigned)&s.c2;
+}
+
+unsigned f3 (void)
+{
+  return 3 & (unsigned)&s.c3;
+}
+
+unsigned f4 (void)
+{
+  return 3 & (unsigned)&s.c4;
+}
+
+unsigned f5 (void)
+{
+  return 4 & (unsigned)&s.c1;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 4" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 2" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 3" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-3.c b/gcc/testsuite/gcc.dg/fold-bitand-3.c
new file mode 100644
index 0000000..5ba2695
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-3.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c[4] __attribute__ ((aligned (4)));
+
+struct S {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+};
+
+int f1 (void)
+{
+  return 3 & (unsigned)&c[1];
+}
+
+int f2 (void)
+{
+  return 3 & (unsigned)&((struct S *)&c)->c2;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-4.c b/gcc/testsuite/gcc.dg/fold-bitand-4.c
new file mode 100644
index 0000000..e405942
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-4.c
@@ -0,0 +1,44 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+typedef char char4[4] __attribute__ ((aligned (4)));
+char4 c4[4] __attribute__ ((aligned (16)));
+
+typedef char char16[16] __attribute__ ((aligned (16)));
+char16 c16[4] __attribute__ ((aligned (4)));
+
+int f1 (void)
+{
+  /* 12 */
+  return 15 & (unsigned)&c4[3];
+}
+
+int f2 (int i)
+{
+  /* Indeterminate */
+  return 15 & (unsigned)&c4[i];
+}
+
+int f3 (int i)
+{
+  /* 0 */
+  return 3 & (unsigned)&c4[i];
+}
+
+int f4 (int i)
+{
+  /* Indeterminate */
+  return 7 & (unsigned)&c16[i];
+}
+
+int f5 (int i)
+{
+  /* 0 */
+  return 3 & (unsigned)&c16[i];
+}
+
+/* { dg-final { scan-tree-dump-times "return 12" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 15" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 2 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 7" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Jakub Jelinek]

On Mon, Sep 17, 2007 at 11:53:43PM -0700, Ollie Wild wrote:
> 2007-09-07  Ollie Wild  <aaw@google.com>
> 
>       gcc.dg/fold-bitand-1.c: New test.
>       gcc.dg/fold-bitand-2.c: New test.
>       gcc.dg/fold-bitand-3.c: New test.
>       gcc.dg/fold-bitand-4.c: New test.

The tests shouldn't cast pointers to (unsigned), but to uintptr_t
or at least size_t, otherwise it is -Wpointer-to-int-cast material
on LP64 architectures.

	Jakub

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Ollie Wild]

[-- Attachment #1: Type: text/plain, Size: 803 bytes --]

On 9/18/07, Jakub Jelinek <jakub@redhat.com> wrote:
>
> The tests shouldn't cast pointers to (unsigned), but to uintptr_t
> or at least size_t, otherwise it is -Wpointer-to-int-cast material
> on LP64 architectures.

I've attached an updated patch.  After some consideration, I've opted
to use __SIZE_TYPE__, which is consistent with several other tests
(e.g. array-10.c) and avoids problems with missing stdint.h headers.

Ollie

2007-09-18  Ollie Wild  <aaw@google.com>

     fold-const.c (fold_binary): Fold BIT_AND_EXPR's with a pointer operand.
     (get_pointer_modulus_and_residue): New function.

2007-09-18  Ollie Wild  <aaw@google.com>

     gcc.dg/fold-bitand-1.c: New test.
     gcc.dg/fold-bitand-2.c: New test.
     gcc.dg/fold-bitand-3.c: New test.
     gcc.dg/fold-bitand-4.c: New test.

[-- Attachment #2: fold-bitand.patch --]
[-- Type: application/octet-stream, Size: 7520 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index fb664fe..09f65a2 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9384,6 +9384,97 @@ fold_mult_zconjz (tree type, tree expr)
 }
 
 
+/* Subroutine of fold_binary.  Computes the MODULUS and RESIDUE of a pointer
+   expression.  MODULUS is a power of 2.  */
+
+static void
+get_pointer_modulus_and_residue (tree expr, unsigned HOST_WIDE_INT *modulus,
+				 unsigned HOST_WIDE_INT *residue)
+{
+  switch (TREE_CODE (expr))
+    {
+    case ADDR_EXPR:
+      *residue = 0;
+
+      expr = TREE_OPERAND (expr, 0);
+      if (handled_component_p (expr))
+	{
+	  HOST_WIDE_INT bitsize, bitpos;
+	  tree offset;
+	  enum machine_mode mode;
+	  int unsignedp, volatilep;
+
+	  expr = get_inner_reference (expr, &bitsize, &bitpos, &offset,
+				      &mode, &unsignedp, &volatilep, false);
+	  *residue = bitpos / BITS_PER_UNIT;
+	  if (offset)
+	    {
+	      if (TREE_CODE (offset) == INTEGER_CST)
+		*residue += TREE_INT_CST_LOW (offset);
+	      else
+		expr = NULL;
+	    }
+	}
+
+      if (expr && DECL_P (expr))
+	*modulus = DECL_ALIGN_UNIT (expr);
+      else
+	*modulus = 1;
+
+      break;
+
+    case POINTER_PLUS_EXPR:
+      {
+	tree op0, op1;
+	
+	op0 = TREE_OPERAND (expr, 0);
+	STRIP_NOPS (op0);
+	get_pointer_modulus_and_residue (op0, modulus, residue);
+
+	op1 = TREE_OPERAND (expr, 1);
+	STRIP_NOPS (op1);
+	switch (TREE_CODE (op1))
+	  {
+	  case INTEGER_CST:
+	    *residue += TREE_INT_CST_LOW (op1);
+	    break;
+
+	  case MULT_EXPR:
+	    op1 = TREE_OPERAND (op1, 1);
+	    STRIP_NOPS (op1);
+	    if (TREE_CODE (op1) == INTEGER_CST)
+	      {
+		unsigned HOST_WIDE_INT align;
+		
+		/* Compute the greatest power-of-2 divisor of op1.  */
+		align = TREE_INT_CST_LOW (op1);
+		align &= -align;
+
+		/* If align is non-zero and less than *modulus, replace
+		   *modulus with align., If align is 0, then either op1 is 0
+		   or the greatest power-of-2 divisor of op1 doesn't fit in an
+		   unsigned HOST_WIDE_INT.  In either case, no additional
+		   constraint is imposed.  */
+		if (align)
+		  *modulus = MIN (*modulus, align);
+	      }
+	    break;
+
+	  default:
+	    *modulus = 1;
+	    *residue = 0;
+	  }
+      }
+      break;
+
+    default:
+      *modulus = 1;
+      *residue = 0;
+      break;
+    }
+}
+
+
 /* Fold a binary expression of code CODE and type TYPE with operands
    OP0 and OP1.  Return the folded expression if folding is
    successful.  Otherwise, return NULL_TREE.  */
@@ -10913,6 +11004,24 @@ fold_binary (enum tree_code code, tree type, tree op0, tree op1)
 				      TREE_OPERAND (arg1, 0)));
 	}
 
+      /* If arg0 is derived from the address of an object or function, we may
+	 be able to fold this expression using the object or function's
+	 alignment.  */
+      if (POINTER_TYPE_P (TREE_TYPE (arg0)) &&
+	  TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0)
+	{
+	  unsigned HOST_WIDE_INT modulus, residue;
+	  unsigned HOST_WIDE_INT low = TREE_INT_CST_LOW (arg1);
+
+	  get_pointer_modulus_and_residue (arg0, &modulus, &residue);
+
+	  /* This works because modulus is a power of 2.  If this weren't the
+	     case, we'd have to replace it by its greatest power-of-2
+	     divisor: modulus & -modulus.  */
+	  if (low < modulus)
+	    return build_int_cst (type, residue & low);
+	}
+
       goto associate;
 
     case RDIV_EXPR:
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-1.c b/gcc/testsuite/gcc.dg/fold-bitand-1.c
new file mode 100644
index 0000000..413ed67
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-1.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c1 __attribute__ ((aligned (1)));
+char c2 __attribute__ ((aligned (2)));
+char c4 __attribute__ ((aligned (4)));
+char c8 __attribute__ ((aligned (8)));
+
+unsigned f1(void)
+{
+  return 3 & (__SIZE_TYPE__)&c1;
+}
+
+unsigned f2(void)
+{
+  return 3 & (__SIZE_TYPE__)&c2;
+}
+
+unsigned f3(void)
+{
+  return 3 & (__SIZE_TYPE__)&c4;
+}
+
+unsigned f4(void)
+{
+  return 3 & (__SIZE_TYPE__)&c8;
+}
+
+/* { dg-final { scan-tree-dump-times "\&c1 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c2 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c4 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c8 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-2.c b/gcc/testsuite/gcc.dg/fold-bitand-2.c
new file mode 100644
index 0000000..de2e674
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-2.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+struct {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+} s __attribute__ ((aligned (4)));
+
+unsigned f1 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c1;
+}
+
+unsigned f2 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c2;
+}
+
+unsigned f3 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c3;
+}
+
+unsigned f4 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c4;
+}
+
+unsigned f5 (void)
+{
+  return 4 & (__SIZE_TYPE__)&s.c1;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 4" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 2" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 3" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-3.c b/gcc/testsuite/gcc.dg/fold-bitand-3.c
new file mode 100644
index 0000000..43d765b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-3.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c[4] __attribute__ ((aligned (4)));
+
+struct S {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+};
+
+int f1 (void)
+{
+  return 3 & (__SIZE_TYPE__)&c[1];
+}
+
+int f2 (void)
+{
+  return 3 & (__SIZE_TYPE__)&((struct S *)&c)->c2;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-4.c b/gcc/testsuite/gcc.dg/fold-bitand-4.c
new file mode 100644
index 0000000..7d82426
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-4.c
@@ -0,0 +1,44 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+typedef char char4[4] __attribute__ ((aligned (4)));
+char4 c4[4] __attribute__ ((aligned (16)));
+
+typedef char char16[16] __attribute__ ((aligned (16)));
+char16 c16[4] __attribute__ ((aligned (4)));
+
+int f1 (void)
+{
+  /* 12 */
+  return 15 & (__SIZE_TYPE__)&c4[3];
+}
+
+int f2 (int i)
+{
+  /* Indeterminate */
+  return 15 & (__SIZE_TYPE__)&c4[i];
+}
+
+int f3 (int i)
+{
+  /* 0 */
+  return 3 & (__SIZE_TYPE__)&c4[i];
+}
+
+int f4 (int i)
+{
+  /* Indeterminate */
+  return 7 & (__SIZE_TYPE__)&c16[i];
+}
+
+int f5 (int i)
+{
+  /* 0 */
+  return 3 & (__SIZE_TYPE__)&c16[i];
+}
+
+/* { dg-final { scan-tree-dump-times "return 12" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 15" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 2 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 7" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Richard Guenther]

On 9/19/07, Ollie Wild <aaw@google.com> wrote:
> On 9/18/07, Jakub Jelinek <jakub@redhat.com> wrote:
> >
> > The tests shouldn't cast pointers to (unsigned), but to uintptr_t
> > or at least size_t, otherwise it is -Wpointer-to-int-cast material
> > on LP64 architectures.
>
> I've attached an updated patch.  After some consideration, I've opted
> to use __SIZE_TYPE__, which is consistent with several other tests
> (e.g. array-10.c) and avoids problems with missing stdint.h headers.

+      /* If arg0 is derived from the address of an object or function, we may
+        be able to fold this expression using the object or function's
+        alignment.  */
+      if (POINTER_TYPE_P (TREE_TYPE (arg0)) &&
+         TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0)
+       {

coding style says the && goes to the next line.  Instead of
TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0 use
host_integer_p (arg1, 1).

The description of get_pointer_modulus_and_residue isn't exactly clear
to me.  It looks
like it should compute the biggest power-of-two N and M so that p % N == M?  But
this doesn't have a single solution - so what is it exactly computing?
 Please clarify
that in the functions description.

+         expr = get_inner_reference (expr, &bitsize, &bitpos, &offset,
+                                     &mode, &unsignedp, &volatilep, false);
+         *residue = bitpos / BITS_PER_UNIT;
+         if (offset)
+           {
+             if (TREE_CODE (offset) == INTEGER_CST)
+               *residue += TREE_INT_CST_LOW (offset);
+             else
+               expr = NULL;

an INTEGER_CST offset is always accounted for in bitpos,  no need to repeat that
here, just bail out.  As for the function I would make it return the
modulus, that would
make the flow easier.

+      if (expr && DECL_P (expr))
+       *modulus = DECL_ALIGN_UNIT (expr);
+      else

expr can't be non-NULL here.  I don't see how you protect against a
residue bigger
than modulus?  But I guess it doesn't matter, still the names are
confusing then.

I would still like you to re-investigate using get_pointer_alignment.
Basically you
would split out a helper function to get the pointer expression with
its ADDR_EXPR
stripped off and do

   base = get_inner_reference (expr, ...);
   base_align = get_pointer_alignment_1 (base, -1);

where base_align yields your modulus and from the get_inner_reference result
you compute the residue.  And yes, the result from get_pointer_alignment has
to be useful for folding as strict alignment targets rely on it for
correct code.

Thanks,
Richard.

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Ollie Wild]

On 9/19/07, Richard Guenther <richard.guenther@gmail.com> wrote:

> +      /* If arg0 is derived from the address of an object or function, we may
> +        be able to fold this expression using the object or function's
> +        alignment.  */
> +      if (POINTER_TYPE_P (TREE_TYPE (arg0)) &&
> +         TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0)
> +       {
>
> coding style says the && goes to the next line.  Instead of
> TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0 use
> host_integer_p (arg1, 1).

OK.

> The description of get_pointer_modulus_and_residue isn't exactly clear
> to me.  It looks
> like it should compute the biggest power-of-two N and M so that p % N == M?  But
> this doesn't have a single solution - so what is it exactly computing?
>  Please clarify
> that in the functions description.

It computes a power-of-two N and (arbitrary) M such that N divides (p
- M).  This tells us that p and M have log2(N) least significant
digits in common.  M is essentially arbitrary so long as these
constraints are met.  Given the information at our disposal, we choose
N as large as possible such that a constant M can be determined.

I'll update the comments.

>
> +         expr = get_inner_reference (expr, &bitsize, &bitpos, &offset,
> +                                     &mode, &unsignedp, &volatilep, false);
> +         *residue = bitpos / BITS_PER_UNIT;
> +         if (offset)
> +           {
> +             if (TREE_CODE (offset) == INTEGER_CST)
> +               *residue += TREE_INT_CST_LOW (offset);
> +             else
> +               expr = NULL;
>
> an INTEGER_CST offset is always accounted for in bitpos,  no need to repeat that
> here, just bail out.

I'm pretty sure offset *can* be an INTEGER_CST.  The end of
get_inner_reference looks something like:

    if (host_integerp (offset, 0)) {
      /* move offset into *pbitbos and return */
    }

    *pbitpos = tree_low_cst (bit_offset, 0);
    *poffset = offset;

If a constant offset is too large to store in a HOST_WIDE_INT, it is
returned in offset instead.  For our purposes, we can safely ignore
the high order bits.

Or is there some other constraint which limits the size of offsets?

> As for the function I would make it return the modulus, that would
> make the flow easier.

OK.

> +      if (expr && DECL_P (expr))
> +       *modulus = DECL_ALIGN_UNIT (expr);
> +      else
>
> expr can't be non-NULL here.

If the "if (handled_component_p (expr))" branch gets executed and the
offset returned from get_inner_reference is not an INTEGER_CST or
NULL, then expr gets set to NULL.  In all other cases, it is non-NULL.
 I guess it would be easier to understand if I just returned rather
than setting expr to NULL.

> I don't see how you protect against a residue bigger
> than modulus?  But I guess it doesn't matter, still the names are
> confusing then.

Since it doesn't affect the results of subsequent operations, I don't
try to limit the size of residue.  Technically, it's an (arbitrary)
representative of a residue class modulo *modulus.  I could put
"*residue %= *modulus" before returning if you think that would be
more comprehensible.  Alternatively, I'll just make the comments
clearer on this point.

> I would still like you to re-investigate using get_pointer_alignment.
> Basically you
> would split out a helper function to get the pointer expression with
> its ADDR_EXPR
> stripped off and do
>
>    base = get_inner_reference (expr, ...);
>    base_align = get_pointer_alignment_1 (base, -1);
>
> where base_align yields your modulus and from the get_inner_reference result
> you compute the residue.  And yes, the result from get_pointer_alignment has
> to be useful for folding as strict alignment targets rely on it for
> correct code.

Just to make sure I'm following you, are you suggesting that I should
pull the code that calculates alignments for DECL's, CONSTANT_CLASS's,
VIEW_CONVERT_EXPR's, and INDIRECT_REF's into a new function,
get_pointer_alignment_1?  Here's some example code which illustrates
my concern about using get_pointer_alignment for folding.

    struct S {
      int i;
    };

    static const char c[8] __attribute__ ((aligned (4)));
    static const struct S *ps = (struct S *)&c[1];

    unsigned f (void)
    {
      return 3 & (__SIZE_TYPE__)&(ps->i);
    }

On machines with strict alignment requirements, treating &c[1] as a
struct S * is illegal, but on x86, this compiles fine without
triggering a warning.  This generates an ADDR_EXPR whose base is an
INDIRECT_REF.  Using the logic from get_pointer_alignment, we set the
alignment to TYPE_ALIGN (TREE_TYPE (indirect_ref_expr)) which on x86
is 32 (4 bytes).  If we incorporated this logic into
get_pointer_modulus_and_residue, we'd fold the BITAND_EXPR to 0, but
the correct value is 1.

Ollie

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Richard Guenther]

On 9/20/07, Ollie Wild <aaw@google.com> wrote:
> On 9/19/07, Richard Guenther <richard.guenther@gmail.com> wrote:
>
> > +      /* If arg0 is derived from the address of an object or function, we may
> > +        be able to fold this expression using the object or function's
> > +        alignment.  */
> > +      if (POINTER_TYPE_P (TREE_TYPE (arg0)) &&
> > +         TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0)
> > +       {
> >
> > coding style says the && goes to the next line.  Instead of
> > TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0 use
> > host_integer_p (arg1, 1).
>
> OK.
>
> > The description of get_pointer_modulus_and_residue isn't exactly clear
> > to me.  It looks
> > like it should compute the biggest power-of-two N and M so that p % N == M?  But
> > this doesn't have a single solution - so what is it exactly computing?
> >  Please clarify
> > that in the functions description.
>
> It computes a power-of-two N and (arbitrary) M such that N divides (p
> - M).  This tells us that p and M have log2(N) least significant
> digits in common.  M is essentially arbitrary so long as these
> constraints are met.  Given the information at our disposal, we choose
> N as large as possible such that a constant M can be determined.
>
> I'll update the comments.

Thanks.

> >
> > +         expr = get_inner_reference (expr, &bitsize, &bitpos, &offset,
> > +                                     &mode, &unsignedp, &volatilep, false);
> > +         *residue = bitpos / BITS_PER_UNIT;
> > +         if (offset)
> > +           {
> > +             if (TREE_CODE (offset) == INTEGER_CST)
> > +               *residue += TREE_INT_CST_LOW (offset);
> > +             else
> > +               expr = NULL;
> >
> > an INTEGER_CST offset is always accounted for in bitpos,  no need to repeat that
> > here, just bail out.
>
> I'm pretty sure offset *can* be an INTEGER_CST.  The end of
> get_inner_reference looks something like:
>
>     if (host_integerp (offset, 0)) {
>       /* move offset into *pbitbos and return */
>     }
>
>     *pbitpos = tree_low_cst (bit_offset, 0);
>     *poffset = offset;
>
> If a constant offset is too large to store in a HOST_WIDE_INT, it is
> returned in offset instead.  For our purposes, we can safely ignore
> the high order bits.
>
> Or is there some other constraint which limits the size of offsets?

No, you are right.

> > As for the function I would make it return the modulus, that would
> > make the flow easier.
>
> OK.
>
> > +      if (expr && DECL_P (expr))
> > +       *modulus = DECL_ALIGN_UNIT (expr);
> > +      else
> >
> > expr can't be non-NULL here.
>
> If the "if (handled_component_p (expr))" branch gets executed and the
> offset returned from get_inner_reference is not an INTEGER_CST or
> NULL, then expr gets set to NULL.  In all other cases, it is non-NULL.
>  I guess it would be easier to understand if I just returned rather
> than setting expr to NULL.

Doh, indeed, I missed that.

> > I don't see how you protect against a residue bigger
> > than modulus?  But I guess it doesn't matter, still the names are
> > confusing then.
>
> Since it doesn't affect the results of subsequent operations, I don't
> try to limit the size of residue.  Technically, it's an (arbitrary)
> representative of a residue class modulo *modulus.  I could put
> "*residue %= *modulus" before returning if you think that would be
> more comprehensible.  Alternatively, I'll just make the comments
> clearer on this point.

Comments are enough.

> > I would still like you to re-investigate using get_pointer_alignment.
> > Basically you
> > would split out a helper function to get the pointer expression with
> > its ADDR_EXPR
> > stripped off and do
> >
> >    base = get_inner_reference (expr, ...);
> >    base_align = get_pointer_alignment_1 (base, -1);
> >
> > where base_align yields your modulus and from the get_inner_reference result
> > you compute the residue.  And yes, the result from get_pointer_alignment has
> > to be useful for folding as strict alignment targets rely on it for
> > correct code.
>
> Just to make sure I'm following you, are you suggesting that I should
> pull the code that calculates alignments for DECL's, CONSTANT_CLASS's,
> VIEW_CONVERT_EXPR's, and INDIRECT_REF's into a new function,
> get_pointer_alignment_1?  Here's some example code which illustrates
> my concern about using get_pointer_alignment for folding.
>
>     struct S {
>       int i;
>     };
>
>     static const char c[8] __attribute__ ((aligned (4)));
>     static const struct S *ps = (struct S *)&c[1];
>
>     unsigned f (void)
>     {
>       return 3 & (__SIZE_TYPE__)&(ps->i);
>     }
>
> On machines with strict alignment requirements, treating &c[1] as a
> struct S * is illegal, but on x86, this compiles fine without
> triggering a warning.  This generates an ADDR_EXPR whose base is an
> INDIRECT_REF.  Using the logic from get_pointer_alignment, we set the
> alignment to TYPE_ALIGN (TREE_TYPE (indirect_ref_expr)) which on x86
> is 32 (4 bytes).  If we incorporated this logic into
> get_pointer_modulus_and_residue, we'd fold the BITAND_EXPR to 0, but
> the correct value is 1.

Hm, right.  So much for less code duplication :/

There's one extra thing,

+    case POINTER_PLUS_EXPR:
+      {
+       tree op0, op1;
...
+         case MULT_EXPR:
+           op1 = TREE_OPERAND (op1, 1);
+           STRIP_NOPS (op1);
+           if (TREE_CODE (op1) == INTEGER_CST)
+             {

there shouldn't be NOPs if op1 is INTEGER_CST, so the STRIP_NOPS
is not necessary.  What happens if op1 is not INTEGER_CST?  Don't
we need to set modulus/residue to 1/0?  For example

int a, n, m;
if (&a + n*m & 3)
   ...

if n == m == 1 then we leave modulus/residue to that of &a which is
wrong.

Otherwise the patch should be ok after you incorporated the changes
(please re-post it).

Thanks for your patience,
Richard.

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Ollie Wild]

[-- Attachment #1: Type: text/plain, Size: 710 bytes --]

On 9/20/07, Richard Guenther <richard.guenther@gmail.com> wrote:

> Otherwise the patch should be ok after you incorporated the changes
> (please re-post it).

I've attached an updated patch.  In addition to the changes we've
discussed, I converted the switch statements to if-else chains as I
believe this makes the code more legible.

Ollie

2007-09-22  Ollie Wild  <aaw@google.com>

    fold-const.c (fold_binary): Fold BIT_AND_EXPR's with a pointer operand.
    (get_pointer_modulus_and_residue): New function.

2007-09-22  Ollie Wild  <aaw@google.com>

    gcc.dg/fold-bitand-1.c: New test.
    gcc.dg/fold-bitand-2.c: New test.
    gcc.dg/fold-bitand-3.c: New test.
    gcc.dg/fold-bitand-4.c: New test.

[-- Attachment #2: fold-bitand.txt --]
[-- Type: text/plain, Size: 8004 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index fb664fe..5f0ee21 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9384,6 +9384,97 @@ fold_mult_zconjz (tree type, tree expr)
 }
 
 
+/* Subroutine of fold_binary.  If P is the value of EXPR, computes
+   power-of-two M and (arbitrary) N such that M divides (P-N).  This condition
+   guarantees that P and N have the same least significant log2(M) bits.
+   N is not otherwise constrained.  In particular, N is not normalized to
+   0 <= N < M as is common.  In general, the precise value of P is unknown.
+   M is chosen as large as possible such that constant N can be determined.
+
+   Returns M and sets *RESIDUE to N.  */
+
+static unsigned HOST_WIDE_INT
+get_pointer_modulus_and_residue (tree expr, unsigned HOST_WIDE_INT *residue)
+{
+  enum tree_code code;
+
+  *residue = 0;
+
+  code = TREE_CODE (expr);
+  if (code == ADDR_EXPR)
+    {
+      expr = TREE_OPERAND (expr, 0);
+      if (handled_component_p (expr))
+	{
+	  HOST_WIDE_INT bitsize, bitpos;
+	  tree offset;
+	  enum machine_mode mode;
+	  int unsignedp, volatilep;
+
+	  expr = get_inner_reference (expr, &bitsize, &bitpos, &offset,
+				      &mode, &unsignedp, &volatilep, false);
+	  *residue = bitpos / BITS_PER_UNIT;
+	  if (offset)
+	    {
+	      if (TREE_CODE (offset) == INTEGER_CST)
+		*residue += TREE_INT_CST_LOW (offset);
+	      else
+		/* We don't handle more complicated offset expressions.  */
+		return 1;
+	    }
+	}
+
+      if (DECL_P (expr))
+	return DECL_ALIGN_UNIT (expr);
+    }
+  else if (code == POINTER_PLUS_EXPR)
+    {
+      tree op0, op1;
+      unsigned HOST_WIDE_INT modulus;
+      enum tree_code inner_code;
+      
+      op0 = TREE_OPERAND (expr, 0);
+      STRIP_NOPS (op0);
+      modulus = get_pointer_modulus_and_residue (op0, residue);
+
+      op1 = TREE_OPERAND (expr, 1);
+      STRIP_NOPS (op1);
+      inner_code = TREE_CODE (op1);
+      if (inner_code == INTEGER_CST)
+	{
+	  *residue += TREE_INT_CST_LOW (op1);
+	  return modulus;
+	}
+      else if (inner_code == MULT_EXPR)
+	{
+	  op1 = TREE_OPERAND (op1, 1);
+	  if (TREE_CODE (op1) == INTEGER_CST)
+	    {
+	      unsigned HOST_WIDE_INT align;
+	      
+	      /* Compute the greatest power-of-2 divisor of op1.  */
+	      align = TREE_INT_CST_LOW (op1);
+	      align &= -align;
+
+	      /* If align is non-zero and less than *modulus, replace
+		 *modulus with align., If align is 0, then either op1 is 0
+		 or the greatest power-of-2 divisor of op1 doesn't fit in an
+		 unsigned HOST_WIDE_INT.  In either case, no additional
+		 constraint is imposed.  */
+	      if (align)
+		modulus = MIN (modulus, align);
+
+	      return modulus;
+	    }
+	}
+    }
+
+    /* If we get here, we were unable to determine anything useful about the
+       expression.  */
+    return 1;
+}
+
+
 /* Fold a binary expression of code CODE and type TYPE with operands
    OP0 and OP1.  Return the folded expression if folding is
    successful.  Otherwise, return NULL_TREE.  */
@@ -10913,6 +11004,23 @@ fold_binary (enum tree_code code, tree type, tree op0, tree op1)
 				      TREE_OPERAND (arg1, 0)));
 	}
 
+      /* If arg0 is derived from the address of an object or function, we may
+	 be able to fold this expression using the object or function's
+	 alignment.  */
+      if (POINTER_TYPE_P (TREE_TYPE (arg0)) && host_integerp (arg1, 1))
+	{
+	  unsigned HOST_WIDE_INT modulus, residue;
+	  unsigned HOST_WIDE_INT low = TREE_INT_CST_LOW (arg1);
+
+	  modulus = get_pointer_modulus_and_residue (arg0, &residue);
+
+	  /* This works because modulus is a power of 2.  If this weren't the
+	     case, we'd have to replace it by its greatest power-of-2
+	     divisor: modulus & -modulus.  */
+	  if (low < modulus)
+	    return build_int_cst (type, residue & low);
+	}
+
       goto associate;
 
     case RDIV_EXPR:
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-1.c b/gcc/testsuite/gcc.dg/fold-bitand-1.c
new file mode 100644
index 0000000..413ed67
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-1.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c1 __attribute__ ((aligned (1)));
+char c2 __attribute__ ((aligned (2)));
+char c4 __attribute__ ((aligned (4)));
+char c8 __attribute__ ((aligned (8)));
+
+unsigned f1(void)
+{
+  return 3 & (__SIZE_TYPE__)&c1;
+}
+
+unsigned f2(void)
+{
+  return 3 & (__SIZE_TYPE__)&c2;
+}
+
+unsigned f3(void)
+{
+  return 3 & (__SIZE_TYPE__)&c4;
+}
+
+unsigned f4(void)
+{
+  return 3 & (__SIZE_TYPE__)&c8;
+}
+
+/* { dg-final { scan-tree-dump-times "\&c1 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c2 \& 3" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c4 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\&c8 \& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-2.c b/gcc/testsuite/gcc.dg/fold-bitand-2.c
new file mode 100644
index 0000000..de2e674
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-2.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+struct {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+} s __attribute__ ((aligned (4)));
+
+unsigned f1 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c1;
+}
+
+unsigned f2 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c2;
+}
+
+unsigned f3 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c3;
+}
+
+unsigned f4 (void)
+{
+  return 3 & (__SIZE_TYPE__)&s.c4;
+}
+
+unsigned f5 (void)
+{
+  return 4 & (__SIZE_TYPE__)&s.c1;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 4" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 2" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 3" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-3.c b/gcc/testsuite/gcc.dg/fold-bitand-3.c
new file mode 100644
index 0000000..43d765b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-3.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+char c[4] __attribute__ ((aligned (4)));
+
+struct S {
+  char c1;
+  char c2;
+  char c3;
+  char c4;
+};
+
+int f1 (void)
+{
+  return 3 & (__SIZE_TYPE__)&c[1];
+}
+
+int f2 (void)
+{
+  return 3 & (__SIZE_TYPE__)&((struct S *)&c)->c2;
+}
+
+/* { dg-final { scan-tree-dump-times "\& 3" 0 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 2 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-bitand-4.c b/gcc/testsuite/gcc.dg/fold-bitand-4.c
new file mode 100644
index 0000000..7d82426
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-bitand-4.c
@@ -0,0 +1,44 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-original" } */
+
+typedef char char4[4] __attribute__ ((aligned (4)));
+char4 c4[4] __attribute__ ((aligned (16)));
+
+typedef char char16[16] __attribute__ ((aligned (16)));
+char16 c16[4] __attribute__ ((aligned (4)));
+
+int f1 (void)
+{
+  /* 12 */
+  return 15 & (__SIZE_TYPE__)&c4[3];
+}
+
+int f2 (int i)
+{
+  /* Indeterminate */
+  return 15 & (__SIZE_TYPE__)&c4[i];
+}
+
+int f3 (int i)
+{
+  /* 0 */
+  return 3 & (__SIZE_TYPE__)&c4[i];
+}
+
+int f4 (int i)
+{
+  /* Indeterminate */
+  return 7 & (__SIZE_TYPE__)&c16[i];
+}
+
+int f5 (int i)
+{
+  /* 0 */
+  return 3 & (__SIZE_TYPE__)&c16[i];
+}
+
+/* { dg-final { scan-tree-dump-times "return 12" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 15" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 2 "original" } } */
+/* { dg-final { scan-tree-dump-times "\& 7" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Richard Guenther]

On 9/23/07, Ollie Wild <aaw@google.com> wrote:
> On 9/20/07, Richard Guenther <richard.guenther@gmail.com> wrote:
>
> > Otherwise the patch should be ok after you incorporated the changes
> > (please re-post it).
>
> I've attached an updated patch.  In addition to the changes we've
> discussed, I converted the switch statements to if-else chains as I
> believe this makes the code more legible.

This is ok for mainline if it passed bootstrap & regtest.

Thanks,
Richard.

> Ollie
>
> 2007-09-22  Ollie Wild  <aaw@google.com>
>
>     fold-const.c (fold_binary): Fold BIT_AND_EXPR's with a pointer operand.
>     (get_pointer_modulus_and_residue): New function.
>
> 2007-09-22  Ollie Wild  <aaw@google.com>
>
>     gcc.dg/fold-bitand-1.c: New test.
>     gcc.dg/fold-bitand-2.c: New test.
>     gcc.dg/fold-bitand-3.c: New test.
>     gcc.dg/fold-bitand-4.c: New test.
>
>

Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

[Ollie Wild]

On 9/23/07, Richard Guenther <richard.guenther@gmail.com> wrote:
>
> This is ok for mainline if it passed bootstrap & regtest.

It did.  Submitting now.

Thanks.

Ollie