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

[Daniel Berlin]

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.