add a type-based alias analysis pass #6750

Closed
thestinger opened this Issue May 26, 2013 · 2 comments

Comments

Projects
None yet
2 participants
@thestinger
Contributor

thestinger commented May 26, 2013

We have an amazing amount of information that we're not passing along to LLVM. We should be attaching metadata to pointers and using it to respond to alias analysis queries. A good start would be to figure out how to make a shim responding MayAlias to all queries.

The NoAlias response may be used when there is never an immediate dependence between any memory reference based on one pointer and any memory reference based the other. The most obvious example is when the two pointers point to non-overlapping memory ranges. Another is when the two pointers are only ever used for reading memory. Another is when the memory is freed and reallocated between accesses through one pointer and accesses through the other — in this case, there is a dependence, but it’s mediated by the free and reallocation.

For Const objects, assuming no incorrect unsafe blocks, we can respond NoAlias for every &mut, & and ~ pointer because they either only read memory or are the only handle able to mutate the memory while they exist. We have the potential to beat C/C++ on a lot of benchmarks here...

@cmr

This comment has been minimized.

Show comment
Hide comment
@cmr

cmr Jul 24, 2013

Member

@smvv expressed interest in this.

Member

cmr commented Jul 24, 2013

@smvv expressed interest in this.

bors added a commit that referenced this issue May 5, 2014

auto merge of #13935 : thestinger/rust/noalias, r=pcwalton
This was removed because these could alias with `&const T` or `@mut T`
and those are now gone from the language. There are still aliasing
issues within local scopes, but this is correct for function parameters.

This also removes the no-op `noalias` marker on proc (not a pointer) and
leaves out the mention of #6750 because real type-based alias analysis
is not within the scope of best effort usage of the `noalias` attribute.

Test case:

    pub fn foo(x: &mut &mut u32) {
        **x = 5;
        **x = 5;
    }

Before:

    define void @_ZN3foo20h0ce94c9671b0150bdaa4v0.0E(i32** nocapture readonly) unnamed_addr #0 {
    entry-block:
      %1 = load i32** %0, align 8
      store i32 5, i32* %1, align 4
      %2 = load i32** %0, align 8
      store i32 5, i32* %2, align 4
      ret void
    }

After:

    define void @_ZN3foo20h0ce94c9671b0150bdaa4v0.0E(i32** noalias nocapture readonly) unnamed_addr #0 {
    entry-block:
      %1 = load i32** %0, align 8
      store i32 5, i32* %1, align 4
      ret void
    }

Closes #12436
@thestinger

This comment has been minimized.

Show comment
Hide comment
@thestinger

thestinger Aug 15, 2014

Contributor

I don't think we need our own pass anymore. See #16515

Contributor

thestinger commented Aug 15, 2014

I don't think we need our own pass anymore. See #16515

@thestinger thestinger closed this Aug 15, 2014

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment