Patchwork [tree-optimization] : Fix for PR 45397 part 1 of 2

login
register
mail settings
Submitter Michael Matz
Date March 15, 2012, 4:25 p.m.
Message ID <Pine.LNX.4.64.1203151720450.25409@wotan.suse.de>
Download mbox | patch
Permalink /patch/147043/
State New
Headers show

Comments

Michael Matz - March 15, 2012, 4:25 p.m.
Hi,

On Thu, 15 Mar 2012, Richard Guenther wrote:

> > The type demotion is PR45397/PR47477 among other PRs. I'd just walk 
> > from the narrowing integer conversion stmts recursively through the 
> > def stmts, see if they can be narrowed, note it, and finally if 
> > everything or significant portion of the stmts can be demoted (if not 
> > all, with some narrowing integer conversion stmt inserted), do it all 
> > together.
> 
> For PROMOTE_MODE targets you'd promote but properly mask out
> constants (to make them cheaper to generate, for example).  You'd
> also take advantate of targets that can do zero/sign-extending loads
> without extra cost (ISTR that's quite important for some SPEC 2k6
> benchmark on x86_64).

gamess.  I still have an old proof of concept patch doing type promotion.  
Probably doesn't apply anymore, and it's using too broad predicates (it 
simple-mindedly extends to the largest type see in an expression tree).
But I think that basic idea of it is sound.


Ciao,
Michael.

Patch

Index: passes.c
===================================================================
--- passes.c	(revision 159226)
+++ passes.c	(working copy)
@@ -831,6 +831,7 @@  init_optimization_passes (void)
   NEXT_PASS (pass_all_optimizations);
     {
       struct opt_pass **p = &pass_all_optimizations.pass.sub;
+      extern struct gimple_opt_pass pass_bprop_extends;
       NEXT_PASS (pass_remove_cgraph_callee_edges);
       /* Initial scalar cleanups before alias computation.
 	 They ensure memory accesses are not indirect wherever possible.  */
@@ -838,6 +839,7 @@  init_optimization_passes (void)
       NEXT_PASS (pass_update_address_taken);
       NEXT_PASS (pass_rename_ssa_copies);
       NEXT_PASS (pass_complete_unrolli);
+      NEXT_PASS (pass_bprop_extends);
       NEXT_PASS (pass_ccp);
       NEXT_PASS (pass_forwprop);
       NEXT_PASS (pass_call_cdce);
Index: tree-ssa-ccp.c
===================================================================
--- tree-ssa-ccp.c	(revision 159226)
+++ tree-ssa-ccp.c	(working copy)
@@ -1999,3 +1999,263 @@  struct gimple_opt_pass pass_fold_builtin
     | TODO_update_ssa			/* todo_flags_finish */
  }
 };
