On May 24, 2017 5:38:53 PM GMT+02:00, Andrew MacLeod <amacl...@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
