Patchwork Remove useless BIT_AND_EXPRs

login
register
mail settings
Submitter Jeff Law
Date April 22, 2013, 2:59 a.m.
Message ID <5174A77D.6070505@redhat.com>
Download mbox | patch
Permalink /patch/238287/
State New
Headers show

Comments

Jeff Law - April 22, 2013, 2:59 a.m.
While looking at dumps I noticed a lot of sequences like

t = a & 1;
x = (bool) t;


The BIT_AND_EXPR is obviously redundant as the narrowing cast has the 
same effect.  This can be trivially generalized for other integral types 
and an appropriate constant.

At different times over the last couple weeks I've formulated this 
optimization in DOM, VRP & forwprop/combine.  Ultimately 
forwprop/combine seems like the right place.

The only thing even marginally weird here is there is no DCE pass after 
the last forwprop pass.   Since this code only does the simplification 
when the result of the BIT_AND_EXPR has a single use in the cast, it can 
trivially clean up after itself and not leave trivially dead code in the 
statement stream.

Bootstrapped & regression tested on x86_64-unknown-linux-gnu.  Installed.
commit 5ac2f05b16c5193c9b760a9493546e36a67ad38c
Author: Jeff Law <law@redhat.com>
Date:   Sun Apr 21 20:57:47 2013 -0600

    	* tree-ssa-forwprop.c (simplify_conversion_from_bitmask): New function.
    	(ssa_forward_propagate_and_combine): Use it.
    
    	* gcc.dg/tree-ssa/forwprop-26.c: New test.

Patch

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 60d2081..469a8b9 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@ 
+2013-04-21  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-forwprop.c (simplify_conversion_from_bitmask): New function.
+	(ssa_forward_propagate_and_combine): Use it.
+
 2013-04-19  Vladimir Makarov  <vmakarov@redhat.com>
 
 	* lra.c: Update the flow chart diagram.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index f8501e0..0c05a76 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@ 
+2013-04-21  Jeff Law  <law@redhat.com>
+
+	* gcc.dg/tree-ssa/forwprop-26.c: New test.
+
 2013-04-20  Tobias Burnus  <burnus@net-b.de>
 
 	PR fortran/56907
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-26.c b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-26.c
new file mode 100644
index 0000000..14821af
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-26.c
@@ -0,0 +1,64 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-forwprop1" } */
+
+union tree_node;
+typedef union tree_node *tree;
+enum tree_code
+{
+  MAX_TREE_CODES
+};
+extern unsigned char tree_contains_struct[MAX_TREE_CODES][64];
+struct tree_base
+{
+  __extension__ enum tree_code code:16;
+  unsigned public_flag:1;
+};
+enum tree_node_structure_enum
+{
+  TS_DECL_WITH_VIS,
+};
+struct tree_decl_with_vis
+{
+  unsigned comdat_flag:1;
+};
+union tree_node
+{
+  struct tree_base base;
+  struct tree_decl_with_vis decl_with_vis;
+};
+struct varpool_node
+{
+  tree decl;
+  struct varpool_node *next_needed, *prev_needed;
+  unsigned externally_visible:1;
+};
+extern struct varpool_node *varpool_nodes_queue;
+struct pointer_set_t;
+struct pointer_set_t *pointer_set_create (void);
+__inline__ static unsigned char
+varpool_externally_visible_p (struct varpool_node *vnode,
+			      unsigned char aliased)
+{
+  struct varpool_node *alias;
+  if (!(( { __typeof (vnode->decl) const __t = (vnode->decl); __t;})->decl_with_vis.comdat_flag)
+      && !((vnode->decl)->base.public_flag))
+    return 0;
+  if (aliased)
+    return 1;
+  return 0;
+}
+
+unsigned int
+function_and_variable_visibility (unsigned char whole_program)
+{
+  struct cgraph_node *node;
+  struct varpool_node *vnode;
+  struct pointer_set_t *aliased_vnodes = pointer_set_create ();
+  for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
+    if (varpool_externally_visible_p
+	(vnode, pointer_set_contains (aliased_vnodes, vnode)))
+      vnode->externally_visible = 1;
+}
+
+/* { dg-final { scan-tree-dump-not "& 255" "forwprop1"} } */
+/* { dg-final { cleanup-tree-dump "forwprop1" } } */
diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c
index ac930c6..715082c 100644
--- a/gcc/tree-ssa-forwprop.c
+++ b/gcc/tree-ssa-forwprop.c
@@ -1142,6 +1142,77 @@  bailout:
 }
 
 
+/* GSI_P points to a statement which performs a narrowing integral
+   conversion.
+
+   Look for cases like:
+
+     t = x & c;
+     y = (T) t;
+
+   Turn them into:
+
+     t = x & c;
+     y = (T) x;
+
+   If T is narrower than X's type and C merely masks off bits outside
+   of (T) and nothing else.
+
+   Normally we'd let DCE remove the dead statement.  But no DCE runs
+   after the last forwprop/combine pass, so we remove the obviously
+   dead code ourselves.
+
+   Return TRUE if a change was made, FALSE otherwise.  */
+
+static bool 
+simplify_conversion_from_bitmask (gimple_stmt_iterator *gsi_p)
+{
+  gimple stmt = gsi_stmt (*gsi_p);
+  gimple rhs_def_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
+
+  /* See if the input for the conversion was set via a BIT_AND_EXPR and
+     the only use of the BIT_AND_EXPR result is the conversion.  */
+  if (is_gimple_assign (rhs_def_stmt)
+      && gimple_assign_rhs_code (rhs_def_stmt) == BIT_AND_EXPR
+      && has_single_use (gimple_assign_lhs (rhs_def_stmt)))
+    {
+      tree rhs_def_operand1 = gimple_assign_rhs1 (rhs_def_stmt);
+      tree rhs_def_operand2 = gimple_assign_rhs2 (rhs_def_stmt);
+      tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
+
+      /* Now verify suitability of the BIT_AND_EXPR's operands.
+	 The first must be an SSA_NAME that we can propagate and the
+	 second must be an integer constant that masks out all the
+	 bits outside the final result's type, but nothing else.  */
+      if (TREE_CODE (rhs_def_operand1) == SSA_NAME
+	  && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand1)
+	  && TREE_CODE (rhs_def_operand2) == INTEGER_CST
+	  && operand_equal_p (rhs_def_operand2,
+			      build_low_bits_mask (TREE_TYPE (rhs_def_operand2),
+			       			   TYPE_PRECISION (lhs_type)),
+						   0))
+	{
+	  /* This is an optimizable case.  Replace the source operand
+	     in the conversion with the first source operand of the
+	     BIT_AND_EXPR.  */
+	  gimple_assign_set_rhs1 (stmt, rhs_def_operand1);
+	  stmt = gsi_stmt (*gsi_p);
+	  update_stmt (stmt);
+
+	  /* There is no DCE after the last forwprop pass.  It's
+	     easy to clean up the first order effects here.  */
+	  gimple_stmt_iterator si;
+	  si = gsi_for_stmt (rhs_def_stmt);
+	  gsi_remove (&si, true);
+	  release_defs (rhs_def_stmt);
+	  return true;
+	}
+    }
+
+  return false;
+}
+
+
 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
    If so, we can change STMT into lhs = y which can later be copy
    propagated.  Similarly for negation.
@@ -3059,6 +3130,23 @@  ssa_forward_propagate_and_combine (void)
 		    int did_something = combine_conversions (&gsi);
 		    if (did_something == 2)
 		      cfg_changed = true;
+
+		    /* If we have a narrowing conversion to an integral
+		       type that is fed by a BIT_AND_EXPR, we might be
+		       able to remove the BIT_AND_EXPR if it merely
+		       masks off bits outside the final type (and nothing
+		       else.  */
+		    if (! did_something)
+		      {
+			tree outer_type = TREE_TYPE (gimple_assign_lhs (stmt));
+			tree inner_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
+			if (INTEGRAL_TYPE_P (outer_type)
+			    && INTEGRAL_TYPE_P (inner_type)
+			    && (TYPE_PRECISION (outer_type)
+				<= TYPE_PRECISION (inner_type)))
+			  did_something = simplify_conversion_from_bitmask (&gsi);
+		      }
+		      
 		    changed = did_something != 0;
 		  }
 		else if (code == VEC_PERM_EXPR)