Teach sccvn about constant vars

Hi,
while analyzing the remianing problems with folding in gfortran testsuite I noticed
that there is actual bug in way fold_const_aggregate_ref handle folding of
array refs into STRING_CST because it ignores lower bound.
Testaces in testsuite are lucky that with ignoring lower bound we get out of
string and thus do not fold, but this should get into real wrong code bugs
if gfortran was not forgetting to set TREE_STATIC flags on initializers and thus
folding happent at all.

Fixed thus (by copying code from expr.c)

Honza

/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-optimized" } */
enum
{
  ERROR_OK, ERROR_UNKNOWN, 
  ERROR_NUM
};
enum
{ __LC_CTYPE = 0, __LC_NUMERIC = 1, __LC_TIME = 2, __LC_COLLATE =
    3, __LC_MONETARY = 4, __LC_MESSAGES = 5, __LC_ALL = 6, __LC_PAPER =
    10, __LC_MEASUREMENT = 11, __LC_IDENTIFICATION = 12 };
static const char *const _messages[] = {
  "no error", "unknown error", "Internal error: unknown reason",
};
elf_errmsg (int err)
{
  if (err < 0 || err >= ERROR_NUM || _messages[err] == ((void *) 0))
    {
      err = ERROR_UNKNOWN;
    }
  return _messages[err];
}

/* We should fold _messages[1].  */
/* { dg-final { scan-tree-dump "unknown error" "optimized"} } */
/* { dg-final { cleanup-tree-dump "optimized" } } */

On Sun, 5 Sep 2010, Jan Hubicka wrote:

> Hi,
> while analyzing the remianing problems with folding in gfortran testsuite I noticed
> that there is actual bug in way fold_const_aggregate_ref handle folding of
> array refs into STRING_CST because it ignores lower bound.
> Testaces in testsuite are lucky that with ignoring lower bound we get out of
> string and thus do not fold, but this should get into real wrong code bugs
> if gfortran was not forgetting to set TREE_STATIC flags on initializers and thus
> folding happent at all.
> 
> Fixed thus (by copying code from expr.c)

As said, please split out the lower-bound fix, we might want to backport
it.

More comments below.

> Honza
> 
> /* { dg-do compile } */
> /* { dg-options "-O2 -fdump-tree-optimized" } */
> enum
> {
>   ERROR_OK, ERROR_UNKNOWN, 
>   ERROR_NUM
> };
> enum
> { __LC_CTYPE = 0, __LC_NUMERIC = 1, __LC_TIME = 2, __LC_COLLATE =
>     3, __LC_MONETARY = 4, __LC_MESSAGES = 5, __LC_ALL = 6, __LC_PAPER =
>     10, __LC_MEASUREMENT = 11, __LC_IDENTIFICATION = 12 };
> static const char *const _messages[] = {
>   "no error", "unknown error", "Internal error: unknown reason",
> };
> elf_errmsg (int err)
> {
>   if (err < 0 || err >= ERROR_NUM || _messages[err] == ((void *) 0))
>     {
>       err = ERROR_UNKNOWN;
>     }
>   return _messages[err];
> }
> 
> /* We should fold _messages[1].  */
> /* { dg-final { scan-tree-dump "unknown error" "optimized"} } */
> /* { dg-final { cleanup-tree-dump "optimized" } } */
> 
> Index: tree-ssa-sccvn.c
> 	* gimple.h (fold_const_array_ref): Declare.
> 	* tree-ssa-sccvn.c (fully_constant_vn_reference_p): Fold initialized
> 	readonly static vars and array references into them.
> 	* tree-ssa-ccp.c (fold_const_array_ref): Break out from ...; fix handling
> 	of lower_bound.
> 	(fold_const_aggregate_ref): ... here.
> ===================================================================
> --- tree-ssa-sccvn.c	(revision 163862)
> +++ tree-ssa-sccvn.c	(working copy)
> @@ -1109,24 +1109,57 @@ fully_constant_vn_reference_p (vn_refere
>  	    return folded;
>  	}
>      }
> -
> -  /* Simplify reads from constant strings.  */
> +  else if (op->opcode == VAR_DECL
> +	   || op->opcode == CONST_DECL)
> +    return get_symbol_constant_value (op->op0);

This needs a check for is_gimple_min_invariant and an unshare_expr.

>    else if (op->opcode == ARRAY_REF
> -	   && TREE_CODE (op->op0) == INTEGER_CST
> -	   && integer_zerop (op->op1)
>  	   && VEC_length (vn_reference_op_s, operands) == 2)
>      {
>        vn_reference_op_t arg0;
> +      tree ctor = NULL_TREE;
> +      tree op0;
> +
>        arg0 = VEC_index (vn_reference_op_s, operands, 1);
> -      if (arg0->opcode == STRING_CST
> -	  && (TYPE_MODE (op->type)
> -	      == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0->op0))))
> -	  && GET_MODE_CLASS (TYPE_MODE (op->type)) == MODE_INT
> -	  && GET_MODE_SIZE (TYPE_MODE (op->type)) == 1
> -	  && compare_tree_int (op->op0, TREE_STRING_LENGTH (arg0->op0)) < 0)
> -	return build_int_cst_type (op->type,
> -				   (TREE_STRING_POINTER (arg0->op0)
> -				    [TREE_INT_CST_LOW (op->op0)]));
> +      op0 = arg0->op0;
> +
> +      switch (arg0->opcode)
> +	{
> +	case MEM_REF:
> +	  /* ???  We could handle this case.  */
> +	  if (!integer_zerop (TREE_OPERAND (op0, 1)))
> +	    return NULL_TREE;
> +	  op0 = get_base_address (op0);
> +	  if (!op0
> +	      || TREE_CODE (op0) != VAR_DECL)
> +	    return NULL_TREE;
> +
> +	  /* Fallthru.  */
> +	case VAR_DECL:
> +	  if (!TREE_READONLY (op0)
> +	      || TREE_CODE (TREE_TYPE (op0)) != ARRAY_TYPE
> +	      || ((TREE_STATIC (op0) || DECL_EXTERNAL (op0))
> +		  && !varpool_get_node (op0)->const_value_known))

well, also for !(TREE_STATIC (op0) || DECL_EXTERNAL (op0)), right?  Thus,

> +       if (!TREE_READONLY (op0)
> +           || TREE_CODE (TREE_TYPE (op0)) != ARRAY_TYPE  
              || !(TREE_STATIC (op0) || DECL_EXTERNAL (op0))
	      || !varpool_get_node (op0)->const_value_known)
> +	    return NULL_TREE;
> +
> +	  ctor = DECL_INITIAL (op0);
> +	  break;
> +
> +	case ARRAY_REF:
> +	case COMPONENT_REF:
> +	  gcc_unreachable ();

Please no unreachables here, the default case should simply
return NULL_TREE.

> +	  break;
> +
> +	case STRING_CST:
> +	case CONSTRUCTOR:
> +	  ctor = op0;
> +	  break;
> +
> +	default:

return NULL_TREE;

> +	  break;
> +	}
> +      gcc_assert (op->op1);

No need to assert that.

