Proposal: Opaque SIL values


(Andrew Trick) #1

I’m sending out a proposal for fundamentally changing SIL. This work feeds into generic code optimization, resilience, semantic ARC, and SIL ownership. This was discussed at length back in October—some info went out on swift-dev—but I realized there hasn’t been a formal proposal. So here it is. I want to make sure enough people have seen this before pushing my PR that puts the infrastructure in place: https://github.com/apple/swift/pull/6922.

Rendered Proposal: https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7

Markdown:

-Andy

silval-proposal-1.md (11.8 KB)


(Chris Lattner) #2

This is great Andy, thanks for pushing it forward. One question: are you concerned at all that the SSA representation of address only values will make it “too easy” for the optimizer to reorder instruction such that a lot more temporary values will been needed in lowering?

-Chris

···

On Jan 24, 2017, at 11:10 AM, Andrew Trick via swift-dev <swift-dev@swift.org> wrote:

I’m sending out a proposal for fundamentally changing SIL. This work feeds into generic code optimization, resilience, semantic ARC, and SIL ownership. This was discussed at length back in October—some info went out on swift-dev—but I realized there hasn’t been a formal proposal. So here it is. I want to make sure enough people have seen this before pushing my PR that puts the infrastructure in place: https://github.com/apple/swift/pull/6922.

Rendered Proposal: https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7' <https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7'>


(Joe Groff) #3

Looks great. One nitpick:

Naturally, opaque types must limit some optimizations, such as inlining.

I don't see how opaque types by themselves prevent inlining. You can inline a generic into another generic, or a function using a resilient type into another function.

This would hide part of the ABI from SIL. However, reabstraction must be exposed to SIL. Doing so simplifies IRGen, allows the SIL optimizer to improve code within thunks, and allows the SIL optimizer can perform function signature optimizations across calls.

Perhaps in the future, we could delay the lowering of reabstraction as well to a late lowering pass. Many times, inlining and specialization eliminate the need for reabstractions by eliminating the call boundaries and generic abstraction shifts, and it would be nice not to have to clean up these unnecessary reabstractions by never emitting them in the first place.

-Joe


(Karl) #4

I won’t pretend to understand all of the implications of this, but as a newcomer to the codebase I found SILGen (particularly lowering) extremely confusing to unpick.

The simplification and separation described here makes a lot of sense to me, and I believe it would make it easier for myself and others to contribute to the project. As do your comments in the PR about using consistent idioms throughout the compiler.

So as far as those things are considerations, I’m really happy with this proposal.

- Karl

···

On 24 Jan 2017, at 20:10, Andrew Trick via swift-dev <swift-dev@swift.org> wrote:

I’m sending out a proposal for fundamentally changing SIL. This work feeds into generic code optimization, resilience, semantic ARC, and SIL ownership. This was discussed at length back in October—some info went out on swift-dev—but I realized there hasn’t been a formal proposal. So here it is. I want to make sure enough people have seen this before pushing my PR that puts the infrastructure in place: https://github.com/apple/swift/pull/6922.

Rendered Proposal: https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7

Markdown:
<silval-proposal-1.md>

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


(John McCall) #5

We've already talked about this at length, so I just want to say for the record that it looks great, and thanks for taking this on.

What's the purpose of SILFunctionConventions? To provide a context with which to interpret the information in SILFunctionType?

John.

···

On Jan 24, 2017, at 2:10 PM, Andrew Trick via swift-dev <swift-dev@swift.org> wrote:
I’m sending out a proposal for fundamentally changing SIL. This work feeds into generic code optimization, resilience, semantic ARC, and SIL ownership. This was discussed at length back in October—some info went out on swift-dev—but I realized there hasn’t been a formal proposal. So here it is. I want to make sure enough people have seen this before pushing my PR that puts the infrastructure in place: https://github.com/apple/swift/pull/6922.

Rendered Proposal: https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7

Markdown:
<silval-proposal-1.md>


(Andrew Trick) #6

That would come about when the program wants to use the same lvalue for multiple real values. I don't expect many problems with simple opaque types. The only way to mutate them is either passing them @inout or returning them @out. We could introduce a copy by sinking a use below one of these calls. But the uses are also likely to be calls.

It could happen. The typically annoying case with copy coalescing in general is induction variables that are both modified in the loop and live out of the loop. I wasn't even able to force a scenario like this with Swift opaque values that didn't already generate a copy up front.

There's definitely an issue with all the temporaries needed to inject opaque values into aggregates. Address lowering needs to be smart about this, but I have a straightforward storage allocation algortihm in mind that should take care of the expected cases. I'm anxious to try out a prototype and get some data.

-Andy

···

