inout and aliasing in the optimizer


(Erik Eckstein) #1

Hi,

I'm currently working on improving alias analysis in the optimizer and I run into following problem:

If alias analysis assumes that inout may not alias any other object, we may violate memory safety. Note that currently it's not always assumed, e.g. not in computeMemoryBehavior for apply insts.

As I understood, if the inout rule is violated, the program is not expected to behave as intended, but is still must be memory safe.
For this reason we had to insert explicit checks for inout violations in the stdlib, e.g. in ArrayBuffer: _precondition(_isNativeTypeChecked == wasNativeTypeChecked, "inout rules were violated: the array was overwritten")

Now with improved alias analysis and assuming inout-no-alias, the optimizer (specifically redundant load elimination) may eliminate these precondition checks in the stdlib.
And I can think of other cases, e.g.

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %3 = load %1
  %4 = ref_element_addr %3
  %ptr = load %4
}

Redundant load elimination may optimize this to

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %4 = ref_element_addr %2
  %ptr = load %4 // load pointer from freed memory
}

What I propose is to add a utility function in Types.h

inline bool isNotAliasedIndirectParameter(ParameterConvention conv,
                                          bool assumeInoutIsNotAliasing)

and optimizations, which use this function, must decide if it is safe to pass true in assumeInoutIsNotAliasing. This might be the case for high-level optimizations like COW array opts.
For alias analysis I think we have to go the conservative way.

John, Joe: any comments?

Thanks,
Erik


(Joe Groff) #2

I agree that we can't make a blanket assumption that inout is noalias. Arnold made a similar conclusion last year, so I think we already treat them as aliasing. IRGen won't apply the LLVM noalias attribute to inout parameters, for instance. It's probably better to target `inout` with specific known-acceptable optimizations (load forwarding, writeback elimination, transforming to input-result pair, etc.) than generally treating it as noalias.

-Joe

···

On Dec 17, 2015, at 2:34 PM, Erik Eckstein via swift-dev <swift-dev@swift.org> wrote:

Hi,

I'm currently working on improving alias analysis in the optimizer and I run into following problem:

If alias analysis assumes that inout may not alias any other object, we may violate memory safety. Note that currently it's not always assumed, e.g. not in computeMemoryBehavior for apply insts.

As I understood, if the inout rule is violated, the program is not expected to behave as intended, but is still must be memory safe.
For this reason we had to insert explicit checks for inout violations in the stdlib, e.g. in ArrayBuffer: _precondition(_isNativeTypeChecked == wasNativeTypeChecked, "inout rules were violated: the array was overwritten")

Now with improved alias analysis and assuming inout-no-alias, the optimizer (specifically redundant load elimination) may eliminate these precondition checks in the stdlib.
And I can think of other cases, e.g.

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %3 = load %1
  %4 = ref_element_addr %3
  %ptr = load %4
}

Redundant load elimination may optimize this to

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %4 = ref_element_addr %2
  %ptr = load %4 // load pointer from freed memory
}

What I propose is to add a utility function in Types.h

inline bool isNotAliasedIndirectParameter(ParameterConvention conv,
                                          bool assumeInoutIsNotAliasing)

and optimizations, which use this function, must decide if it is safe to pass true in assumeInoutIsNotAliasing. This might be the case for high-level optimizations like COW array opts.
For alias analysis I think we have to go the conservative way.

John, Joe: any comments?


(John McCall) #3

Right.

John.

···

On Dec 17, 2015, at 2:48 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Dec 17, 2015, at 2:34 PM, Erik Eckstein via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Hi,

I'm currently working on improving alias analysis in the optimizer and I run into following problem:

If alias analysis assumes that inout may not alias any other object, we may violate memory safety. Note that currently it's not always assumed, e.g. not in computeMemoryBehavior for apply insts.

As I understood, if the inout rule is violated, the program is not expected to behave as intended, but is still must be memory safe.
For this reason we had to insert explicit checks for inout violations in the stdlib, e.g. in ArrayBuffer: _precondition(_isNativeTypeChecked == wasNativeTypeChecked, "inout rules were violated: the array was overwritten")

Now with improved alias analysis and assuming inout-no-alias, the optimizer (specifically redundant load elimination) may eliminate these precondition checks in the stdlib.
And I can think of other cases, e.g.

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %3 = load %1
  %4 = ref_element_addr %3
  %ptr = load %4
}

Redundant load elimination may optimize this to

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %4 = ref_element_addr %2
  %ptr = load %4 // load pointer from freed memory
}

What I propose is to add a utility function in Types.h

inline bool isNotAliasedIndirectParameter(ParameterConvention conv,
                                          bool assumeInoutIsNotAliasing)

and optimizations, which use this function, must decide if it is safe to pass true in assumeInoutIsNotAliasing. This might be the case for high-level optimizations like COW array opts.
For alias analysis I think we have to go the conservative way.

John, Joe: any comments?

