On Tue, 17 Apr 2012, Richard Guenther wrote:
>
> 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.
I ended up with the following simplified variant because we have
testcases that test that niter still records an estimate for
a trailing a[5].
Bootstrapped and tested on x86_64-unknown-linux-gnu, committed.
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 (array_at_struct_end_p): Move ...
* expr.c (array_at_struct_end_p): ... here. Rewrite.
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. */
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 ----