On Jan 24, 2017, at 8:56 PM, Chris Lattner <sabre@nondot.org> wrote:

On Jan 24, 2017, at 11:10 AM, Andrew Trick via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

I’m sending out a proposal for fundamentally changing SIL. This work feeds into generic code optimization, resilience, semantic ARC, and SIL ownership. This was discussed at length back in October—some info went out on swift-dev—but I realized there hasn’t been a formal proposal. So here it is. I want to make sure enough people have seen this before pushing my PR that puts the infrastructure in place: https://github.com/apple/swift/pull/6922.

Rendered Proposal: https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7' <https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7'>

This is great Andy, thanks for pushing it forward. One question: are you concerned at all that the SSA representation of address only values will make it “too easy” for the optimizer to reorder instruction such that a lot more temporary values will been needed in lowering?

-Chris


(John McCall) #7

Hmm. This is a tricky question. I think we'd want to keep *bridging* early, at least. For other kinds of representation change, delaying them has some benefits, but I wonder if those benefits are significant once we have an SSA representation, because that will enable us to also have a "reabstract" instruction which will make the peepholes basically trivial.

John.

···

On Jan 25, 2017, at 9:13 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
Looks great. One nitpick:

Naturally, opaque types must limit some optimizations, such as inlining.

I don't see how opaque types by themselves prevent inlining. You can inline a generic into another generic, or a function using a resilient type into another function.

This would hide part of the ABI from SIL. However, reabstraction must be exposed to SIL. Doing so simplifies IRGen, allows the SIL optimizer to improve code within thunks, and allows the SIL optimizer can perform function signature optimizations across calls.

Perhaps in the future, we could delay the lowering of reabstraction as well to a late lowering pass. Many times, inlining and specialization eliminate the need for reabstractions by eliminating the call boundaries and generic abstraction shifts, and it would be nice not to have to clean up these unnecessary reabstractions by never emitting them in the first place.


(Andrew Trick) #8

Good point. I was just hand-waving here about resilient types, which we can’t inline by design, and archetypes where we can’t inline protocol methods because method resolution requires specialization. But yeah, we should be inlining methods on unbound generic nominal types. I updated the doc.

-Andy

···

On Jan 25, 2017, at 6:13 PM, Joe Groff <jgroff@apple.com> wrote:

Naturally, opaque types must limit some optimizations, such as inlining.

I don't see how opaque types by themselves prevent inlining. You can inline a generic into another generic, or a function using a resilient type into another function.


(Andrew Trick) #9

Thanks. I appreciate the encouragement. I’m actually trying not to add more complexity without offering some way to reason about it.

I added another section to the proposal that offers some background:
https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7#sil-types-and-argument-conventions

...
Here's how this design fits into broader picture of the layers of
abstraction in the type system:

- Formal types: The AST types directly exposed by the language.
  (e.g. `T?`)

- Canonical types: desugared formal AST types.
  (e.g. `Optional<T>`)

- Lowered types: Canonical types in the ASTContext that can be
  directly referenced by SIL. These "formalize" some properties of the
  ABI. For example, they make the ownership and indirection of
  function arguments explicit. These formalized conventions must match
  on both the caller and callee side of every call. Lowered types
  include types that aren't part of the language's formal type
  system. See SILFunctionType. Although these types have been lowered
  for use by SIL, they exist independent of a SILModule.
  (e.g. `@in Optional<T>`)

- SIL types: The actual type associated with a SIL value. These merely
  wrap a lowered type with a flag indicating whether the SIL value
  has indirect SIL semantics. i.e. whether the value is an address or
  an object type. SIL types are part of a SILModule, and reflect the
  SILModule's conventions. Mapping lowered types to SIL types is
  specific to the current SIL stage.
  (`e.g. $Optional<T>`)

- SIL storage types: These are SIL types with lowered addresses. They
  represent the ABI requirements for indirection and storage of SIL
  objects. In the "lowered" SIL stage, the SIL type of every value is
  its storage type. Lowered types directly correspond to SIL storage
  types. For example, if a function parameter has an `@in` lowered type, then
  the storage type of the corresponding SIL argument is an address.
  (`e.g. $*Optional<T>`)

- LLVM types: Represent the ABI requirements in terms of C types. This
  could introduce additional indirection, but I'd like to handle most
  if not all of that in SIL address lowering.
  (e.g. `%Sq* noalias nocapture, %swift.type* %T`)
  
So to recap, if you ask for the SIL type corresponding to a formal
convention, you'll get the SIL *storage* type
(e.g. `$*Optional<T>`). If you ask for the SIL type for a function
argument corresponding to the same formal parameter, you will get the
right level of indirection for the current SIL stage
(e.g. `$Optional<T>`). In short, the lowered type may specify a calling
convention that expects indirect storage, while the SIL type may be
direct.

