..On Tue, May 23, 2017 at 5:24 PM, Andrew MacLeod <amacl...@redhat.com> wrot
> On 05/23/2017 10:54 AM, Jakub Jelinek wrote:
>>
>> On Tue, May 23, 2017 at 10:38:44AM -0400, Andrew MacLeod wrote:
>>>
>>> As follow on work we have discussed an interface which would be able to
>>> calculate a bitmask (for either zeros or ones) from a range and vice
>>> versa..
>>
>> Sometimes the range vs. nonzero_bits info is redundant, you can compute
>> one from the other or vice versa without any information loss, but in many
>> cases it is not redundant, you can have e.g. known zero least significant
>> or
>> some middle bits, or the range boundaries are not powers of two or powers
>> of
>> two - 1. The point is that with the coexistence of both it can be
>> gradually
>> improved, first you e.g. find some range, then CCP can use the
>> corresponding
>> nonzero_bits knowledge from that range in bitwise mask propagation, then
>> you
>> notice some other bits are known to be zero, perhaps from that adjust the
>> value range again if possible, ...
>
>
> Right, but we do only need to store both for those cases which we are
> actually refining the info. and via a central manager of the information it
> can know when that is a thing to do and do it. I also hope to ad some of
> the bit inormation ot the on demand system.. tat'll come later tho. I
> simply maintain that the vast majority of ssa_names are unlikely to need
> both, not that we never need both. This seems like statistics that
> shouldn't be too hard to find with some simple looking at the data at the
> end of compilation or various passes.
>
>>
>>> why don't we actually try measuring it and see if it is noticeable? and
>>> if
>>> it is, where the issues really are. You really think we have relevant
>>> range
>>> info for 50% of the ssa_names in a program? Id be surprised. Again,
>>> thats
>>> something we should probably measure and see whats typical. the range
>>> table
>>> should only be used when we can refine the global range to something
>>> other
>>> than range_for_type().
>>
>> I'm not used to build firefox and various other large C++ projects with
>> LTO
>> regularly, so it would be harder for me to get that stuff working and
>> measure it, but I think e.g. Honza or Martin L. do that often and could
>> provide hints on what is needed to test that, then we can have exact
>> numbers.
>
> that seems reasonable. I think we ought to look at the low hanging fruit
> for making it more efficient to start with before hassling them or that..
> unless it is trivial. It would be useful t have input from "heavy"
> application users if there is any/much impact.
>>>
>>> We can also change the representation of the range to be 2 ranges like it
>>> is
>>
>> Well, the current representation is just 1 range (2 numbers) + 1 extra
>> number for the nonzero_bits bitmask.
>
>
> oh yeah,right.... but anti range is evil. Its worth losing a little bit of
> memory to get rid of that, imo :-)
Well, anti-ranges are "evil" for actual working with ranges. They are nice
for optimizing the storage requirements though.
As I'm replying late I'll add that yes, it does make a difference in memory
use. We've seen this with IPA VRP info eating up 1 GB extra memory
for firefox so we optimized it to use trailing wide-ints. So ..
+#define MAX_RANGES 6
...
+class GTY(()) irange
+{
...
+ public:
+ tree type;
+ wide_int bounds[MAX_RANGES];
is definitely a no-go. type is also redundant. Making 'n' a size_t is stupid.
Please apply some more common sense here...
We need to really think about making this a bit more flexible than just handling
integer ranges, eventually tracking non-zero bits as well.
So first of all I'd suggest to make MAX_RANGES a template parameter
so we can eventually use the same representation in both the VRP lattice,
the SSA name info and the basic range ops (I see you re-implemented all
of those rather than refactoring the VRP ones which would have benefited
most from "getting rid of anti-ranges").
What's this overflow flag for anyway?
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.
>>
>>> 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.
> 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?
>>>
>>> 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.
> Andrew
