This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: SSA range class and removal of VR_ANTI_RANGEs
On May 24, 2017 5:38:53 PM GMT+02:00, Andrew MacLeod <amacleod@redhat.com> wrote:
>On 05/24/2017 04:25 AM, Richard Biener wrote:
>> > What's this overflow flag for anyway?
>
>The new on-demand range calculators do operations on ranges, and that
>flag is set when a range calculation may have overflowed... which is of
>
>use when issuing warnings or deciding to not use a range.
>ie given a made up example:
>
>signed char a,b;
>a_1 = b_3 +10;
>if (b_3 > 100) foo (a_1)
>
>on the true side we know b_3 has the range [101,127]. It also
>calculates the range of a_1 as [111, 127][-128,-119] and sets the
>overflow bit since the calculation of a_1 can overflow for some
>elements
>of the range of b_3. Anyone wanting to use the range can check the
>overflow if its something they care about. The overflow stuff has not
>been completely flushed out yet, but it is in place for the moment. we
>
>can decide down the road if it serves enough purpose to stick around,
>or
>needs expansion, or whatever.
>> > > That said, I think it's the wrong approach to start mucking with
>SSA > name associated ranges given they are supposed to be a cheap
>storage > variant of what VRP computes. Start by making the VRP
>machinery work > from on-demand-ranges. I do have some prototypes from
>
>last year or > the year before to do this -- the helpers VRP machinery
>is already > generic enough if you make use of VRPs range type.
>
>well its also no longer just contained to VRP. This work is all driven
>by the desire of other optimizations to access range information. Some
>
>have hacked their required bits into vrp, making vrp a sort of mini
>optimization phase, others have attempted to leverage assert_exprs at
>their point in time (not too successfully I think?) , others just live
>with the lack of contextual range info after VRP... after looking at
>it,
>i decided trying to teach other optimizations about assert_expr in
>order
>to make their info available later was not something that seemed like a
>
>good long term solution.
>
>The most pressing matter was the desire for CFG sensitive range
>information outside of VRP. Since assert_exprs are gone after VRP, we
>loose the information on the branches of a diamond without a lot of
>hackery.
That's what my prototype does. I'll dig it out and will send it after public holidays tomorrow. I do not believe in duplicating all the range operations we have in VRP.
Richard.
The on-demand system is positioned to leave VRP as is for the
>
>moment, and allow passes outside of VRP to pick up the range info VRP
>generated and refine that range based on branches. Once this is
>working well, I'd have the confidence to then maybe go into VRP and try
>
>to replace the assert_exprs with the on demand system. This allows the
>proving ground to be outside of VRP for just the passes which are
>desperate for better ranges. This allows the on-demand system to be
>tested, utilized, and various efficiencies explored without impacting
>any optimizations negatively by trying to replace VRP up front and not
>getting everything it does or consuming too much compilation time or
>memory..
>
>I'll shortly prepare the writeup for the on demand mechanism.. I'm
>still
>getting it working :-P
>> > >>> >>>> More importantly, when the on-demand range work comes
>online
>it >>>> will end the proliferation of SSA_NAMES which carry ASSERT_EXPR
>
> >>>> information. We won't see the trail of new ssa_names the >>>>
>ASSET_EXPR chains create. I suspect that will eliminate storing >>>>
>global ranges and bits for most SSA names, which is likely to >>>> make
>
>this class a win regardless. >>> >>> Are you sure it is desirable to
>recompute it in all cases, rather >>> than just use what you have
>recorded and recompute what you don't >>> have computed yet? E.g.
>various ranges come from if (cond) >>> __builtin_unreachable (); style
>asserts, we do want to drop them >>> at some point and the only spot to
>
>keep that info afterwards is >>> SSA_NAME range info. >> >> >> I think
>it will be desirable in most cases. The on-demand system >> does *not*
>
>use assert_exprs. It will make them mostly obsolete, >> and the goal
>is to eventually eliminate them from the IL >> completely. > > They are
>
>not in the IL. They are only temporarily there during VRP > (not early
>
>VRP for example) to make VRP work as a SSA propagation > pass.
>
>right but a number of other optimization want the contextual
>information
>assert_expr's provide.. outside of VRP. so either we have to keep the
>multitude of ssa_names that asset_exprs create in order to maintain the
>
>range info, either via copies or maintaining the assert_expr, or we do
>something else.
>
>>> Most assert_exprs exist to provide ranges on sub-branches of the >>
>CFG. These we are likely to be able to simply replace with the >>
>on-demand mechanism. I suspect we'll find some cases where we find >>
>its more useful to have a new global ssa_name which carries >>
>information, but I expect the situation which requires that to be >>
>fairly rare. >> >> There will be a cycle where I have to identify cases
>
>we missing and >> catch those... or introduce a new ssa_name to handle
>the situation >> until such time that it can be addressed. I hope to
>get
>thru most >> of that in this stage 1 > > But if you do on-demand ranges
>
>why do you need to change the SSA > name associated ranges at all?
>
>It will still be of use for things which are learned. VRP has
>algorithms which iterate around loops and refine the known global
>bounds
>of things like loop indexes and such that aren't immediately obvious by
>
>simply looking at the static information in the IL. Other optimizations
>
>will likely do similar things and can help refine the known global
>bounds, This is then combined with whatever the static ranges the
>ondemand system picks up form the IL to give better contextual ranges.
>
>> > >>>> >>>> Im not familiar with the details of how wide_int and host
>
>vs >>>> target integers really works. I don't think Aldy is either. If
>
>>>>> there is a more efficient way to store an integer fr this use >>>>
>
>case then by all means we can do that. to get things working we >>>>
>just used what was easily available. if there is a more >>>>
>efficient
>way to represent it, perhaps it makes sense to create >>>> a class for
>a"memory_efficient_wide_int" and allow it to >>>> convert back and
>forth
>from a wide_int as needed? >>> >>> You want to talk to Richard
>Sandiford
>mainly here I guess. There >>> are many flavors of wide ints, for
>different purposes. >> >> I did not know that :-) Aldy, maybe you
>should have a chat :-) > > There's trailing_wide_ints. But having 6 of
>
>them is still > expensive. > > Something nice would be to make
>wide_ints
>not tied to use > HOST_WIDE_INT as basic element type but for example
>uint32.
>
>Yeah, wide_int always seemed kinda like overkill for some things... it
>would be nice to have something simple and efficient. we can also drop
>
>to 2 ranges instead of 3 initially too, if that helps. and as I
>mentioned, if necessary we can always implement the current irange
>class
>using todays data structures if its really that big a deal.
>
>My original desire was to implement the range class as a chameleon
>class
>which would use only what it needed from a pool of singe range, double
>range, or whatever else was allowed by the current optimization state.
>
>That seemed like overkill to get the stuff up and running, but would
>use
>only the actual amount of memory needed... and none if there was no
>range info. well, other than the pointer to the range class for each
>ssa_name.
>
>
>So at the moment, the bottom line is we need to make the ranges more
>efficient than they are currently. Aldy has been focusing on getting
>things working more so than efficiency of implementation, so that is
>something he needs to focus on now...
>
>what would be the most efficient way to represent a range bound if it
>isn't trailing_wide_int? can we have some sort of class or typedef
>that
>is set up at configuration time to would either be a basic integral
>type
>or whatever else would work best?
>
>
>Andrew