> +      if (ctor)
> +        return fold_const_array_ref (op->type, ctor, op->op0, op->op1);
>      }
>  
>    return NULL_TREE;
> Index: tree-ssa-ccp.c
> ===================================================================
> --- tree-ssa-ccp.c	(revision 163862)
> +++ tree-ssa-ccp.c	(working copy)
> @@ -1310,6 +1310,65 @@ ccp_fold (gimple stmt)
>      }
>  }
>  
> +/* Fold array reference of TYPE into a variable with known value CTOR
> +   with known index IDX.  */
> +tree
> +fold_const_array_ref (tree type, tree ctor, tree idx, tree low_bound)
> +{
> +  unsigned HOST_WIDE_INT cnt;
> +  tree cfield, cval;
> +  tree tem;
> +
> +  if (ctor == NULL_TREE
> +      || (TREE_CODE (ctor) != CONSTRUCTOR
> +	  && TREE_CODE (ctor) != STRING_CST)
> +      || !TREE_STATIC (ctor))
> +    return NULL_TREE;
> +
> +  /* Get the index.  If we have an SSA_NAME, try to resolve it
> +     with the current lattice value for the SSA_NAME.  */
> +  switch (TREE_CODE (idx))
> +    {
> +    case SSA_NAME:
> +      if ((tem = get_constant_value (idx))
> +	  && TREE_CODE (tem) == INTEGER_CST)
> +	idx = tem;
> +      else
> +	return NULL_TREE;
> +      break;
> +
> +    case INTEGER_CST:
> +      break;
> +
> +    default:
> +      return NULL_TREE;
> +    }
> +
> +  /* Fold read from constant string.  */
> +  if (TREE_CODE (ctor) == STRING_CST)
> +    {
> +      tree index = fold_convert (sizetype, idx);
> +      if (low_bound && !integer_zerop (low_bound))
> +	index = size_diffop (index, fold_convert (sizetype, low_bound));

Instead of playing games with size_diffop here please reject
non-INTEGER_CST low_bound early, do the arithmetic with
double-ints and ..

> +      if ((TYPE_MODE (type)
> +	   == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> +	  && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> +	      == MODE_INT)
> +	  && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
> +	  && compare_tree_int (index, TREE_STRING_LENGTH (ctor)) < 0)

.. the comparison here as well.  Avoids building trees and should
speed up things as well.

Otherwise the patch looks good.

Thanks,
Richard.

> +	return build_int_cst_type (type,
> +				   (TREE_STRING_POINTER (ctor)
> +				    [TREE_INT_CST_LOW (index)]));
> +      return NULL_TREE;
> +    }
> +
> +  /* Whoo-hoo!  I'll fold ya baby.  Yeah!  */
> +  FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
> +    if (tree_int_cst_equal (cfield, idx))
> +     return canonicalize_constructor_val (cval);
> +  return NULL_TREE;
> +}
> +
>  /* Return the tree representing the element referenced by T if T is an
>     ARRAY_REF or COMPONENT_REF into constant aggregates.  Return
>     NULL_TREE otherwise.  */
> @@ -1332,11 +1391,11 @@ fold_const_aggregate_ref (tree t)
>    switch (TREE_CODE (t))
>      {
>      case ARRAY_REF:
> +      base = TREE_OPERAND (t, 0);
>        /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
>  	 DECL_INITIAL.  If BASE is a nested reference into another
>  	 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
>  	 the inner reference.  */
> -      base = TREE_OPERAND (t, 0);
>        switch (TREE_CODE (base))
>  	{
>  	case MEM_REF:
> @@ -1373,51 +1432,10 @@ fold_const_aggregate_ref (tree t)
>  	  return NULL_TREE;
>  	}
>  
> -      if (ctor == NULL_TREE
> -	  || (TREE_CODE (ctor) != CONSTRUCTOR
> -	      && TREE_CODE (ctor) != STRING_CST)
> -	  || !TREE_STATIC (ctor))
> -	return NULL_TREE;
> -
> -      /* Get the index.  If we have an SSA_NAME, try to resolve it
> -	 with the current lattice value for the SSA_NAME.  */
> -      idx = TREE_OPERAND (t, 1);
> -      switch (TREE_CODE (idx))
> -	{
> -	case SSA_NAME:
> -	  if ((tem = get_constant_value (idx))
> -	      && TREE_CODE (tem) == INTEGER_CST)
> -	    idx = tem;
> -	  else
> -	    return NULL_TREE;
> -	  break;
> -
> -	case INTEGER_CST:
> -	  break;
> -
> -	default:
> -	  return NULL_TREE;
> -	}
> -
> -      /* Fold read from constant string.  */
> -      if (TREE_CODE (ctor) == STRING_CST)
> -	{
> -	  if ((TYPE_MODE (TREE_TYPE (t))
> -	       == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> -	      && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> -	          == MODE_INT)
> -	      && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
> -	      && compare_tree_int (idx, TREE_STRING_LENGTH (ctor)) < 0)
> -	    return build_int_cst_type (TREE_TYPE (t),
> -				       (TREE_STRING_POINTER (ctor)
> -					[TREE_INT_CST_LOW (idx)]));
> -	  return NULL_TREE;
> -	}
> -
> -      /* Whoo-hoo!  I'll fold ya baby.  Yeah!  */
> -      FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
> -	if (tree_int_cst_equal (cfield, idx))
> -	  return canonicalize_constructor_val (cval);
> +      return fold_const_array_ref (TREE_TYPE (t),
> +				   ctor,
> +				   TREE_OPERAND (t, 1),
> +				   array_ref_low_bound (t));
>        break;
>  
>      case COMPONENT_REF:
> 
>

> > -
> > -  /* Simplify reads from constant strings.  */
> > +  else if (op->opcode == VAR_DECL
> > +	   || op->opcode == CONST_DECL)
> > +    return get_symbol_constant_value (op->op0);
> 
> This needs a check for is_gimple_min_invariant and an unshare_expr.

get_symbol_constant_value is already testing is_gimple_min_invariant.
I guess if unshare_expr belong here, it would need to be around about
every get_symbol_constant_value use?

> > +	  if (!TREE_READONLY (op0)
> > +	      || TREE_CODE (TREE_TYPE (op0)) != ARRAY_TYPE
> > +	      || ((TREE_STATIC (op0) || DECL_EXTERNAL (op0))
> > +		  && !varpool_get_node (op0)->const_value_known))
> 
> well, also for !(TREE_STATIC (op0) || DECL_EXTERNAL (op0)), right?  Thus,

Hmm, yes.
Perhaps this can be simplified at gimple, because local vars are not readonly?
> 
> > +       if (!TREE_READONLY (op0)
> > +           || TREE_CODE (TREE_TYPE (op0)) != ARRAY_TYPE  
>               || !(TREE_STATIC (op0) || DECL_EXTERNAL (op0))
> 	      || !varpool_get_node (op0)->const_value_known)
> > +	    return NULL_TREE;
> > +
> > +	  ctor = DECL_INITIAL (op0);
> > +	  break;
> > +
> > +	case ARRAY_REF:
> > +	case COMPONENT_REF:
> > +	  gcc_unreachable ();
> 
> Please no unreachables here, the default case should simply
> return NULL_TREE.

I was basically interested if functio never need to recursive.  Just returning NULL_TREE
would result in missed optimization on nested references.
> > +  /* Fold read from constant string.  */
> > +  if (TREE_CODE (ctor) == STRING_CST)
> > +    {
> > +      tree index = fold_convert (sizetype, idx);
> > +      if (low_bound && !integer_zerop (low_bound))
> > +	index = size_diffop (index, fold_convert (sizetype, low_bound));
> 
> Instead of playing games with size_diffop here please reject
> non-INTEGER_CST low_bound early, do the arithmetic with
> double-ints and ..
> 
> > +      if ((TYPE_MODE (type)
> > +	   == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> > +	  && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> > +	      == MODE_INT)
> > +	  && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
> > +	  && compare_tree_int (index, TREE_STRING_LENGTH (ctor)) < 0)
> 
> .. the comparison here as well.  Avoids building trees and should
> speed up things as well.

Hmm, OK.  This is copied from code that appears in fold_constat_string_reference
and few other places.  I guess i will first break out the low bound check and update
all the uses to do double int.

Thanks,
Honza

On Mon, 6 Sep 2010, Jan Hubicka wrote:

> > > -
> > > -  /* Simplify reads from constant strings.  */
> > > +  else if (op->opcode == VAR_DECL
> > > +	   || op->opcode == CONST_DECL)
> > > +    return get_symbol_constant_value (op->op0);
> > 
> > This needs a check for is_gimple_min_invariant and an unshare_expr.
> 
> get_symbol_constant_value is already testing is_gimple_min_invariant.

Hm.  I thought this is an implementation detail of the uses, but
you are right.

> I guess if unshare_expr belong here, it would need to be around about
> every get_symbol_constant_value use?

Yes.  Or rather at the point the constants are put into a new use
in the IL (for CCP this is at substitution time).  It might be
that eliminate () already does the unsharing.

> > > +	  if (!TREE_READONLY (op0)
> > > +	      || TREE_CODE (TREE_TYPE (op0)) != ARRAY_TYPE
> > > +	      || ((TREE_STATIC (op0) || DECL_EXTERNAL (op0))
> > > +		  && !varpool_get_node (op0)->const_value_known))
> > 
> > well, also for !(TREE_STATIC (op0) || DECL_EXTERNAL (op0)), right?  Thus,
> 
> Hmm, yes.
> Perhaps this can be simplified at gimple, because local vars are not readonly?

What do you mean by simplified?

> > > +       if (!TREE_READONLY (op0)
> > > +           || TREE_CODE (TREE_TYPE (op0)) != ARRAY_TYPE  
> >               || !(TREE_STATIC (op0) || DECL_EXTERNAL (op0))
> > 	      || !varpool_get_node (op0)->const_value_known)
> > > +	    return NULL_TREE;
> > > +
> > > +	  ctor = DECL_INITIAL (op0);
> > > +	  break;
> > > +
> > > +	case ARRAY_REF:
> > > +	case COMPONENT_REF:
> > > +	  gcc_unreachable ();
> > 
> > Please no unreachables here, the default case should simply
> > return NULL_TREE.
> 
> I was basically interested if functio never need to recursive.  Just returning NULL_TREE
> would result in missed optimization on nested references.

But we don't want to crash.  Maybe for your debugging, but not in
the final patch.

> > > +  /* Fold read from constant string.  */
> > > +  if (TREE_CODE (ctor) == STRING_CST)
> > > +    {
> > > +      tree index = fold_convert (sizetype, idx);
> > > +      if (low_bound && !integer_zerop (low_bound))
> > > +	index = size_diffop (index, fold_convert (sizetype, low_bound));
> > 
> > Instead of playing games with size_diffop here please reject
> > non-INTEGER_CST low_bound early, do the arithmetic with
> > double-ints and ..
> > 
> > > +      if ((TYPE_MODE (type)
> > > +	   == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> > > +	  && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
> > > +	      == MODE_INT)
> > > +	  && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
> > > +	  && compare_tree_int (index, TREE_STRING_LENGTH (ctor)) < 0)
> > 
> > .. the comparison here as well.  Avoids building trees and should
> > speed up things as well.
> 
> Hmm, OK.  This is copied from code that appears in fold_constat_string_reference
> and few other places.  I guess i will first break out the low bound check and update
> all the uses to do double int.

Thx.

Richard.