llvm dev - Jun 2015 - [LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?

On Mon, Jun 15, 2015 at 6:03 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> > From a personal perspective, I'm particularly interested in the
maximum
> > analytic precision each AA approach can take, almost without regard to
> how
> > much time or memory the computation takes to run.
>
> I'm wildly curious why.
>
One reason is that I'm simply curious about the trade-off space between AA
precision and AA running-time.  Since I don't make compilers for a living,
I have the luxury of staring at corners of the design space which would be
idiotic to actually include in LLVM :)

Another reason is that in past work, I've sometimes worked on code where
I'd gladly accept a 10-day compilation time, if it bought me an extra 10%
in performance.  So I sometimes wonder what's involved in making such
optimization passes available, even though people wouldn't want to use them
on a day-to-day basis.

Constraints contain stride info, and intersection is then used
to
> compute what sub-variables a constraint touches during solving.
> It is a variant of this:
> http://homepages.mcs.vuw.ac.nz/~djp/files/paste04.ps

Thanks, I'll try to give it a read.

> Some programs have so many sub-variables you will run out of memory.
> This is true in the location set approach as well.
>
I'm surprised you ran into that kind of trouble with memory.  Was that back
in 32-bit days?

> GCC only created variables for possibly-used field ranges too.
> I can point you at GCC bugs offline if you are interested
>
Yeah, if you don't mind I'd be grateful for the links.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150615/a3168783/attachment.html>

On Mon, Jun 15, 2015 at 4:00 PM, Christian Convey
<christian.convey at gmail.com> wrote:
> On Mon, Jun 15, 2015 at 6:03 PM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>>
>> > From a personal perspective, I'm particularly interested in
the maximum
>> > analytic precision each AA approach can take, almost without
regard to
>> > how
>> > much time or memory the computation takes to run.
>>
>> I'm wildly curious why.
>
>
> One reason is that I'm simply curious about the trade-off space between
AA
> precision and AA running-time.  Since I don't make compilers for a
living, I
> have the luxury of staring at corners of the design space which would be
> idiotic to actually include in LLVM :)
Fair enough.
>
> Another reason is that in past work, I've sometimes worked on code
where I'd
> gladly accept a 10-day compilation time, if it bought me an extra 10% in
> performance.  So I sometimes wonder what's involved in making such
> optimization passes available, even though people wouldn't want to use
them
> on a day-to-day basis.
FWIW:
I've explored this before. I built a large-scale distributed
completely precise context-sensitive alias-analysis and ran it on
about 100k machines.  It was brute-force and took no shortcuts, etc.
It was run on some apps that are very large, and took many terabytes
of memory and disk :)

My result:
Certainly there are some apps it may buy you 10%.
But most, it won't, and where it does, there are often cheaper
techniques (like runtime  tests, etc) that will get you 9%.

>
>> Constraints contain stride info, and intersection is then used to
>> compute what sub-variables a constraint touches during solving.
>> It is a variant of this:
>> http://homepages.mcs.vuw.ac.nz/~djp/files/paste04.ps
>
>
> Thanks, I'll try to give it a read.
>
>>
>> Some programs have so many sub-variables you will run out of memory.
>> This is true in the location set approach as well.
>
>
> I'm surprised you ran into that kind of trouble with memory.  Was that
back
> in 32-bit days?
Even in a 64 bit world, you will run out of memory quickly. I don't
think you realize how many edges/variables/etc you are talking about
for large programs.
People had cases with structures with thousands of fields,  nested
these, and instantiate them into tens of thousands of variables.
It was billions of variables  :)
Having only-used ranges got it down to tens of millions.
Now GCC just punts on some sane size.
>
>>
>> GCC only created variables for possibly-used field ranges too.
>> I can point you at GCC bugs offline if you are interested
>
>
> Yeah, if you don't mind I'd be grateful for the links.
>
I'll send them offline.

On Mon, Jun 15, 2015 at 7:14 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> > Another reason is that in past work, I've sometimes worked on code
where
> I'd
> > gladly accept a 10-day compilation time, if it bought me an extra 10%
in
> > performance.  So I sometimes wonder what's involved in making such
> > optimization passes available, even though people wouldn't want to
use
> them
> > on a day-to-day basis.
>
> FWIW:
> I've explored this before. I built a large-scale distributed
> completely precise context-sensitive alias-analysis and ran it on
> about 100k machines.  It was brute-force and took no shortcuts, etc.
> It was run on some apps that are very large, and took many terabytes
> of memory and disk :)
>
> My result:
> Certainly there are some apps it may buy you 10%.
> But most, it won't, and where it does, there are often cheaper
> techniques (like runtime  tests, etc) that will get you 9%.
>
Wow.  I'll consider my curiosity to have been vicariously satisfied by your
experiment.  Thanks for freeing up six months of my life :)

> Even in a 64 bit world, you will run out of memory quickly. I don't
> think you realize how many edges/variables/etc you are talking about
> for large programs.
> People had cases with structures with thousands of fields,  nested
> these, and instantiate them into tens of thousands of variables.
> It was billions of variables  :)
> Having only-used ranges got it down to tens of millions.
> Now GCC just punts on some sane size.
>
Thanks, I'm going to guess you're right that I'm failing to
appreciate the
numbers of things involved.  I appreciate the warning.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150615/1a773f04/attachment.html>