+
+#if 1
+static bool
+promote_through_insn_p (gimple def, tree *prhs1, tree *prhs2)
+{
+  tree lhs, rhs1, rhs2;
+  if (!is_gimple_assign (def))
+    return false;
+  lhs = gimple_assign_lhs (def);
+  rhs1 = rhs2 = NULL;
+  switch (gimple_assign_rhs_class (def))
+    {
+      case GIMPLE_SINGLE_RHS:
+	rhs1 = gimple_assign_rhs1 (def);
+	if (TREE_CODE (rhs1) != SSA_NAME)
+	  return false;
+	break;
+      case GIMPLE_UNARY_RHS:
+	rhs1 = gimple_assign_rhs1 (def);
+	if (TREE_TYPE (gimple_expr_type (def)) != TREE_TYPE (rhs1))
+	  return false;
+	break;
+      case GIMPLE_BINARY_RHS:
+	rhs1 = gimple_assign_rhs1 (def);
+	rhs2 = gimple_assign_rhs2 (def);
+
+	switch (gimple_assign_rhs_code (def))
+	  {
+	    case LSHIFT_EXPR: case RSHIFT_EXPR:
+	    case LROTATE_EXPR: case RROTATE_EXPR:
+	      rhs2 = NULL;
+	      if (TREE_TYPE (lhs) != TREE_TYPE (rhs1))
+		return false;
+	      break;
+	    case PLUS_EXPR: case MINUS_EXPR:
+	    case MULT_EXPR: case EXACT_DIV_EXPR:
+	    case TRUNC_DIV_EXPR: case CEIL_DIV_EXPR:
+	    case FLOOR_DIV_EXPR: case ROUND_DIV_EXPR:
+	    case TRUNC_MOD_EXPR: case CEIL_MOD_EXPR:
+	    case FLOOR_MOD_EXPR: case ROUND_MOD_EXPR:
+	    case RDIV_EXPR:
+	    case MIN_EXPR: case MAX_EXPR:
+	    case BIT_IOR_EXPR: case BIT_XOR_EXPR: case BIT_AND_EXPR:
+	      if (TREE_TYPE (lhs) != TREE_TYPE (rhs1)
+		  || TREE_TYPE (lhs) != TREE_TYPE (rhs2))
+		return false;
+	      break;
+	    default:
+	      return false;
+	  }
+	break;
+      default:
+	return false;
+    }
+  if (rhs1 && TREE_CODE (rhs1) != SSA_NAME)
+    rhs1 = NULL;
+  if (prhs1)
+    *prhs1 = rhs1;
+  if (rhs2 && TREE_CODE (rhs2) != SSA_NAME)
+    rhs2 = NULL;
+  if (prhs2)
+    *prhs2 = rhs2;
+  return true;
+}
+
+static tree
+get_extended_version (tree newtype, tree name, bool force)
+{
+  tree ret = TREE_CHAIN (name);
+  tree rhs1, rhs2;
+  gimple def;
+  /* If we already have a version of NAME, try to use it.  If it
+     doesn't match in type, fail.  */
+  if (ret)
+    {
+      if (TREE_TYPE (ret) == newtype)
+	return ret;
+      else
+	return NULL_TREE;
+    }
+  def = SSA_NAME_DEF_STMT (name);
+  /* If we can propagate through our defining insn, try to do that.  */
+  if (promote_through_insn_p (def, &rhs1, &rhs2))
+    {
+      gimple stmt;
+      tree extrhs1, extrhs2;
+      gimple_stmt_iterator gsi;
+      enum tree_code code;
+      if (rhs1)
+	{
+	  extrhs1 = get_extended_version (newtype, rhs1, true);
+	  if (!extrhs1)
+	    /* ??? We could force here.  */
+	    return NULL_TREE;
+	}
+      else
+	extrhs1 = gimple_assign_rhs1 (def);
+      if (extrhs1 && !useless_type_conversion_p (newtype, TREE_TYPE (extrhs1)))
+	{
+	  gcc_assert (is_gimple_min_invariant (extrhs1));
+	  extrhs1 = fold_convert (newtype, extrhs1);
+	}
+      if (rhs2)
+	{
+	  extrhs2 = get_extended_version (newtype, rhs2, true);
+	  if (!extrhs2)
+	    return NULL_TREE;
+	}
+      else
+	extrhs2 = gimple_assign_rhs2 (def);
+      code = gimple_assign_rhs_code (def);
+      if (extrhs2
+	  && code != LSHIFT_EXPR && code != RSHIFT_EXPR
+	  && code != LROTATE_EXPR && code != RROTATE_EXPR
+	  && !useless_type_conversion_p (newtype, TREE_TYPE (extrhs2)))
+	{
+	  gcc_assert (is_gimple_min_invariant (extrhs2));
+	  extrhs2 = fold_convert (newtype, extrhs2);
+	}
+      ret = create_tmp_reg (newtype, NULL);
+      add_referenced_var (ret);
+      ret = make_ssa_name (ret, NULL);
+      stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (def),
+					   ret, extrhs1, extrhs2);
+      gsi = gsi_for_stmt (def);
+      gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+    }
+  else if (force)
+    {
+      gimple stmt;
+      gimple_stmt_iterator gsi;
+      /* We can't propagate through our defining statement, so emit
+         a conversion explicitely.  */
+      ret = create_tmp_reg (newtype, NULL);
+      add_referenced_var (ret);
+      ret = make_ssa_name (ret, NULL);
+      stmt = gimple_build_assign_with_ops (NOP_EXPR, ret, name, NULL);
+      if (gimple_nop_p (def))
+	{
+	  gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
+	  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
+	}
+      else if (gimple_code (def) == GIMPLE_PHI)
+	{
+	  gsi = gsi_after_labels (gimple_bb (def));
+	  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
+	}
+      else if (!stmt_ends_bb_p (def))
+	{
+	  gsi = gsi_for_stmt (def);
+	  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+	}
+      else
+	{
+	  /* XXX We could search the fallthru edge, and insert there.
+	     That's correct because if this statement ends the BB it
+	     must be throwing (it can't be a conditional), and hence
+	     the result (which we want to extend) actually is only
+	     available on the fallthru edge.  But inserting on edges
+	     might create new basic blocks, and that doesn't seem 
+	     worth it.  We could do that if the fallthru successor
+	     has only one incoming edge.  Actually we can be sure that
+	     this is the case, as NAME can't be used in a PHI node
+	     (we don't call ourself on them), hence it must be used
+	     in something we dominate and therefore our fallthru successor
+	     must have only one incoming edge.  */
+#if 0
+	  edge e;
+	  edge_iterator ei;
+
+	  FOR_EACH_EDGE (e, ei, gimple_bb (def)->succs)
+	    if (e->flags & EDGE_FALLTHRU)
+	      gsi_insert_on_edge_immediate (e, sum);
+#endif
+	  return NULL_TREE;
+	}
+    }
+  TREE_CHAIN (name) = ret;
+  return ret;
+}
+
+static unsigned int
+execute_bprop_extends (void)
+{
+  unsigned int todoflags = 0;
+  size_t i;
+  /*bitmap_iterator bi;*/
+  bitmap new_extend = BITMAP_ALLOC (NULL);
+
+  /* Collect SSA names that we'd like to have in a wider type.  */
+  for (i = 0; i < num_ssa_names; i++)
+    {
+      tree lhs = ssa_name (i);
+      if (lhs)
+	{
+	  gimple def = SSA_NAME_DEF_STMT (lhs);
+	  tree rhs;
+	  TREE_CHAIN (lhs) = NULL;
+	  if (!is_gimple_assign (def)
+	      || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
+	    continue;
+	  rhs = gimple_assign_rhs1 (def);
+	  /* We could handle int->pointer conversions with some care
+	     through which insns we look through.  Don't bother for now.  */
+	  if (POINTER_TYPE_P (TREE_TYPE (lhs))
+	      || POINTER_TYPE_P (TREE_TYPE (rhs)))
+	    continue;
+	  if (TYPE_PRECISION (TREE_TYPE (lhs))
+	      <= TYPE_PRECISION (TREE_TYPE (rhs)))
+	    continue;
+	  if (!nowrap_type_p (TREE_TYPE (rhs)))
+	    continue;
+	  bitmap_set_bit (new_extend, SSA_NAME_VERSION (lhs));
+	}
+    }
+
+  while (!bitmap_empty_p (new_extend))
+    {
+      tree lhs, rhs, extlhs;
+      gimple def;
+      i = bitmap_first_set_bit (new_extend);
+      bitmap_clear_bit (new_extend, i);
+      lhs = ssa_name (i);
+      gcc_assert (lhs);
+      def = SSA_NAME_DEF_STMT (lhs);
+      rhs = gimple_assign_rhs1 (def);
+      extlhs = get_extended_version (TREE_TYPE (lhs), rhs, false);
+      if (extlhs)
+	{
+	  gimple_assign_set_rhs1 (def, extlhs);
+	  gimple_assign_set_rhs_code (def, SSA_NAME);
+	  update_stmt (def);
+	}
+    }
+
+  BITMAP_FREE (new_extend);
+  return todoflags;
+}
+
+struct gimple_opt_pass pass_bprop_extends =
+{
+ {
+  GIMPLE_PASS,
+  "bprop",				/* name */
+  NULL,					/* gate */
+  execute_bprop_extends,		/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_NONE,				/* tv_id */
+  PROP_cfg | PROP_ssa,			/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func
+    | TODO_verify_ssa
+    | TODO_update_ssa			/* todo_flags_finish */
+ }
+};
+#endif