[LLVMdev] Whole program alias analysis in backend

[Daniel Berlin]

On Sun, Jun 9, 2013 at 11:31 PM, ihusar at fit.vutbr.cz <ihusar at fit.vutbr.cz>wrote:

> Hello everyone,
>
>   we are planning to implement a stronger alias analysis
> for backend, because e.g. for VLIW architectures, this is our main
> performance limitation.
> I would have 2 questions regarding this.
>
>   I know that backend processes one function at a time,
> is it somehow possible to do there a whole program analysis,
> or could you give me some guidelines?
>
>   Which alias analysis algorithm you would recommend?
> There was a Stensgaard algorithm implemented before, but noone
> was maintaning it, so it was removed


There were other concerns that should not be gone into on this mailing list.


> . Do you think that this could be a suitable
> algorithm or should we choose something newer and stronger?
> Regarding the scalability, it ok for us, if the algorithm would run e.g. 1
> hour for a
> 100 KLOC application.
>

Newer implementations of Andersen's will give you more accurate analysis,
and run in about 20 seconds on 1.5 million LOC on a modern machine.
You could actually do better with a little work, but that is an actual
number from an real field-sensitive solver implemented on top of LLVM,
running on Wine (that is about 2.5 million lines of code).
Scalability is roughly linear in practice. The GIMP, which is about 700k
LOC, takes 4 seconds.

There are always edge cases, of course.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130611/41598e4f/attachment.html>