[PATCH] More CCP, "fix" type-system

[Richard Guenther <rguenther at suse dot de>]

This patch teaches CCP to do better propagation of constant addresses
and thus do the same work that forwprop does here (but with a proper
algorithm).  The fact to note is that CCP only should care about the
value of a constant, not its type (for integral constants the constants
get "fixed" during propagation through conversions, for invariant
addresses this obviously doesn't happen).  So for

 int i;
 char *c = (char *)&i;
 return *(int *)c;

(char *)&i is still a constant as far as CCP is concerned and we would
like a constant c be presented to the substitution phase of the
propagation.  Note that the propagation itself makes sure that the
propagation is allowed type-wise (it uses may_propagate_copy, which
also checks for other stuff).

Fixing that you will still see const vs. non-const pointers not
propagated where you think they should (and in fact the tree forwprop
code contains code to circumvent the type-system checks here).
It looks like at the time we designed the type-system we were matching
its behavior more with the C input language than with the middle-end
semantics (which is what really matters for the middle-end type-system).
Fact is that the middle-end does not (and cannot) care about the constant
qualifier as far as pointer targets are concerned, but it is the frontends
job to ensure only valid (at compile-time) programs come through.

Thus, the (imho uncontroversical) proposal is to just ignore differences
in the const qualification of pointers in useless_type_conversion_p.
This allows to get rid of the hack in tree forwprop and exposes more
propagation possibilities to CCP (without introducing the same hack 
there).

Of course there is some fallout in the case where the 
useless_type_conversion_p predicate doesn't agree with what the folders
can handle.  This happens if we have inconsistent types in the IL
which in turn happens with IMA (see PR34989).  Instead of trying to
deal with this by not propagating we simply can force the folding
that is refused (after all the propagation was believed to be correct
for a reason) in fold_stmt.

Bootstrapped and tested on x86_64-unknown-linux-gnu, I'll apply this
later.

(If you are curious, all these patches cure some missed optimizations
if you start shuffling around or deleting passes)

Thanks,
Richard.

2008-03-19  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-forwprop.c (forward_propagate_addr_expr_1): Remove
	special casing of constant qualifiers.
	* tree-ssa.c (useless_type_conversion_p_1): Instead do not
	care about them in general.
	* tree-ssa-ccp.c (ccp_fold): Addresses are constant or not
	regardless of their type.
	(fold_stmt_r): Forcefully fold *& if we end up with that.

	* gcc.dg/tree-ssa/ssa-ccp-17.c: New testcase.

Index: tree-ssa-forwprop.c
===================================================================
*** tree-ssa-forwprop.c	(revision 133342)
--- tree-ssa-forwprop.c	(working copy)
*************** forward_propagate_addr_expr_1 (tree name
*** 601,614 ****
       propagate the ADDR_EXPR into the use of NAME and fold the result.  */
    if (TREE_CODE (lhs) == INDIRECT_REF
        && TREE_OPERAND (lhs, 0) == name
!       /* This will not allow stripping const qualification from
! 	 pointers which we want to allow specifically here to clean up
! 	 the IL for initialization of constant objects.   */
!       && (useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (lhs, 0)),
! 				     TREE_TYPE (def_rhs))
! 	  /* So explicitly check for this here.  */
! 	  || (TYPE_QUALS (TREE_TYPE (TREE_TYPE (TREE_OPERAND (lhs, 0))))
! 	      ^ TYPE_QUALS (TREE_TYPE (TREE_TYPE (def_rhs)))) == TYPE_QUAL_CONST)
        /* ???  This looks redundant, but is required for bogus types
  	 that can sometimes occur.  */
        && useless_type_conversion_p (TREE_TYPE (lhs),
--- 601,608 ----
       propagate the ADDR_EXPR into the use of NAME and fold the result.  */
    if (TREE_CODE (lhs) == INDIRECT_REF
        && TREE_OPERAND (lhs, 0) == name
!       && useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (lhs, 0)),
! 				    TREE_TYPE (def_rhs))
        /* ???  This looks redundant, but is required for bogus types
  	 that can sometimes occur.  */
        && useless_type_conversion_p (TREE_TYPE (lhs),
*************** forward_propagate_addr_expr_1 (tree name
*** 635,647 ****
       propagate the ADDR_EXPR into the use of NAME and fold the result.  */
    if (TREE_CODE (rhs) == INDIRECT_REF
        && TREE_OPERAND (rhs, 0) == name
!       /* ???  This doesn't allow stripping const qualification to
! 	 streamline the IL for reads from non-constant objects.  */
!       && (useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (rhs, 0)),
! 				     TREE_TYPE (def_rhs))
! 	  /* So explicitly check for this here.  */
! 	  || (TYPE_QUALS (TREE_TYPE (TREE_TYPE (TREE_OPERAND (rhs, 0))))
! 	      ^ TYPE_QUALS (TREE_TYPE (TREE_TYPE (def_rhs)))) == TYPE_QUAL_CONST)
        && useless_type_conversion_p (TREE_TYPE (rhs),
  				    TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
      {
--- 629,638 ----
       propagate the ADDR_EXPR into the use of NAME and fold the result.  */
    if (TREE_CODE (rhs) == INDIRECT_REF
        && TREE_OPERAND (rhs, 0) == name
!       && useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (rhs, 0)),
! 				    TREE_TYPE (def_rhs))
!       /* ???  This looks redundant, but is required for bogus types
! 	 that can sometimes occur.  */
        && useless_type_conversion_p (TREE_TYPE (rhs),
  				    TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
      {
Index: tree-ssa.c
===================================================================
*** tree-ssa.c	(revision 133342)
--- tree-ssa.c	(working copy)
*************** useless_type_conversion_p_1 (tree outer_
*** 1117,1128 ****
  	      != get_alias_set (TREE_TYPE (outer_type))))
  	return false;
  
!       /* Do not lose casts from const qualified to non-const
! 	 qualified.  */
!       if ((TYPE_READONLY (TREE_TYPE (outer_type))
! 	   != TYPE_READONLY (TREE_TYPE (inner_type)))
! 	  && TYPE_READONLY (TREE_TYPE (inner_type)))
! 	return false;
  
        /* Do not lose casts to restrict qualified pointers.  */
        if ((TYPE_RESTRICT (outer_type)
--- 1117,1124 ----
  	      != get_alias_set (TREE_TYPE (outer_type))))
  	return false;
  
!       /* We do not care for const qualification of the pointed-to types
! 	 as const qualification has no semantic value to the middle-end.  */
  
        /* Do not lose casts to restrict qualified pointers.  */
        if ((TYPE_RESTRICT (outer_type)
Index: testsuite/gcc.dg/tree-ssa/ssa-ccp-17.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/ssa-ccp-17.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/ssa-ccp-17.c	(revision 0)
***************
*** 0 ****
--- 1,32 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-ccp1" } */
+ 
+ int foo(void)
+ {
+   int i = 0;
+   char *p = (char *)&i;
+   return *(int *)p;
+ }
+ 
+ struct Foo {
+   int i;
+ } f;
+ 
+ int bar(void)
+ {
+   char *p = (char *)&f;
+   return ((struct Foo *)p)->i;
+ }
+ 
+ const struct Foo g;
+ 
+ int foobar(void)
+ {
+   struct Foo *p = (struct Foo *)&g;
+   return ((const struct Foo *)p)->i;
+ }
+ 
+ /* { dg-final { scan-tree-dump "= i;" "ccp1" } } */
+ /* { dg-final { scan-tree-dump "= f.i;" "ccp1" } } */
+ /* { dg-final { scan-tree-dump "= g.i;" "ccp1" } } */
+ /* { dg-final { cleanup-tree-dump "ccp1" } } */
Index: tree-ssa-ccp.c
===================================================================
*** tree-ssa-ccp.c	(revision 133342)
--- tree-ssa-ccp.c	(working copy)
*************** ccp_fold (tree stmt)
*** 947,954 ****
  	    op0 = get_value (op0)->value;
  	}
  
        if ((code == NOP_EXPR || code == CONVERT_EXPR)
! 	  && useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (op0)))
  	return op0;
        return fold_unary (code, TREE_TYPE (rhs), op0);
      }
--- 947,961 ----
  	    op0 = get_value (op0)->value;
  	}
  
+       /* Conversions are useless for CCP purposes if they are
+ 	 value-preserving.  Thus the restrictions that
+ 	 useless_type_conversion_p places for pointer type conversions do
+ 	 not apply here.  Substitution later will only substitute to
+ 	 allowed places.  */
        if ((code == NOP_EXPR || code == CONVERT_EXPR)
! 	  && ((POINTER_TYPE_P (TREE_TYPE (rhs))
! 	       && POINTER_TYPE_P (TREE_TYPE (op0)))
! 	      || useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (op0))))
  	return op0;
        return fold_unary (code, TREE_TYPE (rhs), op0);
      }
*************** fold_stmt_r (tree *expr_p, int *walk_sub
*** 2160,2165 ****
--- 2167,2177 ----
  
        t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0),
  				    integer_zero_node);
+       if (!t
+ 	  && TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR)
+ 	/* If we had a good reason for propagating the address here,
+ 	   make sure we end up with valid gimple.  See PR34989.  */
+ 	t = TREE_OPERAND (TREE_OPERAND (expr, 0), 0);
        break;
  
      case NOP_EXPR: