[LLVMdev] Enhancing BasicAliasAnalysis for Rust

[Cameron Zwarich]

I’ve thought about this a lot, but haven’t started to implement anything yet.

I assume that you’re referring to the aliasing rules on borrowed pointers:

1) Accesses of paths derived from an &mut borrow have no aliases in the scope of the borrow

2) Writes to direct paths of local variables have no aliases in the most narrow borrow scope containing the write.

3) Paths derived from an & borrow aren’t modified in the scope of the borrow, unless the path involves an UnsafeCell (formerly Unsafe).

I think that it should be possible to model these using the noalias / alias.scope metadata:

http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata

There are some questions about using this to model C’s exact restrict semantics, but they shouldn’t apply here. You should be able to translate Rust’s borrow scopes into alias scopes. Currently borrow scopes are nested lexical scopes, but soon they will be single-entry / multiple-exit control-flow regions. Either way it shouldn’t be a problem.

There are a few caveats:

1) A lot of Rust’s memory accesses ultimately occur via raw *T pointers, and we still have to treat an *T as being able to alias anything.

2) We use a lot of memcpys in Rust for moves and copies. I’m not entirely sure how this works with memcpy. If you put both the src and dst scope on a memcpy intrinsic, it will look like the memcpy is modifying the src in addition to the dst. That could be a problem down the line.

If you start working on it and want to talk about this in more detail than is suitable for LLVMdev, feel free to email me or find me on #rust as zwarich.

Cameron

On Jul 28, 2014, at 5:35 PM, John Kåre Alsaker <john.mailinglists at gmail.com> wrote:

> Since Rust references usually never aliases it would be nice if we could exploit this for code generation. One idea I had to improve alias analysis is to insert metadata on pointer loads. !inheritalias could be added to load instructions to indicate that if we know all the aliases of the pointer we load from, then we also know all the aliases of the pointer value loaded. Given that pointer loads are common and things are likely marked with `noalias` in Rust, this seems like useful metadata. It could also for example apply to loading C++'s unique_ptr fields.
> 
> I'm wondering what the feasibility of extending BasicAliasAnalysis to utilize the proposed metadata would be.