llvm dev - Jun 2014 - [LLVMdev] New Alias Analysis Algorithm

Hello LLVMDev,

I'm George, an intern for Google who will be working on LLVM. Currently,
I'm starting to implement a set-based Alias Analysis algorithm for LLVM,
which looks like it may be more accurate than Steensgard's, and can be
constructed in approximately nlog(n) time and linear space (n = number of
memory locations; queries happen in constant time). It will most likely be
implemented as a function pass, and if all goes well, I hope to have it
committed.

If you would like more information about the algorithm, see link [1] below.
If you're interested in rationale behind algorithm selection, a few of the
implementation details, and a summary of how it works, see [2] below. As an
aside, chandlerc has warned me that LLVM isn't quite perfect about
notifying all function passes that transforms have been applied to a
function. This is known, and will be taken into account as best as
possible. :)

If you have any questions, suggestions, comments, etc. about this, then
feel free to ping me,
George

[1] -
http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf?id=home&cache=cache
[2] -
https://docs.google.com/a/google.com/document/d/1lgKGuVoMVXBnqqT6fGNtgvx4P0I8fJbMPqeuGL9GoNU/pub
<https://docs.google.com/a/google.com/document/d/1lgKGuVoMVXBnqqT6fGNtgvx4P0I8fJbMPqeuGL9GoNU/pub>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140610/ec40e87f/attachment.html>

Hi George,

It seems your second link isn't publicly viewable.

Cheers,
Amara

On 10 June 2014 21:45, George Burgess <gbiv at google.com>
wrote:
> Hello LLVMDev,
>
> I'm George, an intern for Google who will be working on LLVM.
Currently, I'm
> starting to implement a set-based Alias Analysis algorithm for LLVM, which
> looks like it may be more accurate than Steensgard's, and can be
constructed
> in approximately nlog(n) time and linear space (n = number of memory
> locations; queries happen in constant time). It will most likely be
> implemented as a function pass, and if all goes well, I hope to have it
> committed.
>
> If you would like more information about the algorithm, see link [1] below.
> If you're interested in rationale behind algorithm selection, a few of
the
> implementation details, and a summary of how it works, see [2] below. As an
> aside, chandlerc has warned me that LLVM isn't quite perfect about
notifying
> all function passes that transforms have been applied to a function. This
is
> known, and will be taken into account as best as possible. :)
>
> If you have any questions, suggestions, comments, etc. about this, then
feel
> free to ping me,
> George
>
> [1] -
>
http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf?id=home&cache=cache
> [2] -
>
https://docs.google.com/a/google.com/document/d/1lgKGuVoMVXBnqqT6fGNtgvx4P0I8fJbMPqeuGL9GoNU/pub
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

My apologies. Please try the link below. :)

https://docs.google.com/a/google.com/document/d/1nGFKMmr-HbdEiag9G1GeWurgOV0CweSUjLXFr3LAwqg/edit

- George

On Tue, Jun 10, 2014 at 4:35 PM, Amara Emerson <amara.emerson at
gmail.com>
wrote:
> Hi George,
>
> It seems your second link isn't publicly viewable.
>
> Cheers,
> Amara
>
> On 10 June 2014 21:45, George Burgess <gbiv at google.com> wrote:
> > Hello LLVMDev,
> >
> > I'm George, an intern for Google who will be working on LLVM.
Currently,
> I'm
> > starting to implement a set-based Alias Analysis algorithm for LLVM,
> which
> > looks like it may be more accurate than Steensgard's, and can be
> constructed
> > in approximately nlog(n) time and linear space (n = number of memory
> > locations; queries happen in constant time). It will most likely be
> > implemented as a function pass, and if all goes well, I hope to have
it
> > committed.
> >
> > If you would like more information about the algorithm, see link [1]
> below.
> > If you're interested in rationale behind algorithm selection, a
few of
> the
> > implementation details, and a summary of how it works, see [2] below.
As
> an
> > aside, chandlerc has warned me that LLVM isn't quite perfect about
> notifying
> > all function passes that transforms have been applied to a function.
> This is
> > known, and will be taken into account as best as possible. :)
> >
> > If you have any questions, suggestions, comments, etc. about this,
then
> feel
> > free to ping me,
> > George
> >
> > [1] -
> >
>
http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf?id=home&cache=cache
> > [2] -
> >
>
https://docs.google.com/a/google.com/document/d/1lgKGuVoMVXBnqqT6fGNtgvx4P0I8fJbMPqeuGL9GoNU/pub
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140610/a0924475/attachment.html>

Hi George,

Are you working on this in a publicly-accessible repository?

When you say it will be a function pass, you mean a function-level analysis
pass? Would making it a CGSCC pass be significantly more expensive?

 -Hal

----- Original Message -----
> From: "George Burgess" <gbiv at google.com>
> To: llvmdev at cs.uiuc.edu
> Sent: Tuesday, June 10, 2014 3:45:56 PM
> Subject: [LLVMdev] New Alias Analysis Algorithm
> 
> 
> 
> 
> Hello LLVMDev,
> 
> 
> I'm George, an intern for Google who will be working on LLVM.
> Currently, I'm starting to implement a set-based Alias Analysis
> algorithm for LLVM, which looks like it may be more accurate than
> Steensgard's, and can be constructed in approximately nlog(n) time
> and linear space (n = number of memory locations; queries happen in
> constant time). It will most likely be implemented as a function
> pass, and if all goes well, I hope to have it committed.
> 
> 
> If you would like more information about the algorithm, see link [1]
> below. If you're interested in rationale behind algorithm selection,
> a few of the implementation details, and a summary of how it works,
> see [2] below. As an aside, chandlerc has warned me that LLVM isn't
> quite perfect about notifying all function passes that transforms
> have been applied to a function. This is known, and will be taken
> into account as best as possible. :)
> 
> 
> If you have any questions, suggestions, comments, etc. about this,
> then feel free to ping me,
> George
> 
> 
> [1] -
>
http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf?id=home&cache=cache
> 
> [2] -
>
https://docs.google.com/a/google.com/document/d/1lgKGuVoMVXBnqqT6fGNtgvx4P0I8fJbMPqeuGL9GoNU/pub
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory