This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: get_ref_base_and_extend based ctor folding
Hi,
this is my best attempt to make fold_ctor_reference not scary.
It breaks up implementation into fold_string_cst_ctor_reference,
fold_array_ctor_reference, and fold_nonarray_ctor_reference
and I've addressed the comments (i.e. reorganized array folding
to first compute index and compare with it and introduced more
comments and temporaries in aggregate folding).
I also removed most of strange view convert logic - now we either
need types to match in the sense of useless_type_conversion_p
or we need to see scalar and try to introduce view_convert_expr.
Later we can add more fun via reinterpretting natural expr
or by teaching fold_string_cst_ctor_reference to play view_convert_expr
games, but it is not important.
Finally i got rid compares with size of access type to cure bitfields.
Instead when looking into arrays or structures, I compare with element
size (or field_decl_size) to see if field is large enough to cover whole
access.
I did not ruled out bitfields since whole code has no special code for
them now, but I defnitly can and update testcase if it makes things safer
too. I regtested with that variant too and it passes as well.
Bootstrapped/regtested x86_64-linux, OK?
Honza
/* { dg-do compile } */
/* { dg-options "-O -fdump-tree-ccp1" } */
static const char a[5]="t";
static const int b[5]={1,2};
static const struct a {int a : 6; int b : 6;} c = {5,9};
test()
{
return a[2]+b[1]+b[3]+c.b;
}
/* { dg-final { scan-tree-dump "return 11;" "ccp1" } } */
/* { dg-final { cleanup-tree-dump "ccp1" } } */
* tree-ssa-ccp.c (fold_ctor_reference): New function.
(fold_string_cst_ctor_reference, fold_array_ctor_reference,
fold_nonarray_ctor_reference): New functions.
(fold_const_aggregate_ref): Use it.
Index: tree-ssa-ccp.c
===================================================================
*** tree-ssa-ccp.c (revision 164617)
--- tree-ssa-ccp.c (working copy)
*************** static prop_value_t *const_val;
*** 168,173 ****
--- 168,176 ----
static void canonicalize_float_value (prop_value_t *);
static bool ccp_fold_stmt (gimple_stmt_iterator *);
+ static tree fold_ctor_reference (tree type, tree ctor,
+ unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size);
/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
*************** get_base_constructor (tree base, tree *o
*** 1369,1374 ****
--- 1372,1592 ----
}
}
+ /* CTOR is STRING_CST. Fold reference of type TYPE and size SIZE
+ to the memory at bit OFFSET.
+
+ We do only simple job of folding byte accesses. */
+
+ static tree
+ fold_string_cst_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+ {
+ if (INTEGRAL_TYPE_P (type)
+ && (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
+ && size == BITS_PER_UNIT
+ && !(offset % BITS_PER_UNIT))
+ {
+ offset /= BITS_PER_UNIT;
+ if (offset < (unsigned HOST_WIDE_INT) TREE_STRING_LENGTH (ctor))
+ return build_int_cst_type (type, (TREE_STRING_POINTER (ctor)
+ [offset]));
+ /* Folding
+ const char a[20]="hello";
+ return a[10];
+
+ might lead to offset greater than string length. In this case we
+ know value is either initialized to 0 or out of bounds. Return 0
+ in both cases. */
+ return build_zero_cst (type);
+ }
+ return NULL_TREE;
+ }
+
+ /* CTOR is CONSTRUCTOR of an array type. Fold reference of type TYPE and size
+ SIZE to the memory at bit OFFSET. */
+
+ static tree
+ fold_array_ctor_reference (tree type, tree ctor,
+ unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+ {
+ unsigned HOST_WIDE_INT cnt;
+ tree cfield, cval;
+ double_int low_bound, elt_size;
+ double_int index, max_index;
+ double_int access_index;
+ tree domain_type = TYPE_DOMAIN (TREE_TYPE (ctor));
+ HOST_WIDE_INT inner_offset;
+
+ /* Compute low bound and elt size. */
+ if (domain_type && TYPE_MIN_VALUE (domain_type))
+ {
+ /* Static constructors for variably sized objects makes no sense. */
+ gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
+ low_bound = tree_to_double_int (TYPE_MIN_VALUE (domain_type));
+ }
+ else
+ low_bound = double_int_zero;
+ /* Static constructors for variably sized objects makes no sense. */
+ gcc_assert (TREE_CODE(TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))))
+ == INTEGER_CST);
+ elt_size =
+ tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))));
+
+ /* We can handle only constantly sized accesses that are known to not
+ be larger than size of array element. */
+ if (!TYPE_SIZE_UNIT (type)
+ || TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST
+ || double_int_cmp (elt_size,
+ tree_to_double_int (TYPE_SIZE_UNIT (type)), 0) < 0)
+ return NULL_TREE;
+
+ /* Compute the array index we look for. */
+ access_index = double_int_udiv (uhwi_to_double_int (offset / BITS_PER_UNIT),
+ elt_size, TRUNC_DIV_EXPR);
+ access_index = double_int_sub (access_index, low_bound);
+
+ /* And offset within the access. */
+ inner_offset = offset % (double_int_to_uhwi (elt_size) * BITS_PER_UNIT);
+
+ /* See if the array field is large enough to span whole access. We do not
+ care to fold accesses spanning multiple array indexes. */
+ if (inner_offset + size > double_int_to_uhwi (elt_size) * BITS_PER_UNIT)
+ return NULL_TREE;
+
+ index = double_int_sub (low_bound, double_int_one);
+ FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
+ {
+ /* Array constructor might explicitely set index, or specify range
+ or leave index NULL meaning that it is next index after previous
+ one. */
+ if (cfield)
+ {
+ if (TREE_CODE (cfield) == INTEGER_CST)
+ max_index = index = tree_to_double_int (cfield);
+ else
+ {
+ gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
+ index = tree_to_double_int (TREE_OPERAND (cfield, 0));
+ max_index = tree_to_double_int (TREE_OPERAND (cfield, 1));
+ }
+ }
+ else
+ max_index = index = double_int_add (index, double_int_one);
+
+ /* Do we have match? */
+ if (double_int_cmp (access_index, index, 1) >= 0
+ && double_int_cmp (access_index, max_index, 1) <= 0)
+ return fold_ctor_reference (type, cval, inner_offset, size);
+ }
+ /* When memory is not explicitely mentioned in constructor,
+ it is 0 (or out of range). */
+ return build_zero_cst (type);
+ }
+
+ /* CTOR is CONSTRUCTOR of an aggregate or vector.
+ Fold reference of type TYPE and size SIZE to the memory at bit OFFSET. */
+
+ static tree
+ fold_nonarray_ctor_reference (tree type, tree ctor,
+ unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+ {
+ unsigned HOST_WIDE_INT cnt;
+ tree cfield, cval;
+
+ FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield,
+ cval)
+ {
+ tree byte_offset = DECL_FIELD_OFFSET (cfield);
+ tree field_offset = DECL_FIELD_BIT_OFFSET (cfield);
+ tree field_size = DECL_SIZE (cfield);
+ double_int bitoffset;
+ double_int byte_offset_cst = tree_to_double_int (byte_offset);
+ double_int bits_per_unit_cst = uhwi_to_double_int (BITS_PER_UNIT);
+ double_int bitoffset_end;
+
+ /* Variable sized objects in static constructors makes no sense. */
+ gcc_assert (TREE_CODE (field_offset) == INTEGER_CST
+ && TREE_CODE (byte_offset) == INTEGER_CST
+ && TREE_CODE (field_size) == INTEGER_CST);
+
+ /* Compute bit offset of the field. */
+ bitoffset = double_int_add (tree_to_double_int (field_offset),
+ double_int_mul (byte_offset_cst,
+ bits_per_unit_cst));
+ /* Compute bit offset where the field ends. */
+ bitoffset_end = double_int_add (bitoffset,
+ tree_to_double_int (field_size));
+
+ /* Is OFFSET in the range (BITOFFSET, BITOFFSET_END)? */
+ if (double_int_cmp (uhwi_to_double_int (offset), bitoffset, 0) >= 0
+ && double_int_cmp (uhwi_to_double_int (offset),
+ bitoffset_end, 0) < 0)
+ {
+ double_int access_end = double_int_add (uhwi_to_double_int (offset),
+ uhwi_to_double_int (size));
+ double_int inner_offset = double_int_sub (uhwi_to_double_int (offset),
+ bitoffset);
+ /* We do have overlap. Now see if field is large enough to
+ cover the access. Give up for accesses spanning multiple
+ fields. */
+ if (double_int_cmp (access_end, bitoffset_end, 0) > 0)
+ return NULL_TREE;
+ return fold_ctor_reference (type, cval,
+ double_int_to_uhwi (inner_offset), size);
+ }
+ }
+ /* When memory is not explicitely mentioned in constructor, it is 0. */
+ return build_zero_cst (type);
+ }
+
+ /* CTOR is value initializing memory, fold reference of type TYPE and size SIZE
+ to the memory at bit OFFSET. */
+
+ static tree
+ fold_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+ {
+ tree ret;
+
+ /* We found the field with exact match. */
+ if (useless_type_conversion_p (type, TREE_TYPE (ctor))
+ && !offset)
+ return canonicalize_constructor_val (ctor);
+
+ /* If we are seeing scalar, we are at the end of recursive walk.
+ See if we can view convert the result. */
+ if (!AGGREGATE_TYPE_P (TREE_TYPE (ctor)) && !offset
+ /* VIEW_CONVERT_EXPR is defined only for matching sizes. */
+ && operand_equal_p (TYPE_SIZE (type),
+ TYPE_SIZE (TREE_TYPE (ctor)), 0))
+ {
+ ret = canonicalize_constructor_val (ctor);
+ ret = fold_unary (VIEW_CONVERT_EXPR, type, ret);
+ if (ret)
+ STRIP_NOPS (ret);
+ return ret;
+ }
+
+ /* Fold accesses into aggregate constructors recursively. */
+ if (TREE_CODE (ctor) == STRING_CST)
+ return fold_string_cst_ctor_reference (type, ctor, offset, size);
+ if (TREE_CODE (ctor) == CONSTRUCTOR)
+ {
+ if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE)
+ return fold_array_ctor_reference (type, ctor, offset, size);
+ else
+ return fold_nonarray_ctor_reference (type, ctor, offset, size);
+ }
+
+ 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. */
*************** get_base_constructor (tree base, tree *o
*** 1376,1385 ****
tree
fold_const_aggregate_ref (tree t)
{
! tree ctor, idx, field;
! unsigned HOST_WIDE_INT cnt;
! tree cfield, cval;
tree tem;
if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
return get_symbol_constant_value (t);
--- 1594,1603 ----
tree
fold_const_aggregate_ref (tree t)
{
! tree ctor, idx, base;
! HOST_WIDE_INT offset, size, max_size;
tree tem;
+ tree ctr_offset;
if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
return get_symbol_constant_value (t);
*************** fold_const_aggregate_ref (tree t)
*** 1391,1489 ****
switch (TREE_CODE (t))
{
case ARRAY_REF:
! ctor = get_base_constructor (TREE_OPERAND (t, 0), &idx);
! if (idx)
! return NULL_TREE;
if (ctor == error_mark_node)
return build_zero_cst (TREE_TYPE (t));
! if (ctor == NULL_TREE
! || (TREE_CODE (ctor) != CONSTRUCTOR
! && TREE_CODE (ctor) != STRING_CST))
! 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)
! {
! tree low_bound = array_ref_low_bound (t);
! double_int low_bound_cst;
! double_int index_cst;
! double_int length_cst;
! bool signed_p = TYPE_UNSIGNED (TREE_TYPE (idx));
!
! if (TREE_CODE (idx) != INTEGER_CST
! || !INTEGRAL_TYPE_P (TREE_TYPE (t))
! || TREE_CODE (low_bound) != INTEGER_CST)
! return NULL_TREE;
! low_bound_cst = tree_to_double_int (low_bound);
! index_cst = tree_to_double_int (idx);
! length_cst = uhwi_to_double_int (TREE_STRING_LENGTH (ctor));
! index_cst = double_int_sub (index_cst, low_bound_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
! && double_int_cmp (index_cst, length_cst, signed_p) < 0)
! return build_int_cst_type (TREE_TYPE (t),
! (TREE_STRING_POINTER (ctor)
! [double_int_to_uhwi (index_cst)]));
! 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);
! break;
!
! case COMPONENT_REF:
! /* 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. */
! ctor = get_base_constructor (TREE_OPERAND (t, 0), &idx);
!
! if (idx)
return NULL_TREE;
!
! if (ctor == error_mark_node)
! return build_zero_cst (TREE_TYPE (t));
!
! if (ctor == NULL_TREE
! || TREE_CODE (ctor) != CONSTRUCTOR)
return NULL_TREE;
! field = TREE_OPERAND (t, 1);
!
! FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
! if (cfield == field
! /* FIXME: Handle bit-fields. */
! && ! DECL_BIT_FIELD (cfield))
! return canonicalize_constructor_val (cval);
! break;
case REALPART_EXPR:
case IMAGPART_EXPR:
--- 1609,1689 ----
switch (TREE_CODE (t))
{
case ARRAY_REF:
! case ARRAY_RANGE_REF:
! /* Constant indexes are handled well by get_base_constructor.
! Only special case variable offsets.
! FIXME: This code can't handle nested references with variable indexes
! (they will be handled only by iteration of ccp). Perhaps we can bring
! get_ref_base_and_extent here and make it use get_constant_value. */
! if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME
! && (idx = get_constant_value (TREE_OPERAND (t, 1)))
! && host_integerp (idx, 0))
! {
! tree low_bound, unit_size;
! /* If the resulting bit-offset is constant, track it. */
! if ((low_bound = array_ref_low_bound (t),
! host_integerp (low_bound, 0))
! && (unit_size = array_ref_element_size (t),
! host_integerp (unit_size, 1)))
! {
! offset = TREE_INT_CST_LOW (idx);
! offset -= TREE_INT_CST_LOW (low_bound);
! offset *= TREE_INT_CST_LOW (unit_size);
! offset *= BITS_PER_UNIT;
!
! base = TREE_OPERAND (t, 0);
! ctor = get_base_constructor (base, &ctr_offset);
! if (ctr_offset)
! {
! if (!host_integerp (ctr_offset, 1))
! return NULL_TREE;
! offset += TREE_INT_CST_LOW (ctr_offset) * BITS_PER_UNIT;
! }
! /* Empty constructor. Always fold to 0. */
! if (ctor == error_mark_node)
! return build_zero_cst (TREE_TYPE (t));
! /* Out of bound array access. Value is undefined, but don't fold. */
! if (offset < 0)
! return NULL_TREE;
! /* We can not determine ctor. */
! if (!ctor)
! return NULL_TREE;
! return fold_ctor_reference (TREE_TYPE (t), ctor, offset,
! TREE_INT_CST_LOW (unit_size)
! * BITS_PER_UNIT);
! }
! }
! /* Fallthru. */
!
! case COMPONENT_REF:
! case BIT_FIELD_REF:
! case TARGET_MEM_REF:
! case MEM_REF:
! base = get_ref_base_and_extent (t, &offset, &size, &max_size);
! ctor = get_base_constructor (base, &ctr_offset);
+ /* Empty constructor. Always fold to 0. */
if (ctor == error_mark_node)
return build_zero_cst (TREE_TYPE (t));
! if (ctr_offset)
{
! if (!host_integerp (ctr_offset, 1))
return NULL_TREE;
! offset += TREE_INT_CST_LOW (ctr_offset) * BITS_PER_UNIT;
}
! /* Out of bound array access. Value is undefined, but don't fold. */
! if (offset < 0)
return NULL_TREE;
! /* We can not determine ctor. */
! if (!ctor)
! return NULL_TREE;
! /* We do not know precise address. */
! if (max_size != size)
return NULL_TREE;
! return fold_ctor_reference (TREE_TYPE (t), ctor, offset, size);
case REALPART_EXPR:
case IMAGPART_EXPR:
*************** fold_const_aggregate_ref (tree t)
*** 1495,1567 ****
break;
}
- case MEM_REF:
- ctor = get_base_constructor (t, &idx);
-
- if (ctor == error_mark_node)
- return build_zero_cst (TREE_TYPE (t));
-
- if (ctor && !AGGREGATE_TYPE_P (TREE_TYPE (ctor))
- && !idx)
- {
- if (ctor
- && !useless_type_conversion_p
- (TREE_TYPE (t), TREE_TYPE (ctor)))
- ctor = fold_unary (VIEW_CONVERT_EXPR, TREE_TYPE (t), ctor);
- return ctor;
- }
-
- if (!idx)
- idx = integer_zero_node;
-
- if (ctor == NULL_TREE
- || (TREE_CODE (ctor) != CONSTRUCTOR
- && TREE_CODE (ctor) != STRING_CST))
- return NULL_TREE;
-
- /* Fold read from constant string. */
- if (TREE_CODE (ctor) == STRING_CST)
- {
- if (INTEGRAL_TYPE_P (TREE_TYPE (t))
- && (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;
- }
-
- /* ??? Implement byte-offset indexing into a non-array CONSTRUCTOR. */
- if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE
- && (TYPE_MODE (TREE_TYPE (t))
- == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
- && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (t))) != 0
- && integer_zerop
- (int_const_binop
- (TRUNC_MOD_EXPR, idx,
- size_int (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (t)))), 0)))
- {
- idx = int_const_binop (TRUNC_DIV_EXPR, idx,
- size_int (GET_MODE_SIZE
- (TYPE_MODE (TREE_TYPE (t)))), 0);
- FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
- if (tree_int_cst_equal (cfield, idx))
- {
- cval = canonicalize_constructor_val (cval);
- if (useless_type_conversion_p (TREE_TYPE (t), TREE_TYPE (cval)))
- return cval;
- else if (CONSTANT_CLASS_P (cval))
- return fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (t), cval);
- else
- return NULL_TREE;
- }
- }
- break;
-
default:
break;
}
--- 1695,1700 ----