[LLVMdev] Enhancing BasicAliasAnalysis for Rust

[Hal Finkel]

----- Original Message -----
> From: "John Kåre Alsaker" <john.mailinglists at gmail.com>
> To: "Sean Silva" <chisophugis at gmail.com>
> Cc: llvmdev at cs.uiuc.edu
> Sent: Tuesday, July 29, 2014 6:10:23 PM
> Subject: Re: [LLVMdev] Enhancing BasicAliasAnalysis for Rust
> 
> 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
> }
> 
> 

Hi John,

To get you started, here's how I imagine such a scheme might be implemented: At the beginning of the BasicAliasAnalysis::aliasCheck function, we call GetUnderlyingObject on both pointers, and if the underlying objects are different, and if they're both 'identified' objects (as determined by the isIdentifiedObject function), then we return NoAlias.

You might create a wrapper around GetUnderlyingObject that will look through loads tagged with your metadata, but increase some kind of depth counter each time this is done. Then, instead of comparing the underlying objects, you instead compare the (underlying object, depth) tuples and make a decision that way (returning NoAlias only if both differ and both underlying objects are identified).

I can imagine a capability like this could be generally useful, but I can also imagine it not being generally useful, so I encourage you to experiment.

You might find, for example, that what you really want is field sensitivity (because you have a pointer to a structure of noalias pointers), and you might find the GetPointerBaseWithConstantOffset function useful in dealing with that.

Please follow-up with us and let us know what you find to be most useful.

 -Hal

> 
> 
> 
> 
> 
> 
> -- 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
> 
> 
> 
> 
> _______________________________________________
> 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