Loop bound computation uses undefined behavior when accessing arrays
outside of their domain. Unfortunately while it tries to honor
issues with trailing arrays in allocated storage its implementation
is broken (for one, it does consider a TYPE_DECL after the array
as a sign that the array is not at struct end). The following patch
moves array_at_struct_end_p to expr.c near its natural user
(it's also used by graphite) and re-implements it. It also adjusts
array_ref_up_bound to not return any bound in the case of an
access to a trailing array - at present what it returns is a
conservative answer in the wrong sense in two of its four callers
(it returns a lower bound for the upper bound). Given the fact
that array_ref_low_bound returns an exact answer not returning
any lower / upper bound for the upper bound but only what we would
consider exact sounds like the most reasonable solution.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
This does not yet fully recover bootstrap if you make use of
undefined behavior loop bound detection in VRP, but two miscompiles
of GCC vanish.
Richard.
2012-04-17 Richard Guenther <rguent...@suse.de>
* tree-flow.h (array_at_struct_end_p): Move declaration ...
* tree.h (array_at_struct_end_p): ... here.
* tree-ssa-loop-niter.c (idx_infer_loop_bounds): Infer nothing
from array references at struct ends.
(array_at_struct_end_p): Move ...
* expr.c (array_at_struct_end_p): ... here. Rewrite.
(array_ref_up_bound): Return NULL_TREE for array references
at struct ends.
Index: gcc/tree.h
===================================================================
*** gcc/tree.h (revision 186496)
--- gcc/tree.h (working copy)
*************** extern bool contains_packed_reference (c
*** 5068,5073 ****
--- 5068,5075 ----
extern tree array_ref_element_size (tree);
+ bool array_at_struct_end_p (tree);
+
/* Return a tree representing the lower bound of the array mentioned in
EXP, an ARRAY_REF or an ARRAY_RANGE_REF. */
Index: gcc/expr.c
===================================================================
*** gcc/expr.c (revision 186496)
--- gcc/expr.c (working copy)
*************** array_ref_low_bound (tree exp)
*** 6778,6783 ****
--- 6778,6820 ----
return build_int_cst (TREE_TYPE (TREE_OPERAND (exp, 1)), 0);
}
+ /* Returns true if REF is an array reference to an array at the end of
+ a structure. If this is the case, the array may be allocated larger
+ than its upper bound implies. */
+
+ bool
+ array_at_struct_end_p (tree ref)
+ {
+ if (TREE_CODE (ref) != ARRAY_REF
+ && TREE_CODE (ref) != ARRAY_RANGE_REF)
+ return false;
+
+ while (handled_component_p (ref))
+ {
+ /* If the reference chain contains a component reference to a
+ non-union type and there follows another field the reference
+ is not at the end of a structure. */
+ if (TREE_CODE (ref) == COMPONENT_REF
+ && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
+ {
+ tree nextf = DECL_CHAIN (TREE_OPERAND (ref, 1));
+ while (nextf && TREE_CODE (nextf) != FIELD_DECL)
+ nextf = DECL_CHAIN (nextf);
+ if (nextf)
+ return false;
+ }
+
+ ref = TREE_OPERAND (ref, 0);
+ }
+
+ /* If the reference is based on a declared entity, the size of the array
+ is constrained by its given domain. */
+ if (DECL_P (ref))
+ return false;
+
+ return true;
+ }
+
/* Return a tree representing the upper bound of the array mentioned in
EXP, an ARRAY_REF or an ARRAY_RANGE_REF. */
*************** array_ref_up_bound (tree exp)
*** 6789,6795 ****
/* If there is a domain type and it has an upper bound, use it, substituting
for a PLACEHOLDER_EXPR as needed. */
if (domain_type && TYPE_MAX_VALUE (domain_type))
! return SUBSTITUTE_PLACEHOLDER_IN_EXPR (TYPE_MAX_VALUE (domain_type), exp);
/* Otherwise fail. */
return NULL_TREE;
--- 6826,6843 ----
/* If there is a domain type and it has an upper bound, use it, substituting
for a PLACEHOLDER_EXPR as needed. */
if (domain_type && TYPE_MAX_VALUE (domain_type))
! {
! tree max = TYPE_MAX_VALUE (domain_type);
!
! /* For references to arrays at the end of dynamically allocated
! structures TYPE_MAX_VALUE is not an upper bound for the array
! size. */
! if (TREE_CODE (max) == INTEGER_CST
! && array_at_struct_end_p (exp))
! return NULL_TREE;
!
! return SUBSTITUTE_PLACEHOLDER_IN_EXPR (max, exp);
! }
/* Otherwise fail. */
return NULL_TREE;
Index: gcc/tree-flow.h
===================================================================
*** gcc/tree-flow.h (revision 186496)
--- gcc/tree-flow.h (working copy)
*************** tree find_loop_niter (struct loop *, edg
*** 686,692 ****
tree loop_niter_by_eval (struct loop *, edge);
tree find_loop_niter_by_eval (struct loop *, edge *);
void estimate_numbers_of_iterations (bool);
- bool array_at_struct_end_p (tree);
bool scev_probably_wraps_p (tree, tree, gimple, struct loop *, bool);
bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple, bool);
--- 686,691 ----
Index: gcc/tree-ssa-loop-niter.c
===================================================================
*** gcc/tree-ssa-loop-niter.c (revision 186496)
--- gcc/tree-ssa-loop-niter.c (working copy)
*************** record_nonwrapping_iv (struct loop *loop
*** 2640,2686 ****
record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
}
- /* Returns true if REF is a reference to an array at the end of a dynamically
- allocated structure. If this is the case, the array may be allocated
larger
- than its upper bound implies. */
-
- bool
- array_at_struct_end_p (tree ref)
- {
- tree base = get_base_address (ref);
- tree parent, field;
-
- /* Unless the reference is through a pointer, the size of the array matches
- its declaration. */
- if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF))
- return false;
-
- for (;handled_component_p (ref); ref = parent)
- {
- parent = TREE_OPERAND (ref, 0);
-
- if (TREE_CODE (ref) == COMPONENT_REF)
- {
- /* All fields of a union are at its end. */
- if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
- continue;
-
- /* Unless the field is at the end of the struct, we are done. */
- field = TREE_OPERAND (ref, 1);
- if (DECL_CHAIN (field))
- return false;
- }
-
- /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
- In all these cases, we might be accessing the last element, and
- although in practice this will probably never happen, it is legal for
- the indices of this last element to exceed the bounds of the array.
- Therefore, continue checking. */
- }
-
- return true;
- }
-
/* Determine information about number of iterations a LOOP from the index
IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
guaranteed to be executed in every iteration of LOOP. Callback for
--- 2648,2653 ----
*************** idx_infer_loop_bounds (tree base, tree *
*** 2699,2719 ****
struct ilb_data *data = (struct ilb_data *) dta;
tree ev, init, step;
tree low, high, type, next;
! bool sign, upper = data->reliable, at_end = false;
struct loop *loop = data->loop;
if (TREE_CODE (base) != ARRAY_REF)
return true;
- /* For arrays at the end of the structure, we are not guaranteed that they
- do not really extend over their declared size. However, for arrays of
- size greater than one, this is unlikely to be intended. */
- if (array_at_struct_end_p (base))
- {
- at_end = true;
- upper = false;
- }
-
ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
init = initial_condition (ev);
step = evolution_part_in_loop_num (ev, loop->num);
--- 2666,2677 ----
struct ilb_data *data = (struct ilb_data *) dta;
tree ev, init, step;
tree low, high, type, next;
! bool sign, upper = data->reliable;
struct loop *loop = data->loop;
if (TREE_CODE (base) != ARRAY_REF)
return true;
ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
init = initial_condition (ev);
step = evolution_part_in_loop_num (ev, loop->num);
*************** idx_infer_loop_bounds (tree base, tree *
*** 2738,2749 ****
sign = tree_int_cst_sign_bit (step);
type = TREE_TYPE (step);
- /* The array of length 1 at the end of a structure most likely extends
- beyond its bounds. */
- if (at_end
- && operand_equal_p (low, high, 0))
- return true;
-
/* In case the relevant bound of the array does not fit in type, or
it does, but bound + step (in type) still belongs into the range of the
array, the index may wrap and still stay within the range of the array
--- 2696,2701 ----
