On Tue, May 02, 2017 at 01:13:19PM +0200, Richard Biener wrote:
> On Sat, 29 Apr 2017, Jakub Jelinek wrote:
>
> > On Fri, Apr 21, 2017 at 04:42:03PM +0200, Richard Biener wrote:
> > > On April 21, 2017 4:06:59 PM GMT+02:00, Jakub Jelinek <ja...@redhat.com>
> > > wrote:
> > > >This patch attempts to implement the optimization mentioned in
> > > >http://gcc.gnu.org/ml/gcc-patches/2017-02/msg00945.html
> > > >If we know a (relatively small) value range for ARRAY_REF index
> > > >in constant array load and the values in the array for all the indexes
> > > >in the array are the same (and constant), we can just replace the load
> > > >with the constant.
> > >
> > > But this should be done during propagation (and thus can even produce a
> > > range rather than just a constant).
> >
> > True, I've changed the implementation to do that.
> > Except that it is only useful during propagation for integral or pointer
> > types, for anything else (and for pointers when not just doing NULL vs.
> > non-NULL vr) it is also performed during simplification (in that case
> > it requires operand_equal_p values).
> >
> > The patch also newly computes range for the index and range from the array
> > bounds (taking into account arrays at struct end) and intersects them,
> > plus takes into account that some iterators might have a couple of zero LBS
> > bits (as computed by ccp).
>
> Hmm, while I can see how this helps I'd rather not do this in this way.
> (see PR80533 and my followup with a testcase which shows
> array_at_struct_end_p is wrong) Ideally we'd add asserts for array
> indices instead. Thus
>
> i_3 = ASSERT_EXPR <i_2, (unsigned)i_2 <= 3>
> .. = a[i_3];
>
> which of course needs adjustment to -Warray-bounds to look at the
> range of the original SSA name (and in loops even that might degrade...).
>
> Was this necessary to get any reasonable results?
Yes, it is very common that you end up with a VR that has negative min, or
very large max, but if the array is in the middle of a struct, or it is a
toplevel non-common array variable etc., which is quite common case, then
we still should be able to optimize it.
Adding extra ASSERT_EXPRs would work too, but wouldn't it be too expensive?
I mean there can be lots of array accesses with the same index, if we'd add
an ASSERT_EXPR for every case, VRP work could increase many times. It is
true that we'd be able to optimize:
int foo [5] = { 1, 2, 3, 4, 5 };
void
foo (int i, int j)
{
if (j > 10)
{
foo[i] = 10;
if (i < 0 || i >= 5)
link_error ();
}
foo[i]++;
}
If array_at_struct_end_p is wrong, it should be fixed ;)
> Still given the high cost of get_array_ctor_element_at_index which
> does linear searching I'd add a few early-outs like
>
> base = get_base_address (rhs);
> ctor = ctor_for_folding (base);
> if (! ctor)
> return NULL_TREE;
This one I can add easily.
> I'd restructure the patch quite different, using for_each_index on the
> ref gather an array of index pointers (bail out on sth unhandled).
> Then I'd see if I have interesting ranges for them, if not, bail out.
> Also compute the size product of all ranges and test that against
> PARAM_MAX_VRP_CONSTANT_ARRAY_LOADS. Then store the minimum range
> value in the index places (temporarily) and use get_base_ref_and_extent to
> get at the constant "starting" offset. From there iterate using
> the remembered indices (remember the ref tree as well via for_each_index),
> directly adjusting the constant offset so you can feed
> fold_ctor_reference the constant offsets of all elements that need to
> be considered. As optimization fold_ctor_reference would know how
> to start from the "last" offset (much refactoring would need to be
> done here given nested ctors and multiple indices I guess).
But for this, don't you want to take it over?
I agree that the current implementation is not very efficient and that is
why it is also limited to that small number of iterations.
As many cases just aren't able to use the valueize callback, handling
arbitrary numbers of non-constant indexes would be harder.
Jakub