···

On Jan 25, 2017, at 4:22 PM, Karl Wagner <razielim@gmail.com> wrote:

On 24 Jan 2017, at 20:10, Andrew Trick via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

I’m sending out a proposal for fundamentally changing SIL. This work feeds into generic code optimization, resilience, semantic ARC, and SIL ownership. This was discussed at length back in October—some info went out on swift-dev—but I realized there hasn’t been a formal proposal. So here it is. I want to make sure enough people have seen this before pushing my PR that puts the infrastructure in place: https://github.com/apple/swift/pull/6922.

Rendered Proposal: https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7

Markdown:
<silval-proposal-1.md>

-Andy
_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

I won’t pretend to understand all of the implications of this, but as a newcomer to the codebase I found SILGen (particularly lowering) extremely confusing to unpick.

The simplification and separation described here makes a lot of sense to me, and I believe it would make it easier for myself and others to contribute to the project. As do your comments in the PR about using consistent idioms throughout the compiler.

So as far as those things are considerations, I’m really happy with this proposal.

- Karl


(Andrew Trick) #10

Yes, that’s the motivating factor. SILFunctionTypes are created as part of the ASTContext and I believe they should be immutable. A function's type should never change. SILFunctionConventions is a transient view of that type corresponding to the module’s current conventions.

I hope the separation of APIs also helps make the distinction between lowered types and SIL types. It’s hard for me to even talk about that distinction since they’ve always been the same thing.

-Andy

···

On Jan 26, 2017, at 8:33 AM, John McCall <rjmccall@apple.com> wrote:

On Jan 24, 2017, at 2:10 PM, Andrew Trick via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
I’m sending out a proposal for fundamentally changing SIL. This work feeds into generic code optimization, resilience, semantic ARC, and SIL ownership. This was discussed at length back in October—some info went out on swift-dev—but I realized there hasn’t been a formal proposal. So here it is. I want to make sure enough people have seen this before pushing my PR that puts the infrastructure in place: https://github.com/apple/swift/pull/6922.

Rendered Proposal: https://gist.github.com/atrick/38063a90bf4a6ebae05fe83ea9ebc0b7

Markdown:
<silval-proposal-1.md>

We've already talked about this at length, so I just want to say for the record that it looks great, and thanks for taking this on.

What's the purpose of SILFunctionConventions? To provide a context with which to interpret the information in SILFunctionType?

John.


(Chris Lattner) #11

That would come about when the program wants to use the same lvalue for multiple real values. I don't expect many problems with simple opaque types. The only way to mutate them is either passing them @inout or returning them @out. We could introduce a copy by sinking a use below one of these calls. But the uses are also likely to be calls.

It could happen. The typically annoying case with copy coalescing in general is induction variables that are both modified in the loop and live out of the loop. I wasn't even able to force a scenario like this with Swift opaque values that didn't already generate a copy up front.

Ok, I’m a bit concerned about it, but not strongly enough to try to obstruct this architectural change (which, again, seems like totally the right thing to do). I’m ok with just waiting and seeing, particularly given that other constraints (lack of ability to analyze the generic ops) may prevent the bad thing from happening.

There's definitely an issue with all the temporaries needed to inject opaque values into aggregates. Address lowering needs to be smart about this, but I have a straightforward storage allocation algortihm in mind that should take care of the expected cases. I'm anxious to try out a prototype and get some data.

I’d really love to see new ideas on how to change our modeling of this. The injection model is nice in a lot of ways, but seems overly general and has introduced a lot of complexity in the past.

-Chris

···

On Jan 24, 2017, at 10:58 PM, Andrew Trick <atrick@apple.com> wrote:


(Joe Groff) #12

We can't inline any information about the type layout of a resilient type, but it wouldn't block inlining of functions that use values of the resilient type when we have visibility into their bodies. It doesn't seem right to me to call them out as "not inlinable" when most of the non-inlinable things about them, like layout, value witnesses, and type metadata, are below the abstraction level of SIL.

-Joe

···

On Jan 26, 2017, at 12:45 AM, Andrew Trick <atrick@apple.com> wrote:

On Jan 25, 2017, at 6:13 PM, Joe Groff <jgroff@apple.com> wrote:

Naturally, opaque types must limit some optimizations, such as inlining.

I don't see how opaque types by themselves prevent inlining. You can inline a generic into another generic, or a function using a resilient type into another function.

Good point. I was just hand-waving here about resilient types, which we can’t inline by design, and archetypes where we can’t inline protocol methods because method resolution requires specialization. But yeah, we should be inlining methods on unbound generic nominal types. I updated the doc.