[patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Kai Tietz]

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

Hello,

this patch sink type conversions in forward-propagate for the following patterns:
- ((type) X) op ((type) Y): If X and Y have compatible types.
- ((type) X) op CST: If the conversion of (type) ((type-x) CST) == CST and X has integral type.
- CST op ((type) X): If the conversion of (type) ((type-x) CST) == CST and X has integral type.

Additionally it fixes another issue shown by this type-sinking in bswap detection. The bswap pattern matching algorithm goes for the first hit, and not tries to seek for best hit.  So we search here two times. First for di case (if present) and then for si mode case.

ChangeLog

2011-06-27  Kai Tietz  <ktietz@redhat.com>

        * tree-ssa-forwprop.c (simplify_bitwise_binary): Improve
        type sinking.
        * tree-ssa-math-opts.c (execute_optimize_bswap): Separate
        search for di/si mode patterns for finding widest match.

Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?

Regards,
Kai

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

Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1624,30 +1624,56 @@ simplify_bitwise_binary (gimple_stmt_ite
   /* If the first argument is an SSA name that is itself a result of a
      typecast of an ADDR_EXPR to an integer, feed the ADDR_EXPR to the
      folder rather than the ssa name.  */
-  if (code == BIT_AND_EXPR
-      && TREE_CODE (arg2) == INTEGER_CST
+  if (TREE_CODE (arg2) == INTEGER_CST
       && TREE_CODE (arg1) == SSA_NAME)
     {
       gimple def = SSA_NAME_DEF_STMT (arg1);
       tree op = arg1;
+      tree opp = NULL_TREE;
+      tree folded_int = NULL_TREE;
 
-      /* ???  This looks bogus - the conversion could be truncating.  */
       if (is_gimple_assign (def)
 	  && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
 	  && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
 	{
-	  tree opp = gimple_assign_rhs1 (def);
-	  if (TREE_CODE (opp) == ADDR_EXPR)
+	  opp = gimple_assign_rhs1 (def);
+	  folded_int = fold_convert_loc (gimple_location (stmt),
+					 TREE_TYPE (opp), arg2);
+	  /* Check if integer value remains the same on cast back
+	     to original type.  */
+	  if (!operand_equal_p (arg2, fold_convert (TREE_TYPE (arg1),
+						    folded_int), 0))
+	    folded_int = NULL_TREE;
+	  if (TREE_CODE (opp) == ADDR_EXPR && folded_int)
 	    op = opp;
 	}
+      if (code == BIT_AND_EXPR)
+        {
+	  res = fold_binary_loc (gimple_location (stmt),
+				 BIT_AND_EXPR,
+				 TREE_TYPE (gimple_assign_lhs (stmt)),
+				 op, arg2);
+	  if (res && is_gimple_min_invariant (res))
+	    {
+	      gimple_assign_set_rhs_from_tree (gsi, res);
+	      update_stmt (stmt);
+	      return true;
+	    }
+	}
 
-      res = fold_binary_loc (gimple_location (stmt),
-			     BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
-			     op, arg2);
-      if (res && is_gimple_min_invariant (res))
-	{
-	  gimple_assign_set_rhs_from_tree (gsi, res);
-	  update_stmt (stmt);
+      /* Convert (type) X & CST -> (type) (X & (typeof-X) CST),
+         if conversion of CST is reversible.  */
+      if (opp != NULL_TREE && folded_int != NULL_TREE)
+        {
+	  gimple newop;
+	  tree tem = create_tmp_reg (TREE_TYPE (opp), NULL);
+	  newop = gimple_build_assign_with_ops (code, tem, opp, folded_int);
+	  tem = make_ssa_name (tem, newop);
+	  gimple_assign_set_lhs (newop, tem);
+	  gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+	  gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					    tem, NULL_TREE, NULL_TREE);
+	  update_stmt (gsi_stmt (*gsi));
 	  return true;
 	}
     }
@@ -1682,10 +1708,11 @@ simplify_bitwise_binary (gimple_stmt_ite
   if (CONVERT_EXPR_CODE_P (def1_code)
       && CONVERT_EXPR_CODE_P (def2_code)
       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
-      /* Make sure that the conversion widens the operands or that it
-	 changes the operation to a bitfield precision.  */
+      /* Make sure that the conversion widens the operands, or has same
+	 precision,  or that it changes the operation to a bitfield
+	 precision.  */
       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
-	   < TYPE_PRECISION (TREE_TYPE (arg1)))
+	   <= TYPE_PRECISION (TREE_TYPE (arg1)))
 	  || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
 	      != MODE_INT)
 	  || (TYPE_PRECISION (TREE_TYPE (arg1))
Index: gcc-head/gcc/tree-ssa-math-opts.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-math-opts.c
+++ gcc-head/gcc/tree-ssa-math-opts.c
@@ -1785,6 +1785,7 @@ execute_optimize_bswap (void)
   bool bswap32_p, bswap64_p;
   bool changed = false;
   tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
+  int iter = 0;
 
   if (BITS_PER_UNIT != 8)
     return 0;
@@ -1815,108 +1816,123 @@ execute_optimize_bswap (void)
       bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
     }
 
+  /* Is 64-bit bswap not supported?  */
+  if (!bswap64_p)
+    iter = 1;
+
   memset (&bswap_stats, 0, sizeof (bswap_stats));
 
-  FOR_EACH_BB (bb)
+  /* If iter has value of zero, then seek for 64-bit bswap,
+     If iter has value of one, then seek for 32-bit bswap.  */
+  for (; iter < 2; iter++)
     {
-      gimple_stmt_iterator gsi;
+      FOR_EACH_BB (bb)
+	{
+	  gimple_stmt_iterator gsi;
 
-      for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-        {
-	  gimple stmt = gsi_stmt (gsi);
-	  tree bswap_src, bswap_type;
-	  tree bswap_tmp;
-	  tree fndecl = NULL_TREE;
-	  int type_size;
-	  gimple call;
-
-	  if (!is_gimple_assign (stmt)
-	      || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
-	    continue;
+	  for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	    {
+	      gimple stmt = gsi_stmt (gsi);
+	      tree bswap_src, bswap_type;
+	      tree bswap_tmp;
+	      tree fndecl = NULL_TREE;
+	      int type_size;
+	      gimple call;
+
+	      if (!is_gimple_assign (stmt)
+		  || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
+		continue;
 
-	  type_size = TYPE_PRECISION (gimple_expr_type (stmt));
+	      type_size = TYPE_PRECISION (gimple_expr_type (stmt));
 
-	  switch (type_size)
-	    {
-	    case 32:
-	      if (bswap32_p)
+	      switch (type_size)
 		{
-		  fndecl = built_in_decls[BUILT_IN_BSWAP32];
-		  bswap_type = bswap32_type;
-		}
-	      break;
-	    case 64:
-	      if (bswap64_p)
-		{
-		  fndecl = built_in_decls[BUILT_IN_BSWAP64];
-		  bswap_type = bswap64_type;
+		case 32:
+		  if (iter != 1)
+		    continue;
+		  if (bswap32_p)
+		    {
+		      fndecl = built_in_decls[BUILT_IN_BSWAP32];
+		      bswap_type = bswap32_type;
+		    }
+		  break;
+		case 64:
+		  if (iter != 0)
+		    continue;
+		  if (bswap64_p)
+		    {
+		      fndecl = built_in_decls[BUILT_IN_BSWAP64];
+		      bswap_type = bswap64_type;
+		    }
+		  break;
+		default:
+		  continue;
 		}
-	      break;
-	    default:
-	      continue;
-	    }
 
-	  if (!fndecl)
-	    continue;
+	      if (!fndecl)
+		continue;
 
-	  bswap_src = find_bswap (stmt);
+	      bswap_src = find_bswap (stmt);
 
-	  if (!bswap_src)
-	    continue;
+	      if (!bswap_src)
+		continue;
 
-	  changed = true;
-	  if (type_size == 32)
-	    bswap_stats.found_32bit++;
-	  else
-	    bswap_stats.found_64bit++;
+	      changed = true;
+	      if (type_size == 32)
+		bswap_stats.found_32bit++;
+	      else
+		bswap_stats.found_64bit++;
 
-	  bswap_tmp = bswap_src;
+	      bswap_tmp = bswap_src;
 
-	  /* Convert the src expression if necessary.  */
-	  if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
-	    {
-	      gimple convert_stmt;
+	      /* Convert the src expression if necessary.  */
+	      if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp),
+					      bswap_type))
+		{
+		  gimple convert_stmt;
 
-	      bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
-	      add_referenced_var (bswap_tmp);
-	      bswap_tmp = make_ssa_name (bswap_tmp, NULL);
-
-	      convert_stmt = gimple_build_assign_with_ops (
-			       CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
-	      gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
-	    }
+		  bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
+		  add_referenced_var (bswap_tmp);
+		  bswap_tmp = make_ssa_name (bswap_tmp, NULL);
+
+		  convert_stmt = gimple_build_assign_with_ops (
+				   CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
+		  gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
+		}
 
-	  call = gimple_build_call (fndecl, 1, bswap_tmp);
+	      call = gimple_build_call (fndecl, 1, bswap_tmp);
 
-	  bswap_tmp = gimple_assign_lhs (stmt);
+	      bswap_tmp = gimple_assign_lhs (stmt);
 
-	  /* Convert the result if necessary.  */
-	  if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
-	    {
-	      gimple convert_stmt;
+	      /* Convert the result if necessary.  */
+	      if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp),
+					      bswap_type))
+		{
+		  gimple convert_stmt;
 
-	      bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
-	      add_referenced_var (bswap_tmp);
-	      bswap_tmp = make_ssa_name (bswap_tmp, NULL);
-	      convert_stmt = gimple_build_assign_with_ops (
-		               CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL);
-	      gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
-	    }
+		  bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
+		  add_referenced_var (bswap_tmp);
+		  bswap_tmp = make_ssa_name (bswap_tmp, NULL);
+		  convert_stmt = gimple_build_assign_with_ops (
+				   CONVERT_EXPR, gimple_assign_lhs (stmt),
+				   bswap_tmp, NULL);
+		  gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
+		}
 
-	  gimple_call_set_lhs (call, bswap_tmp);
+	      gimple_call_set_lhs (call, bswap_tmp);
 
-	  if (dump_file)
-	    {
-	      fprintf (dump_file, "%d bit bswap implementation found at: ",
-		       (int)type_size);
-	      print_gimple_stmt (dump_file, stmt, 0, 0);
-	    }
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "%d bit bswap implementation found at: ",
+			   (int) type_size);
+		  print_gimple_stmt (dump_file, stmt, 0, 0);
+		}
 
-	  gsi_insert_after (&gsi, call, GSI_SAME_STMT);
-	  gsi_remove (&gsi, true);
+	      gsi_insert_after (&gsi, call, GSI_SAME_STMT);
+	      gsi_remove (&gsi, true);
+	    }
 	}
     }
-
   statistics_counter_event (cfun, "32-bit bswap implementations found",
 			    bswap_stats.found_32bit);
   statistics_counter_event (cfun, "64-bit bswap implementations found",

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Richard Guenther]

On Mon, Jun 27, 2011 at 3:46 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Hello,
>
> this patch sink type conversions in forward-propagate for the following patterns:
> - ((type) X) op ((type) Y): If X and Y have compatible types.
> - ((type) X) op CST: If the conversion of (type) ((type-x) CST) == CST and X has integral type.
> - CST op ((type) X): If the conversion of (type) ((type-x) CST) == CST and X has integral type.

See IRC comments.

> Additionally it fixes another issue shown by this type-sinking in bswap detection. The bswap pattern matching algorithm goes for the first hit, and not tries to seek for best hit.  So we search here two times. First for di case (if present) and then for si mode case.

Please split this piece out.  I suppose either walking over stmts backwards
or simply handling __builtin_bswap in find_bswap_1 would be a better
fix than yours.

Richard.

> ChangeLog
>
> 2011-06-27  Kai Tietz  <ktietz@redhat.com>
>
>        * tree-ssa-forwprop.c (simplify_bitwise_binary): Improve
>        type sinking.
>        * tree-ssa-math-opts.c (execute_optimize_bswap): Separate
>        search for di/si mode patterns for finding widest match.
>
> Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?
>
> Regards,
> Kai
>

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Kai Tietz]

