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. :slight_smile:

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

[1] -

[2] -

Hi George,

It seems your second link isn't publicly viewable.


My apologies. Please try the link below. :slight_smile:

- George

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?