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