2011/6/27 Richard Guenther <richard.guenther@gmail.com>:
> On Mon, Jun 27, 2011 at 3:46 PM, Kai Tietz <ktietz@redhat.com> wrote:
>> Hello,
>>
>> this patch sink type conversions in forward-propagate for the following patterns:
>> - ((type) X) op ((type) Y): If X and Y have compatible types.
>> - ((type) X) op CST: If the conversion of (type) ((type-x) CST) == CST and X has integral type.
>> - CST op ((type) X): If the conversion of (type) ((type-x) CST) == CST and X has integral type.
>
> See IRC comments.

See IRC comments, too.  int_fits_type_p isn't suitable here, as for
bitwise operations and/or/xor casts to/from sign for same precision
don't matter. Nevertheless it is of course important to handle
sign-extension proper for operands with different precisions.
Eg: int foo (char c) { return ((int) c & 0xf0f); }.

>> Additionally it fixes another issue shown by this type-sinking in bswap detection. The bswap pattern matching algorithm goes for the first hit, and not tries to seek for best hit.  So we search here two times. First for di case (if present) and then for si mode case.
>
> Please split this piece out.  I suppose either walking over stmts backwards
> or simply handling __builtin_bswap in find_bswap_1 would be a better
> fix than yours.

Ok, I'll do.

