public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [patch gimplifier]: Do folding on truth and/or trees
@ 2011-04-27 20:32 Kai Tietz
  2011-04-27 20:33 ` Jakub Jelinek
  2011-04-27 20:55 ` Richard Guenther
  0 siblings, 2 replies; 5+ messages in thread
From: Kai Tietz @ 2011-04-27 20:32 UTC (permalink / raw)
  To: GCC Patches; +Cc: Richard Henderson

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

Hello,

this patch adds the ability to gimple-fold to operate for truth and/or
operations
on folded binary-and/or optimized truth trees - as done by fold-const.  As fold
converts trivial operations like (A && B) to (A & B) != 0, in most cases further
folding of truth and/or trees wasn't done.
folding will be again detected.

ChangeLog gcc/

2011-04-27  Kai Tietz

	* gimple-fold.c (is_bit_ior_and): New helper function.
	(fold_equal_and_or): New helper function for truth &&
	and || logic folding with treating binary optimization.
	(maybe_fold_and_comparisons): Folding for and.
	(maybe_fold_or_comparisons): Folding for or.

ChangeLog gcc/testsuite/

2011-04-27  Kai Tietz

	* gcc.dg/binop-tand1.c: New.
	* gcc.dg/binop-tand2.c: New.
	* gcc.dg/binop-tor1.c: New.
	* gcc.dg/binop-tor2.c: New.

Tested for x86_64-pc-linux-gnu and x86_64-w64-mingw32. Ok for apply?

Regards,
Kai

[-- Attachment #2: gm_andor.txt --]
[-- Type: text/plain, Size: 9036 bytes --]

Index: gcc/gcc/gimple-fold.c
===================================================================
--- gcc.orig/gcc/gimple-fold.c	2011-04-26 13:25:59.000000000 +0200
+++ gcc/gcc/gimple-fold.c	2011-04-27 20:08:50.276783700 +0200
@@ -2300,6 +2300,85 @@ and_comparisons_1 (enum tree_code code1,
   return NULL_TREE;
 }
 
+/* Checks if the binary logic can be expand for truth logic specified by the
+   IS_AND flag.  We assume that C is EQ_EXPR or NE_EXPR.  If we see a binary
+   or the variable IS_IOR is set to true, otherwise it is set to zero.  */
+
+static bool
+is_bit_ior_and (tree op, enum tree_code c, bool *is_ior, bool is_and)
+{
+  enum tree_code code;
+  gimple s;
+
+  gcc_assert (c == EQ_EXPR || c == NE_EXPR);
+
+  if (TREE_CODE (op) != SSA_NAME
+      || !is_gimple_assign ((s = SSA_NAME_DEF_STMT (op))))
+    return false;
+  code = gimple_assign_rhs_code (s);
+  if (code != BIT_IOR_EXPR && code != BIT_AND_EXPR)
+    return false;
+  if (is_and)
+    {
+      if ((code == BIT_IOR_EXPR && c == NE_EXPR)
+          || (code != BIT_IOR_EXPR && c == EQ_EXPR))
+        return false;
+    }
+  else
+    {
+      if ((code == BIT_IOR_EXPR && c != NE_EXPR)
+          || (code != BIT_IOR_EXPR && c != EQ_EXPR))
+        return false;
+    }
+  *is_ior = (code == BIT_IOR_EXPR);
+  return true;
+}
+
+/* Try to unfold truth and/or logic by watching into binary and/or optimized
+   truth logic.  */
+static tree
+fold_equal_and_or (tree l, bool l_true, int l_and, tree r, bool r_true, int is_and)
+{
+  gimple s;
+  if (operand_equal_p (l, r, 0))
+    {
+      if (l_true == r_true)
+        return l;
+      return (is_and ? boolean_false_node : boolean_true_node);
+    }
+  if (TREE_CODE (l) == SSA_NAME && is_gimple_assign ((s = SSA_NAME_DEF_STMT (l)))
+      && gimple_assign_rhs_code (s) == (l_and ? BIT_AND_EXPR : BIT_IOR_EXPR))
+    {
+      tree l1, l2, t1, t2;
+      gimple_stmt_iterator gsi;
+      l1 = gimple_assign_rhs1 (s);
+      l2 = gimple_assign_rhs1 (s);
+      t1 = fold_equal_and_or (l1, l_true, l_and, r, r_true, is_and);
+      if (t1 && ((is_and && integer_zerop (t1)) || (!is_and && integer_onep (t1))))
+        return t1;
+      if (t1 && ((is_and && integer_zerop (t1)) || (!is_and && integer_zerop (t1))))
+        return l2;
+
+      t2 = fold_equal_and_or (l2, l_true, l_and, r, r_true, is_and);
+      if (!t1 && !t2)
+        return NULL_TREE;
+      if (t2 && ((is_and && integer_zerop (t2)) || (!is_and && integer_onep (t2))))
+        return t2;
+      if (t2 && ((is_and && integer_zerop (t2)) || (!is_and && integer_zerop (t2))))
+        return l1;
+      if (t1)
+        t2 = l2;
+      else if (t2)
+        t1 = l1;
+      t1 = fold_build2 ((l_and ? BIT_AND_EXPR : BIT_IOR_EXPR), TREE_TYPE (gimple_assign_lhs (s)),
+        t1, t2);
+      gsi = gsi_for_stmt (s);
+      gimple_assign_set_rhs_from_tree (&gsi, t1);
+      return gimple_assign_lhs (s);
+    }
+  return NULL;
+}
+
 /* Try to simplify the AND of two comparisons, specified by
    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
    If this can be simplified to a single expression (without requiring
@@ -2311,11 +2390,43 @@ tree
 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
 			    enum tree_code code2, tree op2a, tree op2b)
 {
-  tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
+  tree t;
+  bool is_ior;
+
+  t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
   if (t)
     return t;
-  else
-    return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+  t = and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+  if (t)
+    return t;
+
+  if ((code1 != NE_EXPR && code1 != EQ_EXPR)
+      || (code2 != NE_EXPR && code2 != EQ_EXPR)
+      || !integer_zerop (op1b) || !integer_zerop (op2b))
+    return NULL_TREE;
+
+  if (is_bit_ior_and (op1a, code1, &is_ior, true))
+    {
+      t = fold_equal_and_or (op1a, (code1 == NE_EXPR), !is_ior, op2a, (code2 == NE_EXPR), 1);
+      if (t)
+	{
+	  if (integer_zerop (t) || integer_onep (t))
+	    return t;
+	  return fold_build2 (code1, boolean_type_node, t, op1b);
+	}
+    }
+  if (is_bit_ior_and (op2a, code2, &is_ior, true))
+    {
+      t = fold_equal_and_or (op2a, (code2 == NE_EXPR), !is_ior, op1a, (code1 == NE_EXPR), 1);
+      if (t)
+	{
+	  if (integer_zerop (t) || integer_onep (t))
+	    return t;
+	  return fold_build2 (code2, boolean_type_node, t, op2b);
+	}
+    }
+
+  return NULL;
 }
 
 /* Helper function for or_comparisons_1:  try to simplify the OR of the
@@ -2761,11 +2872,43 @@ tree
 maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
 			   enum tree_code code2, tree op2a, tree op2b)
 {
-  tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
+  tree t;
+  bool is_ior;
+
+  t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
   if (t)
     return t;
-  else
-    return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+  t = or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+  if (t)
+    return t;
+
+  if ((code1 != NE_EXPR && code1 != EQ_EXPR)
+      || (code2 != NE_EXPR && code2 != EQ_EXPR)
+      || !integer_zerop (op1b) || !integer_zerop (op2b))
+    return NULL_TREE;
+
+  if (is_bit_ior_and (op1a, code1, &is_ior, false))
+    {
+      t = fold_equal_and_or (op1a, (code1 == NE_EXPR), !is_ior, op2a, (code2 == NE_EXPR), 0);
+      if (t)
+	{
+	  if (integer_zerop (t) || integer_onep (t))
+	    return t;
+	  return fold_build2 (code1, boolean_type_node, t, op1b);
+	}
+    }
+  if (is_bit_ior_and (op2a, code2, &is_ior, false))
+    {
+      t = fold_equal_and_or (op2a, (code2 == NE_EXPR), !is_ior, op1a, (code1 == NE_EXPR), 0);
+      if (t)
+	{
+	  if (integer_zerop (t) || integer_onep (t))
+	    return t;
+	  return fold_build2 (code2, boolean_type_node, t, op2b);
+	}
+    }
+
+  return NULL;
 }
 
 
@@ -2806,7 +2949,7 @@ gimple_fold_stmt_to_constant_1 (gimple s
 	      else if (TREE_CODE (rhs) == ADDR_EXPR
 		       && !is_gimple_min_invariant (rhs))
 		{
-		  HOST_WIDE_INT offset;
+		  HOST_WIDE_INT offset = 0;
 		  tree base;
 		  base = get_addr_base_and_unit_offset_1 (TREE_OPERAND (rhs, 0),
 							  &offset,
Index: gcc/gcc/testsuite/gcc.dg/binop-tand1.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tand1.c	2011-04-27 21:31:19.276726900 +0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+  return ((!a && !b) && c && b && c && a);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+   it in the real test.  */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-tand2.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tand2.c	2011-04-27 21:30:24.705797300 +0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+  return ((a && b) && (a & b) != 0 && c);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+   it in the real test.  */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 5 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "&" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-tor1.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tor1.c	2011-04-27 21:37:35.889550600 +0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+  return ((a || b) || c || !b || c || !a);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+   it in the real test.  */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-tor2.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tor2.c	2011-04-27 21:41:04.270511700 +0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+  return ((a || b) || c || (a & b) == 0 || c);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+   it in the real test.  */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */

^ permalink raw reply	[flat|nested] 5+ messages in thread
end of thread, other threads:[~2011-04-30  2:42 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-04-27 20:32 [patch gimplifier]: Do folding on truth and/or trees Kai Tietz
2011-04-27 20:33 ` Jakub Jelinek
2011-04-30  9:21   ` Hans-Peter Nilsson
2011-04-27 20:55 ` Richard Guenther
2011-04-27 21:10   ` Richard Guenther

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).