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] Optimize manual byte swap implementations using the GCC bswap builtin


Hello,

with the attached patch GCC detects manual byte swap implementations
and emits a call to the bswap builtins instead. It is implemented as a
tree-level pass in tree-ssa-math-opts.c.

The testcase includes the most prominent byte swap implementation for
32 and 64 bit copied from the Linux kernel.

I've bootstrapped the patch on x86_64, s390 and s390x.
The included testcase succeeds on these 3 targets.

Ok for mainline when entering stage 1?

Bye,

-Andreas-


2008-11-28  Andreas Krebbel  <Andreas.Krebbel@de.ibm.com>

	* passes.c (init_optimization_passes): Add the bswap pass.
	* tree-pass.h: Likewise.
	* tree-ssa-math-opts.c (find_bswap_1, find_bswap,
	execute_optimize_bswap, gate_optimize_bswap): New functions.
	(pass_optimize_bswap): New pass structure.

2008-11-28  Andreas Krebbel  <Andreas.Krebbel@de.ibm.com>

	* gcc.dg/optimize-bswap-1.c: New testcase.


Index: gcc/passes.c
===================================================================
*** gcc/passes.c.orig	2008-11-27 17:49:12.000000000 +0100
--- gcc/passes.c	2008-11-27 17:49:20.000000000 +0100
*************** init_optimization_passes (void)
*** 673,678 ****
--- 673,679 ----
  	}
        NEXT_PASS (pass_cse_reciprocals);
        NEXT_PASS (pass_convert_to_rsqrt);
+       NEXT_PASS (pass_optimize_bswap);
        NEXT_PASS (pass_reassoc);
        NEXT_PASS (pass_vrp);
        NEXT_PASS (pass_dominator);
Index: gcc/tree-pass.h
===================================================================
*** gcc/tree-pass.h.orig	2008-11-27 17:49:12.000000000 +0100
--- gcc/tree-pass.h	2008-11-27 17:49:20.000000000 +0100
*************** extern struct gimple_opt_pass pass_late_
*** 363,368 ****
--- 363,369 ----
  extern struct gimple_opt_pass pass_cse_reciprocals;
  extern struct gimple_opt_pass pass_cse_sincos;
  extern struct gimple_opt_pass pass_convert_to_rsqrt;
+ extern struct gimple_opt_pass pass_optimize_bswap;
  extern struct gimple_opt_pass pass_warn_function_return;
  extern struct gimple_opt_pass pass_warn_function_noreturn;
  extern struct gimple_opt_pass pass_cselim;
Index: gcc/tree-ssa-math-opts.c
===================================================================
*** gcc/tree-ssa-math-opts.c.orig	2008-11-27 17:49:12.000000000 +0100
--- gcc/tree-ssa-math-opts.c	2008-11-28 12:33:10.000000000 +0100
*************** along with GCC; see the file COPYING3.  
*** 97,102 ****
--- 97,103 ----
  #include "alloc-pool.h"
  #include "basic-block.h"
  #include "target.h"
+ #include "diagnostic.h"
  
  
  /* This structure represents one basic block that either computes a
*************** struct gimple_opt_pass pass_convert_to_r
*** 879,881 ****
--- 880,1094 ----
      | TODO_verify_stmts                 /* todo_flags_finish */
   }
  };
+ 
+ /* Check if STMT completes a bswap implementation consisting of ORs,
+    SHIFTs and ANDs.  Return the source tree expression on which the
+    byte swap is performed and NULL if no bswap was found.  The
+    ROOT_NODE_P argument should always by true when calling this
+    function.  It will be set to false for recursively checking the
+    previous statements.  */
+ 
+ static tree
+ find_bswap_1 (gimple stmt, bool root_node_p)
+ {
+   static int bytes_moved_inplace;
+   static tree source_expr;
+   static HOST_WIDE_INT type_size;
+   tree source;
+   gimple op;
+   HOST_WIDE_INT shift_count;
+   int bytenum;
+   enum tree_code code;
+ 
+   if (!is_gimple_assign (stmt))
+     return NULL;
+ 
+   if (root_node_p)
+     {
+       bytes_moved_inplace = 0;
+       source_expr = NULL;
+       type_size = int_cst_value (TYPE_SIZE (TREE_TYPE (
+                                              gimple_assign_lhs (stmt))));
+     }
+ 
+   code = gimple_assign_rhs_code (stmt);
+ 
+   if (code == BIT_IOR_EXPR)
+     {
+       tree left, right;
+ 
+       left = gimple_assign_rhs1 (stmt);
+       right = gimple_assign_rhs2 (stmt);
+ 
+       if (TREE_CODE (left) != SSA_NAME || TREE_CODE (right) != SSA_NAME)
+ 	return NULL;
+ 
+       left = find_bswap_1 (SSA_NAME_DEF_STMT (left), false);
+       right = find_bswap_1 (SSA_NAME_DEF_STMT (right), false);
+ 
+       return left ? left : right;
+     }
+ 
+   if (root_node_p)
+     return NULL;
+ 
+   if (code != LSHIFT_EXPR && code != RSHIFT_EXPR)
+     return NULL;
+ 
+   if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
+     return NULL;
+ 
+   shift_count = int_cst_value (gimple_assign_rhs2 (stmt));
+ 
+   if (shift_count & 7)
+     return NULL;
+ 
+   /* Calculate the number of the byte being shifted starting at the
+      lowest order byte with 0.  */
+   bytenum = ((shift_count >> 3) - 1) >> 1;
+ 
+   if (code == LSHIFT_EXPR)
+     bytenum = (type_size >> 4) - 1 - bytenum;
+   else
+     bytenum = (type_size >> 4) + bytenum;
+ 
+   if (TREE_CODE (gimple_assign_rhs1 (stmt)) != SSA_NAME)
+     return NULL;
+ 
+   op = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
+ 
+   if (!op || !is_gimple_assign (op)
+       || gimple_assign_rhs_code (op) != BIT_AND_EXPR)
+     {
+       /* The two shifts moving the leftmost and rightmost bytes work
+ 	 without masking the bits before.  */
+       if (shift_count != (type_size - 8))
+ 	return NULL;
+ 
+       source = gimple_assign_rhs1 (stmt);
+     }
+   else
+     {
+       /* The operand is masked with an AND rtx.  Check if the proper
+ 	 mask is used.  */
+       tree mask = gimple_assign_rhs2 (op);
+       if (TREE_CODE (mask) != INTEGER_CST
+ 	  || int_cst_value (mask) != (HOST_WIDE_INT)0xff << (bytenum * 8))
+ 	return NULL;
+       source = gimple_assign_rhs1 (op);
+     }
+ 
+   if (TREE_CODE (source) != SSA_NAME)
+     return NULL;
+ 
+   if (!source_expr)
+     source_expr = source;
+ 
+   /* All operands have to use the same source.  */
+   if (source_expr != source)
+     return NULL;
+ 
+   /* The byte has already been moved in place.  */
+   if (bytes_moved_inplace & (1 << bytenum))
+     return NULL;
+ 
+   bytes_moved_inplace |= 1 << bytenum;
+ 
+   if (bytes_moved_inplace != ((1 << (type_size >> 3)) - 1))
+     return NULL;
+ 
+   return source_expr;
+ }
+ 
+ /* Check if STMT completes a bswap implementation consisting of ORs,
+    SHIFTs and ANDs.  Return the source tree expression on which the
+    byte swap is performed and NULL if no bswap was found.  */
+ 
+ static tree
+ find_bswap (gimple stmt)
+ {
+   if (!is_gimple_assign (stmt))
+     return NULL;
+ 
+   return find_bswap_1 (stmt, true);
+ }
+ 
+ /* Find manual byte swap implementations and turn them into a bswap
+    builtin invokation.  */
+ 
+ static unsigned int
+ execute_optimize_bswap (void)
+ {
+   basic_block bb;
+ 
+   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 = find_bswap (stmt);
+ 	  tree fndecl;
+ 	  HOST_WIDE_INT type_size;
+ 	  gimple call;
+ 
+ 	  if (!bswap_src)
+ 	    continue;
+ 
+ 	  type_size = int_cst_value (TYPE_SIZE (TREE_TYPE (
+                                                  gimple_assign_lhs (stmt))));
+ 
+ 	  switch (type_size)
+ 	    {
+ 	    case 32:
+ 	      fndecl = built_in_decls[BUILT_IN_BSWAP32];
+ 	      break;
+ 	    case 64:
+ 	      fndecl = built_in_decls[BUILT_IN_BSWAP64];
+ 	      break;
+ 	    default:
+ 	      continue;
+ 	    }
+ 	  call = gimple_build_call (fndecl, 1, bswap_src);
+ 	  gimple_call_set_lhs (call, gimple_assign_lhs (stmt));
+ 
+ 	  if (dump_file)
+ 	    {
+ 	      fprintf (dump_file, "bswap implemenation found at: ");
+ 	      print_gimple_stmt (dump_file, stmt, 0, 0);
+ 	    }
+ 
+ 	  gsi_insert_after (&gsi, call, GSI_SAME_STMT);
+ 	  gsi_remove (&gsi, true);
+ 	}
+     }
+ 
+   return 0;
+ }
+ 
+ static bool
+ gate_optimize_bswap (void)
+ {
+   return optimize;
+ }
+ 
+ struct gimple_opt_pass pass_optimize_bswap =
+ {
+  {
+   GIMPLE_PASS,
+   "bswap",				/* name */
+   gate_optimize_bswap,                  /* gate */
+   execute_optimize_bswap,		/* execute */
+   NULL,					/* sub */
+   NULL,					/* next */
+   0,					/* static_pass_number */
+   0,					/* tv_id */
+   PROP_ssa,				/* properties_required */
+   0,					/* properties_provided */
+   0,					/* properties_destroyed */
+   0,					/* todo_flags_start */
+   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
+     | TODO_verify_stmts                 /* todo_flags_finish */
+  }
+ };
Index: gcc/testsuite/gcc.dg/optimize-bswap-1.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/optimize-bswap-1.c	2008-11-28 12:55:23.000000000 +0100
***************
*** 0 ****
--- 1,38 ----
+ /* { dg-do compile } */
+ /* { dg-require-effective-target stdint_types } */
+ /* { dg-options "-O2 -fdump-tree-bswap" } */
+ 
+ #include <stdint.h>
+ 
+ /* These are the byte swap implementations used by the Linux kernel.  */
+ 
+ #define __const_swab32(x) ((uint32_t)(				      \
+         (((uint32_t)(x) & (uint32_t)0x000000ffUL) << 24) |            \
+         (((uint32_t)(x) & (uint32_t)0x0000ff00UL) <<  8) |            \
+         (((uint32_t)(x) & (uint32_t)0x00ff0000UL) >>  8) |            \
+         (((uint32_t)(x) & (uint32_t)0xff000000UL) >> 24)))
+ 
+ #define __const_swab64(x) ((uint64_t)(			                        \
+ 	(((uint64_t)(x) & (uint64_t)0x00000000000000ffULL) << 56) |             \
+ 	(((uint64_t)(x) & (uint64_t)0x000000000000ff00ULL) << 40) |		\
+ 	(((uint64_t)(x) & (uint64_t)0x0000000000ff0000ULL) << 24) |		\
+ 	(((uint64_t)(x) & (uint64_t)0x00000000ff000000ULL) <<  8) |		\
+ 	(((uint64_t)(x) & (uint64_t)0x000000ff00000000ULL) >>  8) |		\
+ 	(((uint64_t)(x) & (uint64_t)0x0000ff0000000000ULL) >> 24) |		\
+ 	(((uint64_t)(x) & (uint64_t)0x00ff000000000000ULL) >> 40) |		\
+ 	(((uint64_t)(x) & (uint64_t)0xff00000000000000ULL) >> 56)))
+ 
+ uint32_t
+ swap32 (uint32_t in)
+ {
+   return __const_swab32 (in);
+ }
+ 
+ uint64_t
+ swap64 (uint64_t in)
+ {
+   return __const_swab64 (in);
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "bswap implemenation found at" 2 "bswap" } } */
+ /* { dg-final { cleanup-tree-dump "bswap" } } */


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