> Richard.
>
>> ChangeLog
>>
>> 2011-06-27  Kai Tietz  <ktietz@redhat.com>
>>
>>        * tree-ssa-forwprop.c (simplify_bitwise_binary): Improve
>>        type sinking.
>>        * tree-ssa-math-opts.c (execute_optimize_bswap): Separate
>>        search for di/si mode patterns for finding widest match.
>>
>> Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?

Regards,
Kai

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Kai Tietz]

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

----- Original Message -----
From: "Richard Guenther" <richard.guenther@gmail.com>
To: "Kai Tietz" <ktietz@redhat.com>
Cc: gcc-patches@gcc.gnu.org
Sent: Monday, June 27, 2011 4:08:41 PM
Subject: Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

On Mon, Jun 27, 2011 at 3:46 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Hello,
>
> this patch sink type conversions in forward-propagate for the following patterns:
> - ((type) X) op ((type) Y): If X and Y have compatible types.
> - ((type) X) op CST: If the conversion of (type) ((type-x) CST) == CST and X has integral type.
> - CST op ((type) X): If the conversion of (type) ((type-x) CST) == CST and X has integral type.

See IRC comments.

> Additionally it fixes another issue shown by this type-sinking in bswap detection. The bswap pattern matching algorithm goes for the first hit, and not tries to seek for best hit.  So we search here two times. First for di case (if present) and then for si mode case.

Please split this piece out.  I suppose either walking over stmts backwards
or simply handling __builtin_bswap in find_bswap_1 would be a better
fix than yours.

Richard.

> ChangeLog
>
> 2011-06-27  Kai Tietz  <ktietz@redhat.com>
>
>        * tree-ssa-forwprop.c (simplify_bitwise_binary): Improve
>        type sinking.
>        * tree-ssa-math-opts.c (execute_optimize_bswap): Separate
>        search for di/si mode patterns for finding widest match.
>
> Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?


Revised patch without the bswap part.

Regards,
Kai

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

Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1624,30 +1624,56 @@ simplify_bitwise_binary (gimple_stmt_ite
   /* If the first argument is an SSA name that is itself a result of a
      typecast of an ADDR_EXPR to an integer, feed the ADDR_EXPR to the
      folder rather than the ssa name.  */
-  if (code == BIT_AND_EXPR
-      && TREE_CODE (arg2) == INTEGER_CST
+  if (TREE_CODE (arg2) == INTEGER_CST
       && TREE_CODE (arg1) == SSA_NAME)
     {
       gimple def = SSA_NAME_DEF_STMT (arg1);
       tree op = arg1;
+      tree opp = NULL_TREE;
+      tree folded_int = NULL_TREE;
 
-      /* ???  This looks bogus - the conversion could be truncating.  */
       if (is_gimple_assign (def)
 	  && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
 	  && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
 	{
-	  tree opp = gimple_assign_rhs1 (def);
-	  if (TREE_CODE (opp) == ADDR_EXPR)
+	  opp = gimple_assign_rhs1 (def);
+	  folded_int = fold_convert_loc (gimple_location (stmt),
+					 TREE_TYPE (opp), arg2);
+	  /* Check if integer value remains the same on cast back
+	     to original type.  */
+	  if (!operand_equal_p (arg2, fold_convert (TREE_TYPE (arg1),
+						    folded_int), 0))
+	    folded_int = NULL_TREE;
+	  if (TREE_CODE (opp) == ADDR_EXPR && folded_int)
 	    op = opp;
 	}
+      if (code == BIT_AND_EXPR)
+        {
+	  res = fold_binary_loc (gimple_location (stmt),
+				 BIT_AND_EXPR,
+				 TREE_TYPE (gimple_assign_lhs (stmt)),
+				 op, arg2);
+	  if (res && is_gimple_min_invariant (res))
+	    {
+	      gimple_assign_set_rhs_from_tree (gsi, res);
+	      update_stmt (stmt);
+	      return true;
+	    }
+	}
 
-      res = fold_binary_loc (gimple_location (stmt),
-			     BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
-			     op, arg2);
-      if (res && is_gimple_min_invariant (res))
-	{
-	  gimple_assign_set_rhs_from_tree (gsi, res);
-	  update_stmt (stmt);
+      /* Convert (type) X & CST -> (type) (X & (typeof-X) CST),
+         if conversion of CST is reversible.  */
+      if (opp != NULL_TREE && folded_int != NULL_TREE)
+        {
+	  gimple newop;
+	  tree tem = create_tmp_reg (TREE_TYPE (opp), NULL);
+	  newop = gimple_build_assign_with_ops (code, tem, opp, folded_int);
+	  tem = make_ssa_name (tem, newop);
+	  gimple_assign_set_lhs (newop, tem);
+	  gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+	  gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					    tem, NULL_TREE, NULL_TREE);
+	  update_stmt (gsi_stmt (*gsi));
 	  return true;
 	}
     }
@@ -1682,10 +1708,11 @@ simplify_bitwise_binary (gimple_stmt_ite
   if (CONVERT_EXPR_CODE_P (def1_code)
       && CONVERT_EXPR_CODE_P (def2_code)
       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
-      /* Make sure that the conversion widens the operands or that it
-	 changes the operation to a bitfield precision.  */
+      /* Make sure that the conversion widens the operands, or has same
+	 precision,  or that it changes the operation to a bitfield
+	 precision.  */
       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
-	   < TYPE_PRECISION (TREE_TYPE (arg1)))
+	   <= TYPE_PRECISION (TREE_TYPE (arg1)))
 	  || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
 	      != MODE_INT)
 	  || (TYPE_PRECISION (TREE_TYPE (arg1))

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Kai Tietz]

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

Hi,

so I modified patch to use int_fits_type_p() for integer CST checking.  Well, this approach is - as discussed on IRC suboptimal - as my intial approach was for and-operations with precision type > precision type-x and unsigned type-x for constant values bigger then (type-x)~0.
But well, those we miss now by int_fits_type_p() approach, too. And also we miss now the cases for that type is signed and type-x is unsigned with same precision.

Anyway ... here is the updated patch

Regards,
Kai

----- Original Message -----
From: "Richard Guenther" <richard.guenther@gmail.com>
To: "Kai Tietz" <ktietz@redhat.com>
Cc: gcc-patches@gcc.gnu.org
Sent: Monday, June 27, 2011 4:08:41 PM
Subject: Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

On Mon, Jun 27, 2011 at 3:46 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Hello,
>
> this patch sink type conversions in forward-propagate for the following patterns:
> - ((type) X) op ((type) Y): If X and Y have compatible types.
> - ((type) X) op CST: If the conversion of (type) ((type-x) CST) == CST and X has integral type.
> - CST op ((type) X): If the conversion of (type) ((type-x) CST) == CST and X has integral type.

See IRC comments.

> Additionally it fixes another issue shown by this type-sinking in bswap detection. The bswap pattern matching algorithm goes for the first hit, and not tries to seek for best hit.  So we search here two times. First for di case (if present) and then for si mode case.

Please split this piece out.  I suppose either walking over stmts backwards
or simply handling __builtin_bswap in find_bswap_1 would be a better
fix than yours.

Richard.

> ChangeLog
>
> 2011-06-27  Kai Tietz  <ktietz@redhat.com>
>
>        * tree-ssa-forwprop.c (simplify_bitwise_binary): Improve
>        type sinking.
>        * tree-ssa-math-opts.c (execute_optimize_bswap): Separate
>        search for di/si mode patterns for finding widest match.
>
> Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?
>
> Regards,
> Kai
>

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

Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1624,30 +1624,53 @@ simplify_bitwise_binary (gimple_stmt_ite
   /* If the first argument is an SSA name that is itself a result of a
      typecast of an ADDR_EXPR to an integer, feed the ADDR_EXPR to the
      folder rather than the ssa name.  */
-  if (code == BIT_AND_EXPR
-      && TREE_CODE (arg2) == INTEGER_CST
+  if (TREE_CODE (arg2) == INTEGER_CST
       && TREE_CODE (arg1) == SSA_NAME)
     {
       gimple def = SSA_NAME_DEF_STMT (arg1);
       tree op = arg1;
+      tree opp = NULL_TREE;
+      tree folded_int = NULL_TREE;
 
-      /* ???  This looks bogus - the conversion could be truncating.  */
       if (is_gimple_assign (def)
 	  && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
 	  && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
 	{
-	  tree opp = gimple_assign_rhs1 (def);
-	  if (TREE_CODE (opp) == ADDR_EXPR)
+	  opp = gimple_assign_rhs1 (def);
+	  if (int_fits_type_p (arg2, TREE_TYPE (opp)))
+	    folded_int = fold_convert_loc (gimple_location (stmt),
+					   TREE_TYPE (opp), arg2);
+	  /* ???  This looks bogus - the conversion could be truncating.  */
+	  if (TREE_CODE (opp) == ADDR_EXPR && folded_int)
 	    op = opp;
 	}
+      if (code == BIT_AND_EXPR)
+        {
+	  res = fold_binary_loc (gimple_location (stmt),
+				 BIT_AND_EXPR,
+				 TREE_TYPE (gimple_assign_lhs (stmt)),
+				 op, arg2);
+	  if (res && is_gimple_min_invariant (res))
+	    {
+	      gimple_assign_set_rhs_from_tree (gsi, res);
+	      update_stmt (stmt);
+	      return true;
+	    }
+	}
 
-      res = fold_binary_loc (gimple_location (stmt),
-			     BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
-			     op, arg2);
-      if (res && is_gimple_min_invariant (res))
-	{
-	  gimple_assign_set_rhs_from_tree (gsi, res);
-	  update_stmt (stmt);
+      /* Convert (type) X & CST -> (type) (X & (typeof-X) CST),
+         if conversion of CST is reversible.  */
+      if (opp != NULL_TREE && folded_int != NULL_TREE)
+        {
+	  gimple newop;
+	  tree tem = create_tmp_reg (TREE_TYPE (opp), NULL);
+	  newop = gimple_build_assign_with_ops (code, tem, opp, folded_int);
+	  tem = make_ssa_name (tem, newop);
+	  gimple_assign_set_lhs (newop, tem);
+	  gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+	  gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					    tem, NULL_TREE, NULL_TREE);
+	  update_stmt (gsi_stmt (*gsi));
 	  return true;
 	}
     }
@@ -1682,10 +1705,11 @@ simplify_bitwise_binary (gimple_stmt_ite
   if (CONVERT_EXPR_CODE_P (def1_code)
       && CONVERT_EXPR_CODE_P (def2_code)
       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
-      /* Make sure that the conversion widens the operands or that it
-	 changes the operation to a bitfield precision.  */
+      /* Make sure that the conversion widens the operands, or has same
+	 precision,  or that it changes the operation to a bitfield
+	 precision.  */
       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
-	   < TYPE_PRECISION (TREE_TYPE (arg1)))
+	   <= TYPE_PRECISION (TREE_TYPE (arg1)))
 	  || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
 	      != MODE_INT)
 	  || (TYPE_PRECISION (TREE_TYPE (arg1))

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Kai Tietz]

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

Ups, missed to update patch.

Kai

----- Original Message -----
From: "Kai Tietz" <ktietz@redhat.com>
To: "Richard Guenther" <richard.guenther@gmail.com>
Cc: gcc-patches@gcc.gnu.org
Sent: Monday, June 27, 2011 7:04:04 PM
Subject: Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

Hi,

so I modified patch to use int_fits_type_p() for integer CST checking.  Well, this approach is - as discussed on IRC suboptimal - as my intial approach was for and-operations with precision type > precision type-x and unsigned type-x for constant values bigger then (type-x)~0.
But well, those we miss now by int_fits_type_p() approach, too. And also we miss now the cases for that type is signed and type-x is unsigned with same precision.

Anyway ... here is the updated patch

Regards,
Kai

----- Original Message -----
From: "Richard Guenther" <richard.guenther@gmail.com>
To: "Kai Tietz" <ktietz@redhat.com>
Cc: gcc-patches@gcc.gnu.org
Sent: Monday, June 27, 2011 4:08:41 PM
Subject: Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

On Mon, Jun 27, 2011 at 3:46 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Hello,
>
> this patch sink type conversions in forward-propagate for the following patterns:
> - ((type) X) op ((type) Y): If X and Y have compatible types.
> - ((type) X) op CST: If the conversion of (type) ((type-x) CST) == CST and X has integral type.
> - CST op ((type) X): If the conversion of (type) ((type-x) CST) == CST and X has integral type.

See IRC comments.

> Additionally it fixes another issue shown by this type-sinking in bswap detection. The bswap pattern matching algorithm goes for the first hit, and not tries to seek for best hit.  So we search here two times. First for di case (if present) and then for si mode case.

Please split this piece out.  I suppose either walking over stmts backwards
or simply handling __builtin_bswap in find_bswap_1 would be a better
fix than yours.

Richard.

> ChangeLog
>
> 2011-06-27  Kai Tietz  <ktietz@redhat.com>
>
>        * tree-ssa-forwprop.c (simplify_bitwise_binary): Improve
>        type sinking.
>        * tree-ssa-math-opts.c (execute_optimize_bswap): Separate
>        search for di/si mode patterns for finding widest match.
>
> Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?
>
> Regards,
> Kai
>

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

Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1624,30 +1624,54 @@ simplify_bitwise_binary (gimple_stmt_ite
   /* If the first argument is an SSA name that is itself a result of a
      typecast of an ADDR_EXPR to an integer, feed the ADDR_EXPR to the
      folder rather than the ssa name.  */
-  if (code == BIT_AND_EXPR
-      && TREE_CODE (arg2) == INTEGER_CST
+  if (TREE_CODE (arg2) == INTEGER_CST
       && TREE_CODE (arg1) == SSA_NAME)
     {
       gimple def = SSA_NAME_DEF_STMT (arg1);
       tree op = arg1;
+      tree opp = NULL_TREE;
+      tree folded_int = NULL_TREE;
 
-      /* ???  This looks bogus - the conversion could be truncating.  */
       if (is_gimple_assign (def)
 	  && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
 	  && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
 	{
-	  tree opp = gimple_assign_rhs1 (def);
+	  opp = gimple_assign_rhs1 (def);
+	  if (INTEGRAL_TYPE_P (opp)
+	      && int_fits_type_p (arg2, TREE_TYPE (opp)))
+	    folded_int = fold_convert_loc (gimple_location (stmt),
+					   TREE_TYPE (opp), arg2);
+	  /* ???  This looks bogus - the conversion could be truncating.  */
 	  if (TREE_CODE (opp) == ADDR_EXPR)
 	    op = opp;
 	}
+      if (code == BIT_AND_EXPR)
+        {
+	  res = fold_binary_loc (gimple_location (stmt),
+				 BIT_AND_EXPR,
+				 TREE_TYPE (gimple_assign_lhs (stmt)),
+				 op, arg2);
+	  if (res && is_gimple_min_invariant (res))
+	    {
+	      gimple_assign_set_rhs_from_tree (gsi, res);
+	      update_stmt (stmt);
+	      return true;
+	    }
+	}
 
-      res = fold_binary_loc (gimple_location (stmt),
-			     BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
-			     op, arg2);
-      if (res && is_gimple_min_invariant (res))
-	{
-	  gimple_assign_set_rhs_from_tree (gsi, res);
-	  update_stmt (stmt);
+      /* Convert (type) X & CST -> (type) (X & (typeof-X) CST),
+         if conversion of CST is reversible.  */
+      if (opp != NULL_TREE && folded_int != NULL_TREE)
+        {
+	  gimple newop;
+	  tree tem = create_tmp_reg (TREE_TYPE (opp), NULL);
+	  newop = gimple_build_assign_with_ops (code, tem, opp, folded_int);
+	  tem = make_ssa_name (tem, newop);
+	  gimple_assign_set_lhs (newop, tem);
+	  gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+	  gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					    tem, NULL_TREE, NULL_TREE);
+	  update_stmt (gsi_stmt (*gsi));
 	  return true;
 	}
     }
@@ -1682,10 +1706,11 @@ simplify_bitwise_binary (gimple_stmt_ite
   if (CONVERT_EXPR_CODE_P (def1_code)
       && CONVERT_EXPR_CODE_P (def2_code)
       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
-      /* Make sure that the conversion widens the operands or that it
-	 changes the operation to a bitfield precision.  */
+      /* Make sure that the conversion widens the operands, or has same
+	 precision,  or that it changes the operation to a bitfield
+	 precision.  */
       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
-	   < TYPE_PRECISION (TREE_TYPE (arg1)))
+	   <= TYPE_PRECISION (TREE_TYPE (arg1)))
 	  || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
 	      != MODE_INT)
 	  || (TYPE_PRECISION (TREE_TYPE (arg1))

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Richard Guenther]

On Mon, Jun 27, 2011 at 7:17 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Ups, missed to update patch.

You still modify the

  /* If the first argument is an SSA name that is itself a result of a
     typecast of an ADDR_EXPR to an integer, feed the ADDR_EXPR to the
     folder rather than the ssa name.  */

block.  Please merge the constant handling with the
CONVERT_EXPR_CODE_P path instead.  The above block is purely
legacy and should probably be entirely dropped.

Richard.


> Kai
>
> ----- Original Message -----
> From: "Kai Tietz" <ktietz@redhat.com>
> To: "Richard Guenther" <richard.guenther@gmail.com>
> Cc: gcc-patches@gcc.gnu.org
> Sent: Monday, June 27, 2011 7:04:04 PM
> Subject: Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations
>
> Hi,
>
> so I modified patch to use int_fits_type_p() for integer CST checking.  Well, this approach is - as discussed on IRC suboptimal - as my intial approach was for and-operations with precision type > precision type-x and unsigned type-x for constant values bigger then (type-x)~0.
> But well, those we miss now by int_fits_type_p() approach, too. And also we miss now the cases for that type is signed and type-x is unsigned with same precision.
>
> Anyway ... here is the updated patch
>
> Regards,
> Kai
>
> ----- Original Message -----
> From: "Richard Guenther" <richard.guenther@gmail.com>
> To: "Kai Tietz" <ktietz@redhat.com>
> Cc: gcc-patches@gcc.gnu.org
> Sent: Monday, June 27, 2011 4:08:41 PM
> Subject: Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations
>
> On Mon, Jun 27, 2011 at 3:46 PM, Kai Tietz <ktietz@redhat.com> wrote:
>> Hello,
>>
>> this patch sink type conversions in forward-propagate for the following patterns:
>> - ((type) X) op ((type) Y): If X and Y have compatible types.
>> - ((type) X) op CST: If the conversion of (type) ((type-x) CST) == CST and X has integral type.
>> - CST op ((type) X): If the conversion of (type) ((type-x) CST) == CST and X has integral type.
>
> See IRC comments.
>
>> Additionally it fixes another issue shown by this type-sinking in bswap detection. The bswap pattern matching algorithm goes for the first hit, and not tries to seek for best hit.  So we search here two times. First for di case (if present) and then for si mode case.
>
> Please split this piece out.  I suppose either walking over stmts backwards
> or simply handling __builtin_bswap in find_bswap_1 would be a better
> fix than yours.
>
> Richard.
>
>> ChangeLog
>>
>> 2011-06-27  Kai Tietz  <ktietz@redhat.com>
>>
>>        * tree-ssa-forwprop.c (simplify_bitwise_binary): Improve
>>        type sinking.
>>        * tree-ssa-math-opts.c (execute_optimize_bswap): Separate
>>        search for di/si mode patterns for finding widest match.
>>
>> Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?
>>
>> Regards,
>> Kai
>>
>

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Kai Tietz]

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

Ok, moved code out of special case for addresses.

Bootstrapped for x86_64-pc-linux-gnu.  Patch ok for apply?

Regards,
Kai

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

Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1676,16 +1676,61 @@ simplify_bitwise_binary (gimple_stmt_ite
 	}
     }
 
+  /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)).  */
+  if (TREE_CODE (arg2) == INTEGER_CST
+      && CONVERT_EXPR_CODE_P (def1_code)
+      && INTEGRAL_TYPE_P (def1_arg1)
+      && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
+    {
+      gimple newop;
+      tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
+      newop =
+        gimple_build_assign_with_ops (code, tem, def1_arg1,
+				      fold_convert_loc (gimple_location (stmt),
+							TREE_TYPE (def1_arg1),
+							arg2));
+      tem = make_ssa_name (tem, newop);
+      gimple_assign_set_lhs (newop, tem);
+      gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+      gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					tem, NULL_TREE, NULL_TREE);
+      update_stmt (gsi_stmt (*gsi));
+      return true;
+    }
+
+  /* Try to fold CST op (type) X -> (type) (((type-x) CST) op X).  */
+  if (TREE_CODE (arg1) == INTEGER_CST
+      && CONVERT_EXPR_CODE_P (def2_code)
+      && INTEGRAL_TYPE_P (def2_arg1)
+      && int_fits_type_p (arg1, TREE_TYPE (def2_arg1)))
+    {
+      gimple newop;
+      tree tem = create_tmp_reg (TREE_TYPE (def2_arg1), NULL);
+      newop =
+        gimple_build_assign_with_ops (code, tem, def2_arg1,
+				      fold_convert_loc (gimple_location (stmt),
+							TREE_TYPE (def2_arg1),
+							arg1));
+      tem = make_ssa_name (tem, newop);
+      gimple_assign_set_lhs (newop, tem);
+      gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+      gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					tem, NULL_TREE, NULL_TREE);
+      update_stmt (gsi_stmt (*gsi));
+      return true;
+    }
+
   /* For bitwise binary operations apply operand conversions to the
      binary operation result instead of to the operands.  This allows
      to combine successive conversions and bitwise binary operations.  */
   if (CONVERT_EXPR_CODE_P (def1_code)
       && CONVERT_EXPR_CODE_P (def2_code)
       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
-      /* Make sure that the conversion widens the operands or that it
-	 changes the operation to a bitfield precision.  */
+      /* Make sure that the conversion widens the operands, or has same
+	 precision,  or that it changes the operation to a bitfield
+	 precision.  */
       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
-	   < TYPE_PRECISION (TREE_TYPE (arg1)))
+	   <= TYPE_PRECISION (TREE_TYPE (arg1)))
 	  || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
 	      != MODE_INT)
 	  || (TYPE_PRECISION (TREE_TYPE (arg1))

Re: [patch tree-optimization]: Try to sink type-casts for binary and/or/xor operations

[Richard Guenther]

On Tue, Jun 28, 2011 at 12:04 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Ok, moved code out of special case for addresses.
>
> Bootstrapped for x86_64-pc-linux-gnu.  Patch ok for apply?

There is no need to check for CST op (T) arg, the constant is always
the 2nd operand for commutative operations.

Ok with that variant removed.

Thanks,
Richard.

> Regards,
> Kai
>