[PATCH] Teach SCCVN/PRE about type-punning through unions

[Richard Guenther <rguenther at suse dot de>]

This patch is an alternate implementation to
http://gcc.gnu.org/ml/gcc-patches/2008-02/msg01422.html
to optimize type-punning operations through unions to use scalar
operations (aka VIEW_CONVERT_EXPR).

It does so by doing (pseudo-)insertion of new expressions with an
associated SSA_NAME (to hold its value number) during the final
SCC iteration.  At PRE/FRE elimination time these expressions are
inserted in place of the SSA_NAME (that is, no real insertion takes
place, but we replace with an expression instead of an SSA_NAME),
properly re-constructed with using expression leaders for its
operands (where available).

Variants of this approach would be to add the fake SSA_NAMEs
during regular SCC iteration, but then also to the SCC itself
(which was too tricky for me, thus only doing that at the final
iteration).

On the PRE/FRE side a new insertion phase after SCCVN could insert
the expressions explicitly (like we insert fake stores);  I don't
know if this would fix anything or make anything easier at the
point of insertion though (at least we would only insert a replacement
expression once).  The problem with availability we face is that for

union { int i; float f; } u;

 # VUSE <u_1>
 tmp_2 = u.i;
 # VUSE <u_1>
 tmp_1 = u.f;

SCCVN (randomly?) processes the SCCs for tmp_1 and tmp_2 and thus
can end up value-numbering tmp_2 as VIEW_CONVERT_EXPR <tmp_1> which
obviously would violate SSA form.  Usually bitmap_find_leader sorts
this out, but for libgomp.fortran/retval1.f90 it doesn't (thus
the extra code in the substitute_leaders_in_expr helper function).

With doing real insertion before compute_avail the same problem is
there, as the expression tmp_4 = VIEW_CONVERT_EXPR <tmp_1> (tmp_4
is the fake SSA_NAME SCCVN uses for the value-number of tmp_2)
cannot be inserted anywhere if tmp_4 is used by tmp_2.

Danny, do you have any idea to the above problem?  (Other than
unconditionally inserting expressions for VIEW_CONVERT_EXPR to
any other union member even before running SCCVN)

But, the following was bootstrapped and tested on x86_64-unknown-linux-gnu
and fixes PRs 34043 and 33989 (and maybe others), like the other
patch referenced above.

Shall we just pick one or are there suggestions for improvements
for either approaches?

Thanks,
Richard.

2008-02-29  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/34043
	PR tree-optimization/33989
	* tree-ssa-pre.c (get_sccvn_value): Build a value handle for
	to be inserted expressions.
	(substitute_leaders_in_expr): New function.
	(eliminate): If we do not have a fully redundant leader but
	can insert an alternate simplified expression, do so with all
	operands replaced with their leader.
	* tree-ssa-sccvn.h (struct vn_ssa_aux): Add needs_insertion flag.
	* tree-ssa-sccvn.c (copy_reference_ops_from_ref): Value-number
	union member access based on its size, not type and member.
	(visit_reference_op_load): For a weak match from union type
	punning create a fake SSA_NAME to attach a value-number for
	the result VIEW_CONVERTed to the correct type.
	(free_scc_vn): Release fake SSA_NAMEs again.

	* gcc.dg/tree-ssa/ssa-fre-7.c: New testcase.
	* gcc.dg/tree-ssa/ssa-fre-8.c: Likewise.

Index: trunk/gcc/tree-ssa-pre.c
===================================================================
*** trunk.orig/gcc/tree-ssa-pre.c	2008-03-01 19:51:04.000000000 +0100
--- trunk/gcc/tree-ssa-pre.c	2008-03-01 22:39:23.000000000 +0100
*************** get_sccvn_value (tree name)
*** 3237,3247 ****
        bool is_invariant = is_gimple_min_invariant (val);
        tree valvh = !is_invariant ? get_value_handle (val) : NULL_TREE;
  
        /* We may end up with situations where SCCVN has chosen a
  	 representative for the equivalence set that we have not
  	 visited yet.  In this case, just create the value handle for
  	 it.  */
!       if (!valvh && !is_invariant)
  	{
  	  tree defstmt = SSA_NAME_DEF_STMT (val);
  
--- 3237,3252 ----
        bool is_invariant = is_gimple_min_invariant (val);
        tree valvh = !is_invariant ? get_value_handle (val) : NULL_TREE;
  
+       /* In the case SCCVN has created a dummy SSA_NAME to value
+ 	 number a simplified expression, just create a value handle
+ 	 for it.  */
+       if (!valvh && !is_invariant && VN_INFO (val)->needs_insertion)
+ 	valvh = vn_lookup_or_add (VN_INFO (val)->expr);
        /* We may end up with situations where SCCVN has chosen a
  	 representative for the equivalence set that we have not
  	 visited yet.  In this case, just create the value handle for
  	 it.  */
!       else if (!valvh && !is_invariant)
  	{
  	  tree defstmt = SSA_NAME_DEF_STMT (val);
  
*************** compute_avail (void)
*** 3590,3595 ****
--- 3595,3648 ----
    free (worklist);
  }
  
+ /* Substitutes leaders for all operands in EXPR supposed to replace
+    the rhs of STMT in basic-block BB.
+    Returns an available expression if that succeeds, NULL_TREE otherwise.  */
+ 
+ static tree
+ substitute_leaders_in_expr (basic_block bb, tree stmt, tree expr)
+ {
+   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
+     {
+     case tcc_reference:
+       if (TREE_CODE (expr) != VIEW_CONVERT_EXPR
+ 	  && TREE_CODE (expr) != REALPART_EXPR
+ 	  && TREE_CODE (expr) != IMAGPART_EXPR)
+ 	return NULL_TREE;
+ 
+       /* Fallthrough.  */
+     case tcc_unary:
+       if (is_gimple_min_invariant (TREE_OPERAND (expr, 0)))
+ 	return expr;
+       if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME)
+         {
+ 	  tree def_stmt;
+ 	  tree tmp = get_value_handle (TREE_OPERAND (expr, 0));
+ 	  tmp = bitmap_find_leader (AVAIL_OUT (bb), tmp);
+ 	  if (!tmp)
+ 	    return NULL_TREE;
+ 	  /* tmp can still be unavailable if it is defined in the same
+ 	     basic-block, but after stmt.  libgomp.fortran/retval1.f90:f5  */
+ 	  def_stmt = SSA_NAME_DEF_STMT (tmp);
+ 	  if (def_stmt
+ 	      && TREE_CODE (def_stmt) != PHI_NODE
+ 	      && bb_for_stmt (def_stmt) == bb)
+ 	    {
+ 	      block_stmt_iterator bsi = bsi_start (bb);
+ 	      while (bsi_stmt (bsi) != def_stmt)
+ 		{
+ 		  if (bsi_stmt (bsi) == stmt)
+ 		    return NULL_TREE;
+ 		  bsi_next (&bsi);
+ 		}
+ 	    }
+ 	  return build1 (TREE_CODE (expr), TREE_TYPE (expr), tmp);
+ 	}
+ 
+     default:;
+     }
+   return NULL_TREE;
+ }
  
  /* Eliminate fully redundant computations.  */
  
*************** eliminate (void)
*** 3622,3627 ****
--- 3675,3696 ----
  	      sprime = bitmap_find_leader (AVAIL_OUT (b),
  					   get_value_handle (lhs));
  
+ 	      /* If we didn't find a leader but have an expression
+ 		 we can insert, use that as replacement.  */
+ 	      if (sprime
+ 		  && sprime == lhs
+ 		  && VN_INFO (lhs)->valnum != VN_TOP
+ 		  /* Instead of VN_TOP we also can end up with a
+ 		     constant value.  g++.dg/opt/reload1.C  */
+ 		  && TREE_CODE (VN_INFO (lhs)->valnum) == SSA_NAME
+ 		  && VN_INFO (VN_INFO (lhs)->valnum)->needs_insertion)
+ 		{
+ 		  tree tmp = VN_INFO (VN_INFO (lhs)->valnum)->expr;
+ 		  tmp = substitute_leaders_in_expr (b, stmt, tmp);
+ 		  if (tmp)
+ 		    sprime = tmp;
+ 		}
+ 
  	      if (sprime
  		  && sprime != lhs
  		  && (TREE_CODE (*rhs_p) != SSA_NAME
Index: trunk/gcc/tree-ssa-sccvn.c
===================================================================
*** trunk.orig/gcc/tree-ssa-sccvn.c	2008-03-01 19:53:24.000000000 +0100
--- trunk/gcc/tree-ssa-sccvn.c	2008-03-01 19:53:24.000000000 +0100
*************** copy_reference_ops_from_ref (tree ref, V
*** 544,551 ****
  	  temp.op1 = TREE_OPERAND (ref, 2);
  	  break;
  	case COMPONENT_REF:
! 	  /* Record field as operand.  */
! 	  temp.op0 = TREE_OPERAND (ref, 1);
  	  break;
  	case ARRAY_RANGE_REF:
  	case ARRAY_REF:
--- 544,561 ----
  	  temp.op1 = TREE_OPERAND (ref, 2);
  	  break;
  	case COMPONENT_REF:
! 	  /* If this is a reference to a union member, record the union
! 	     member size as operand.  */
! 	  if (TREE_CODE (DECL_CONTEXT (TREE_OPERAND (ref, 1))) == UNION_TYPE
! 	      && integer_zerop (DECL_FIELD_OFFSET (TREE_OPERAND (ref, 1)))
! 	      && integer_zerop (DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1))))
! 	    {
! 	      temp.type = NULL_TREE;
! 	      temp.op0 = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)));
! 	    }
! 	  else
! 	    /* Record field as operand.  */
! 	    temp.op0 = TREE_OPERAND (ref, 1);
  	  break;
  	case ARRAY_RANGE_REF:
  	case ARRAY_REF:
*************** defs_to_varying (tree stmt)
*** 1165,1170 ****
--- 1175,1183 ----
    return changed;
  }
  
+ static tree
+ try_to_simplify (tree stmt, tree rhs);
+ 
  /* Visit a copy between LHS and RHS, return true if the value number
     changed.  */
  
