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. 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