I agree that we can't make a blanket assumption that inout is noalias. Arnold made a similar conclusion last year, so I think we already treat them as aliasing. IRGen won't apply the LLVM noalias attribute to inout parameters, for instance. It's probably better to target `inout` with specific known-acceptable optimizations (load forwarding, writeback elimination, transforming to input-result pair, etc.) than generally treating it as noalias.


(Jordan Rose) #4

Do we really preserve memory safety today? It seems like any optimizations we might do could lead to half an object getting written, which can result in memory unsafety if that object is implemented using UnsafePointer (like *cough* Array).

Jordan

···

On Dec 17, 2015, at 14:48, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Dec 17, 2015, at 2:34 PM, Erik Eckstein via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Hi,

I'm currently working on improving alias analysis in the optimizer and I run into following problem:

If alias analysis assumes that inout may not alias any other object, we may violate memory safety. Note that currently it's not always assumed, e.g. not in computeMemoryBehavior for apply insts.

As I understood, if the inout rule is violated, the program is not expected to behave as intended, but is still must be memory safe.
For this reason we had to insert explicit checks for inout violations in the stdlib, e.g. in ArrayBuffer: _precondition(_isNativeTypeChecked == wasNativeTypeChecked, "inout rules were violated: the array was overwritten")

Now with improved alias analysis and assuming inout-no-alias, the optimizer (specifically redundant load elimination) may eliminate these precondition checks in the stdlib.
And I can think of other cases, e.g.

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %3 = load %1
  %4 = ref_element_addr %3
  %ptr = load %4
}

Redundant load elimination may optimize this to

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %4 = ref_element_addr %2
  %ptr = load %4 // load pointer from freed memory
}

What I propose is to add a utility function in Types.h

inline bool isNotAliasedIndirectParameter(ParameterConvention conv,
                                          bool assumeInoutIsNotAliasing)

and optimizations, which use this function, must decide if it is safe to pass true in assumeInoutIsNotAliasing. This might be the case for high-level optimizations like COW array opts.
For alias analysis I think we have to go the conservative way.

John, Joe: any comments?

I agree that we can't make a blanket assumption that inout is noalias. Arnold made a similar conclusion last year, so I think we already treat them as aliasing. IRGen won't apply the LLVM noalias attribute to inout parameters, for instance. It's probably better to target `inout` with specific known-acceptable optimizations (load forwarding, writeback elimination, transforming to input-result pair, etc.) than generally treating it as noalias.


(Dave Abrahams) #5

Hi,

I'm currently working on improving alias analysis in the optimizer and I run into following problem:

If alias analysis assumes that inout may not alias any other object, we may violate memory safety. Note that currently it's not always assumed, e.g. not in computeMemoryBehavior for apply insts.

As I understood, if the inout rule is violated, the program is not expected to behave as intended, but is still must be memory safe.
For this reason we had to insert explicit checks for inout violations in the stdlib, e.g. in ArrayBuffer: _precondition(_isNativeTypeChecked == wasNativeTypeChecked, "inout rules were violated: the array was overwritten")

Now with improved alias analysis and assuming inout-no-alias, the optimizer (specifically redundant load elimination) may eliminate these precondition checks in the stdlib.
And I can think of other cases, e.g.

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %3 = load %1
  %4 = ref_element_addr %3
  %ptr = load %4
}

Redundant load elimination may optimize this to

sil @test(@inout %1 : $*C) {
  %2 = load %1
  apply inout_violating_function // replaces *%1 and releases the original *%1.
  %4 = ref_element_addr %2
  %ptr = load %4 // load pointer from freed memory
}

What I propose is to add a utility function in Types.h

inline bool isNotAliasedIndirectParameter(ParameterConvention conv,
                                          bool assumeInoutIsNotAliasing)

and optimizations, which use this function, must decide if it is safe to pass true in assumeInoutIsNotAliasing. This might be the case for high-level optimizations like COW array opts.
For alias analysis I think we have to go the conservative way.

John, Joe: any comments?

I agree that we can't make a blanket assumption that inout is noalias. Arnold made a similar conclusion last year, so I think we already treat them as aliasing. IRGen won't apply the LLVM noalias attribute to inout parameters, for instance. It's probably better to target `inout` with specific known-acceptable optimizations (load forwarding, writeback elimination, transforming to input-result pair, etc.) than generally treating it as noalias.

Do we really preserve memory safety today?

Modulo bugs, yes. Those are the intended semantics.

···

Sent from my moss-covered three-handled family gradunza

On Dec 17, 2015, at 4:52 PM, Jordan Rose via swift-dev <swift-dev@swift.org> wrote:

On Dec 17, 2015, at 14:48, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Dec 17, 2015, at 2:34 PM, Erik Eckstein via swift-dev <swift-dev@swift.org> wrote:

It seems like any optimizations we might do could lead to half an object getting written, which can result in memory unsafety if that object is implemented using UnsafePointer (like *cough* Array).

Jordan

_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev