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 optimization]: Improve tree-ssa-ifcombine pass


Hello,

This patch adds further optimization to gimple's ifcombine pass for single-bit
andif operations.

New patterns recognized are:

* if ((a & 4) == 0) if ((a & 8) == 0) -> if ((a & 12) == 0)
* if ((a & 4) != 0) if ((a & 8) == 0) -> if ((a & 12) == 4)
* if ((a & 4) == 0) if ((a & 8) != 0) -> if ((a & 12) == 8)

To support that, patch adds required additional patterns for
if.and.if, and if.or.if
detection to tree_ssa_ifcombine_bb.

ChangeLog

2011-10-13  Kai Tietz  <ktietz@redhat.com>

	* tree-ssa-ifcombine.c (same_phi_args_p_2): New
	helper for new andif pattern edge PHI comparison.
	(recognize_single_bit_test): Add new argument and
	allow EQ_EXPR.
	(ifcombine_ifandif): Handle == 0 cases.
	(tree_ssa_ifcombine_bb): Add new ifandif pattern.

2011-10-13  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/tree-ssa/ssa-ifcombine-8.c: New test.
	* gcc.dg/tree-ssa/ssa-ifcombine-9.c: New test.
	* gcc.dg/tree-ssa/ssa-ifcombine-10.c: New test.
	* gcc.dg/tree-ssa/ssa-ifcombine-11.c: New test.
	* gcc.dg/tree-ssa/ssa-ifcombine-12.c: New test.

Bootstrapped and regression tested for all languages plus Ada and
Obj-C++ on x86_64-unknown-linux-gnu.
Ok for apply?

Regards,
Kai

Index: gcc/gcc/tree-ssa-ifcombine.c
===================================================================
--- gcc.orig/gcc/tree-ssa-ifcombine.c
+++ gcc/gcc/tree-ssa-ifcombine.c
@@ -138,6 +138,54 @@ same_phi_args_p (basic_block bb1, basic_
   return true;
 }

+/* Verify if all PHI node arguments in DEST1 for edges from BB1, BB2
+   or DEST2 to DEST1 are the same.  This makes the CFG merge point
+   free from side-effects.  Return true in this case, else false.
+   If DEST1 is not equal to DEST2, then DEST2 has to be a PHI node
+   in DEST1 and DEST2 has not to have statements or its own PHI node.  */
+
+static bool
+same_phi_args_p_2 (basic_block bb1, basic_block bb2, basic_block
dest1, basic_block dest2)
+{
+  edge e1 = find_edge (bb1, dest1);
+  edge e2 = find_edge (bb2, dest2);
+  gimple_stmt_iterator gsi1;
+  gimple_stmt_iterator gsi2;
+  gimple phi;
+
+  gsi1 = gsi_start_phis (dest1);
+  if (gsi_end_p (gsi1))
+    return (dest1 == dest2);
+
+  /* See if we can't find a PHI in DEST2 and that we find
+     a PHI edge in DEST1 for DEST2.  */
+  gsi2 = gsi_start_phis (dest2);
+  if (gsi_end_p (gsi2))
+    {
+      /* If DEST2 has no PHI, then it also has not to contain
+         any statements.  */
+      if (last_stmt (dest2) != NULL)
+        return false;
+      gsi2 = gsi1;
+      /* See if we can find DEST2 within PHI of DEST1.  */
+      e2 = find_edge (dest2, dest1);
+      if (!e2)
+        return false;
+    }
+  else if (dest1 != dest2)
+    return false;
+
+  for (; !gsi_end_p (gsi1); gsi_next (&gsi1))
+    {
+      phi = gsi_stmt (gsi1);
+      if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
+			    PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
+	return false;
+    }
+
+  return true;
+}
+
 /* Return the best representative SSA name for CANDIDATE which is used
    in a bit test.  */

@@ -165,15 +213,19 @@ get_name_for_bit_test (tree candidate)
 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
    statements.  Store the name being tested in *NAME and the bit
    in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
+   The GIMPLE_COND code is either NE_EXPR or EQ_EXPR.
+   IS_CMPEQ will be set to true, if comparison is EQ_EXPR, otherwise
+   to false.
    Returns true if the pattern matched, false otherwise.  */

 static bool
-recognize_single_bit_test (gimple cond, tree *name, tree *bit)
+recognize_single_bit_test (gimple cond, tree *name, tree *bit, bool *is_cmpeq)
 {
   gimple stmt;

   /* Get at the definition of the result of the bit test.  */
-  if (gimple_cond_code (cond) != NE_EXPR
+  if ((gimple_cond_code (cond) != NE_EXPR
+       && gimple_cond_code (cond) != EQ_EXPR)
       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
       || !integer_zerop (gimple_cond_rhs (cond)))
     return false;
@@ -181,6 +233,8 @@ recognize_single_bit_test (gimple cond,
   if (!is_gimple_assign (stmt))
     return false;

+  *is_cmpeq = (gimple_cond_code (cond) == EQ_EXPR);
+
   /* Look at which bit is tested.  One form to recognize is
      D.1985_5 = state_3(D) >> control1_4(D);
      D.1986_6 = (int) D.1985_5;
@@ -306,6 +360,7 @@ ifcombine_ifandif (basic_block inner_con
   gimple_stmt_iterator gsi;
   gimple inner_cond, outer_cond;
   tree name1, name2, bit1, bit2;
+  bool is_cmpeq1, is_cmpeq2;

   inner_cond = last_stmt (inner_cond_bb);
   if (!inner_cond
@@ -321,25 +376,40 @@ ifcombine_ifandif (basic_block inner_con
      that case remove the outer test, merging both else edges,
      and change the inner one to test for
      name & (bit1 | bit2) == (bit1 | bit2).  */
-  if (recognize_single_bit_test (inner_cond, &name1, &bit1)
-      && recognize_single_bit_test (outer_cond, &name2, &bit2)
+  if (recognize_single_bit_test (inner_cond, &name1, &bit1, &is_cmpeq1)
+      && recognize_single_bit_test (outer_cond, &name2, &bit2, &is_cmpeq2)
       && name1 == name2)
     {
-      tree t, t2;
+      tree t, t1, t2;

       /* Do it.  */
       gsi = gsi_for_stmt (inner_cond);
-      t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
+      t1 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 		       build_int_cst (TREE_TYPE (name1), 1), bit1);
       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 		        build_int_cst (TREE_TYPE (name1), 1), bit2);
-      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
+      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t1, t2);
       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 				    true, GSI_SAME_STMT);
+      if (!is_cmpeq1 && !is_cmpeq2)
+        t1 = t;
+      else if (is_cmpeq1 && is_cmpeq2)
+        t1 = build_int_cst (TREE_TYPE (name1), 0);
+      else if (!is_cmpeq1)
+       {
+	 t1 = force_gimple_operand_gsi (&gsi, t1, true, NULL_TREE,
+				        true, GSI_SAME_STMT);
+       }
+     else if (!is_cmpeq2)
+       {
+	 t1 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
+				        true, GSI_SAME_STMT);
+       }
+
       t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
       t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
 				     true, GSI_SAME_STMT);
-      t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
+      t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t1);
       t = canonicalize_cond_expr_cond (t);
       if (!t)
 	return false;
@@ -354,11 +424,24 @@ ifcombine_ifandif (basic_block inner_con
 	{
 	  fprintf (dump_file, "optimizing double bit test to ");
 	  print_generic_expr (dump_file, name1, 0);
-	  fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
+	  fprintf (dump_file, " & T == %s\n",
+		   (!is_cmpeq1 && !is_cmpeq2 ? "T"
+					     : (is_cmpeq1 == is_cmpeq2
+					        ? "0" : "Q")));
+	  fprintf (dump_file, "with temporary T = (1 << ");
 	  print_generic_expr (dump_file, bit1, 0);
 	  fprintf (dump_file, ") | (1 << ");
 	  print_generic_expr (dump_file, bit2, 0);
 	  fprintf (dump_file, ")\n");
+	  if (is_cmpeq1 != is_cmpeq2)
+	    {
+	      fprintf (dump_file, "with temporary Q = (1 << ");
+	      if (!is_cmpeq1)
+	        print_generic_expr (dump_file, bit1, 0);
+	      else
+	        print_generic_expr (dump_file, bit2, 0);
+	      fprintf (dump_file, ")\n");
+	    }
 	}

       return true;
@@ -571,24 +654,38 @@ tree_ssa_ifcombine_bb (basic_block inner
   if (single_pred_p (inner_cond_bb))
     {
       basic_block outer_cond_bb = single_pred (inner_cond_bb);
+      basic_block outer_else_bb = NULL;
+      basic_block outer_then_bb = NULL;
+
+      if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb,
+				   &outer_else_bb))
+        return false;

       /* The && form is characterized by a common else_bb with
 	 the two edges leading to it mergable.  The latter is
 	 guaranteed by matching PHI arguments in the else_bb and
 	 the inner cond_bb having no side-effects.  */
-      if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
-	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
-	  && bb_no_side_effects_p (inner_cond_bb))
+      if (inner_cond_bb == outer_then_bb
+          && ((else_bb == outer_else_bb
+               && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb))
+              || (outer_else_bb == then_bb
+                  && !same_phi_args_p_2 (outer_cond_bb,
inner_cond_bb, outer_else_bb, then_bb)
+                  && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
outer_else_bb, else_bb)))
+	  && bb_no_side_effects_p (inner_cond_bb))
 	{
 	  /* We have
 	       <outer_cond_bb>
-		 if (q) goto inner_cond_bb; else goto else_bb;
+		 if (q) goto inner_cond_bb; else goto outer_else_bb;
 	       <inner_cond_bb>
 		 if (p) goto ...; else goto else_bb;
 		 ...
 	       <else_bb>
+	       <outer_else_bb>
 		 ...
-	   */
+	     If the else_bb,is not equal to outer_else_bb, then the
+	     else_bb needs to be empty (no PHIs, no statments) and
+	     and the PHI in outer_else_bb for else_bb has to be the same value
+	     as PHI value for outer_else_bb.  */
 	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
 	}

@@ -596,18 +693,26 @@ tree_ssa_ifcombine_bb (basic_block inner
 	 two edges leading to it mergable.  The latter is guaranteed
          by matching PHI arguments in the then_bb and the inner cond_bb
 	 having no side-effects.  */
-      if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
-	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
+      if (inner_cond_bb == outer_else_bb
+          && ((then_bb == outer_then_bb
+	       && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb))
+	      || (outer_then_bb == else_bb
+                  && !same_phi_args_p_2 (outer_cond_bb,
inner_cond_bb, outer_then_bb, else_bb)
+                  && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
outer_then_bb, then_bb)))
 	  && bb_no_side_effects_p (inner_cond_bb))
 	{
 	  /* We have
 	       <outer_cond_bb>
-		 if (q) goto then_bb; else goto inner_cond_bb;
+		 if (q) goto outer_then_bb; else goto inner_cond_bb;
 	       <inner_cond_bb>
 		 if (q) goto then_bb; else goto ...;
 	       <then_bb>
+	       <outer-then_bb>
 		 ...
-	   */
+	     If the then_bb,is not equal to outer_then_bb, then the
+	     then_bb needs to be empty (no PHIs, no statments) and
+	     the PHI in outer_then_bb for then_bb has to be the same value
+	     as PHI value for outer_then_bb.  */
 	  return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
 	}
     }
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+int foo (int x, int a, int b)
+{
+  int c = 1 << a;
+  if ((x & c) == 0)
+    if ((x & (1 << b))  == 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\|" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) == 0)
+    if ((x & 8) == 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) == 0)
+    if ((x & 8) != 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "== 8" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) != 0)
+    if ((x & 8) == 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "== 4" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) != 0)
+    return 2;
+  if ((x & 8) != 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "!= 0" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */


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