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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140729/c328b00c/attachment.html>
Did you mean to phrase this as a proposed approach and ask for feasibility? Or are you more interested in the question "Rust has these language semantics, how can I get LLVM to best exploit this?"? LLVM may have an existing mechanism which would serve your needs. Do you have some concrete examples of IR produced by the Rust frontend that you are seeing LLVM not optimize as well as it could? -- Sean Silva On Mon, Jul 28, 2014 at 6: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. > > _______________________________________________ > 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/20140729/b7d43162/attachment.html>
On Tue, Jul 29, 2014 at 6:14 PM, Sean Silva <chisophugis at gmail.com> wrote:> Did you mean to phrase this as a proposed approach and ask for feasibility? >Yes.> Or are you more interested in the question "Rust has these language > semantics, how can I get LLVM to best exploit this?"? LLVM may have an > existing mechanism which would serve your needs. >I am interested in that as well. Rust has the very nice property where references never alias, with the exception of references to UnsafeCell.> > Do you have some concrete examples of IR produced by the Rust frontend > that you are seeing LLVM not optimize as well as it could? >An example my proposed approach would solve if the Rust frontend was modified to output !inheritalias metadata: !0 = metadata !{} define void @foo(i8** noalias nocapture readonly %g) { %1 = load i8** %g, align 8, !inheritalias !0 %2 = load i8* %1, align 1 tail call void @bar(i8 signext %2) %3 = load i8** %g, align 8, !inheritalias !0 %4 = load i8* %3, align 1 tail call void @bar(i8 signext %4) ret void } declare void @bar(i8 signext) With this metadata LLVM could infer that %1 and %3 doesn't alias with anything since %g doesn't and optimize @foo to: define void @foo(i8** noalias nocapture readonly %g) { %1 = load i8** %g, align 8, !inheritalias !0 %2 = load i8* %1, align 1 tail call void @bar(i8 signext %2) tail call void @bar(i8 signext %2) ret void }> -- Sean Silva > > > On Mon, Jul 28, 2014 at 6: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. >> >> _______________________________________________ >> 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/20140730/511fc315/attachment.html>
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.