On Tue, 2 May 2017, Jakub Jelinek wrote: > 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]++; > }
I don't think it's too expensive. Yes, you get one additional assert (and SSA name) per array index. My main gripe would be the affect on -Warray-bounds... > > If array_at_struct_end_p is wrong, it should be fixed ;) Indeed. It was originally meant to say false if you can trust TYPE_DOMAIN of the array but now it says false if there's some means to constrain the array size (the DECL_P path and now your STRING_CST one). But all callers afterwards just look at TYPE_DOMAIN ... > > 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 can try. Is there a PR for this? > 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. Sure. I'd have expected you simply handle ARRAY_REF of a VAR_DECL and nothing else ;) Richard.