*************** visit_reference_op_load (tree lhs, tree 
*** 1237,1244 ****
    bool changed = false;
    tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt));
  
!   if (result)
!     {
        changed = set_ssa_val_to (lhs, result);
      }
    else
--- 1250,1298 ----
    bool changed = false;
    tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt));
  
!   /* We handle type-punning through unions by value-numbering based
!      on offset and size of the access.  Be prepared to handle a
!      type-mismatch here via creating a VIEW_CONVERT_EXPR.
!      Do this only after the iteration converged as introducing new
!      SSA_NAMEs will let it never finish otherwise.  */
!   if (result
!       && (useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op))
! 	  || current_info == valid_info))
!     {
!       if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
! 	{
! 	  tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op),
! 				  result);
! 	  /* Make sure to simplify with earlier conversions as otherwise
! 	     our dummy SSA_NAMEs start to leak all over.  */
! 	  if (TREE_CODE (val) == VIEW_CONVERT_EXPR)
! 	    val = try_to_simplify (stmt, val);
! 	  result = val;
! 	  if (result != lhs
! 	      && !is_gimple_min_invariant (val)
! 	      && TREE_CODE (val) != SSA_NAME)
! 	    /* Finally do a lookup to not create redundant conversions.  */
! 	    result = vn_unary_op_lookup (val);
! 	  if (!result)
! 	    {
! 	      /* Create a new temporary SSA_NAME to attach the
! 		 conversion expression to.  */
! 	      result = make_ssa_name (SSA_NAME_VAR (lhs), NULL_TREE);
! 	      VN_INFO_GET (result)->valnum = result;
! 	      VN_INFO (result)->expr = val;
! 	      VN_INFO (result)->needs_insertion = true;
! 	      /* And insert the conversion so we can find it later.  */
! 	      vn_unary_op_insert (val, result);
! 	      if (dump_file && (dump_flags & TDF_DETAILS))
! 		{
! 		  fprintf (dump_file, "Inserting name ");
! 		  print_generic_expr (dump_file, result, 0);
! 		  fprintf (dump_file, " for expression ");
! 		  print_generic_expr (dump_file, val, 0);
! 		  fprintf (dump_file, "\n");
! 		}
! 	    }
! 	}
        changed = set_ssa_val_to (lhs, result);
      }
    else
*************** free_scc_vn (void)
*** 2136,2141 ****
--- 2196,2204 ----
  	  && SSA_NAME_VALUE (name)
  	  && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
  	SSA_NAME_VALUE (name) = NULL;
+       if (name
+ 	  && VN_INFO (name)->needs_insertion)
+ 	release_ssa_name (name);
      }
    obstack_free (&vn_ssa_aux_obstack, NULL);
    VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
Index: trunk/gcc/tree-ssa-sccvn.h
===================================================================
*** trunk.orig/gcc/tree-ssa-sccvn.h	2008-03-01 19:51:04.000000000 +0100
--- trunk/gcc/tree-ssa-sccvn.h	2008-03-01 19:53:24.000000000 +0100
*************** typedef struct vn_ssa_aux
*** 44,49 ****
--- 44,53 ----
       once.  It cannot be used to avoid visitation for SSA_NAME's
       involved in non-singleton SCC's.  */
    unsigned use_processed : 1;
+ 
+   /* True, if this SSA_NAME doesn't have a defining statement.
+      Insertion of such with expr or replacement with expr is necessary.  */
+   unsigned needs_insertion : 1;
  } *vn_ssa_aux_t;
  
  /* Return the value numbering info for an SSA_NAME.  */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-7.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-7.c	2008-03-01 19:53:25.000000000 +0100
***************
*** 0 ****
--- 1,30 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre-details -fdump-tree-optimized" } */
+ 
+ struct X {
+   int i;
+   union {
+     int j;
+     int k;
+     float f;
+   } u;
+ };
+ 
+ int foo(int j)
+ {
+   struct X a;
+ 
+   a.u.j = j;
+   a.u.f = a.u.f;
+   a.u.f = a.u.f;
+   a.u.j = a.u.j;
+   a.u.f = a.u.f;
+   return a.u.k;
+ }
+ 
+ /* { dg-final { scan-tree-dump "Replaced a.u.f with VIEW_CONVERT_EXPR" "fre" } } */
+ /* { dg-final { scan-tree-dump "Replaced a.u.j with j" "fre" } } */
+ /* { dg-final { scan-tree-dump "Replaced a.u.k with j" "fre" } } */
+ /* { dg-final { scan-tree-dump "return j" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-8.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-8.c	2008-03-01 19:53:25.000000000 +0100
***************
*** 0 ****
--- 1,26 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre-details" } */
+ 
+ union U {
+   int i;
+   float f;
+ };
+ int foo(int i, int b)
+ {
+   union U u;
+   if (b)
+     {
+       i = i << 2;
+       u.i = i;
+       return u.f;
+     }
+   else
+     {
+       i = i << 2;
+       u.i = i;
+       return u.f;
+     }
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "Replaced u.f with VIEW_CONVERT_EXPR" 2 "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */