Re: [swift-dev] Proposal: Opaque SIL values

[Andrew Trick via swift-dev]

> On Jan 26, 2017, at 8:33 AM, John McCall  wrote:
> 
>> On Jan 24, 2017, at 2:10 PM, Andrew Trick via swift-dev > > 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:
>> 
> 
> 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.

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___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Proposal: Opaque SIL values

[Joe Groff via swift-dev]

> On Jan 26, 2017, at 12:45 AM, Andrew Trick  wrote:
> 
> 
>> On Jan 25, 2017, at 6:13 PM, Joe Groff  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.

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
___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Proposal: Opaque SIL values

[John McCall via swift-dev]

> On Jan 24, 2017, at 2:10 PM, Andrew Trick via swift-dev  
> 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:
> 

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.___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Proposal: Opaque SIL values

[Andrew Trick via swift-dev]

> On Jan 25, 2017, at 4:22 PM, Karl Wagner  wrote:
> 
> 
>> On 24 Jan 2017, at 20:10, Andrew Trick via swift-dev > > 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:
>> 
>> 
>> -Andy
>> ___
>> swift-dev mailing list
>> 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


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`)

- 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`)

- 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`)

- 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`)

- 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`). 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`). In short, the lowered type may specify a calling
convention that expects indirect storage, while the SIL type may be
direct.

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

Re: [swift-dev] Proposal: Opaque SIL values

[Andrew Trick via swift-dev]

> On Jan 25, 2017, at 6:13 PM, Joe Groff  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.

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

Re: [swift-dev] Proposal: Opaque SIL values

[John McCall via swift-dev]

> On Jan 25, 2017, at 9:13 PM, Joe Groff via swift-dev  
> 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.

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.
___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Proposal: Opaque SIL values

[Chris Lattner via swift-dev]

On Jan 24, 2017, at 10:58 PM, Andrew Trick  wrote:
> 
> 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

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

Re: [swift-dev] Proposal: Opaque SIL values

[Joe Groff via swift-dev]

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
___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Proposal: Opaque SIL values

[Karl Wagner via swift-dev]

> On 24 Jan 2017, at 20:10, Andrew Trick via swift-dev  
> 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:
> 
> 
> -Andy
> ___
> swift-dev mailing list
> 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___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Proposal: Opaque SIL values

[Andrew Trick via swift-dev]

> On Jan 24, 2017, at 8:56 PM, Chris Lattner  wrote:
> 
> 
>> On Jan 24, 2017, at 11:10 AM, Andrew Trick via swift-dev 
>> 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' 
>> 
> 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
> 

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___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Proposal: Opaque SIL values

[Chris Lattner via swift-dev]

> On Jan 24, 2017, at 11:10 AM, Andrew Trick via swift-dev 
>  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' 
> 
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

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

[swift-dev] Proposal: Opaque SIL values

[Andrew Trick via swift-dev]

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/38063a90bf4a6ebae05fe83ea9ebc0b7Markdown:# SIL Opaque Values

# Introduction

A SIL type is either loadable or address-only. A loadable type is one
whose object size and layout can be determined by the compiler *and*
whose values are not "pinned" to a memory address. Types are most
commonly address-only because their layout is opaque by
abstraction. Generic type parameters are address-only because their
concrete type not statically identified. Resilient types are
statically identified, but have opaque layout for binary
compatibility.

Compiled code must access and pass address-only objects via their
memory addresses. We refer to this as "physical" access, as expressed
by LLVM IR. Currently, SIL also reflects physical access. For example,
SIL for a generic function relies on address types:
```
sil @identity : $ (@in T) -> @out T {
bb0(%0 : $*T, %1 : $*T):
  copy_addr %1 to [initialization] %0 : $*T
  destroy_addr %1 : $*T
  %4 = tuple ()
  return %4 : $()
}
```

If the generic type is bound to a loadable type, then the SIL values
are promoted to value types:
```
// generic specialization  of identity  (T) -> T
sil @identity : $(Int) -> Int {
bb0(%0 : $Int):
  return %0 : $Int
}
```

This leads to drastically different SIL patterns in code that is
semantically almost identical. A key aspect of optimizing SIL is
converting values from an in-memory form to an SSA value. Being
address-only currently prevents opaque values from taking part in
normal optimization. Naturally, opaque types must limit some
optimizations, such as inlining. However, an important feature of the
SIL optimizer is copy elimination and by extension ARC operations,
which applies equally to opaque and loadable types.

This SIL code creates an unnecessary local copy:
```
%copy = alloc_stack $T
copy_addr %arg to [initialization] %copy : $*T
...
%ret = apply %callee(%copy) : $@convention(thin) <τ_0_0> (@in τ_0_0) -> ()
...
dealloc_stack %copy : $*T
destroy_addr %arg : $*T
```

The same code expressed in SSA reveals that the copy is redundant:
```
%copy = copy_value %arg : $T
...
%ret = apply %callee(%copy) : $@convention(thin) <τ_0_0> (@in τ_0_0) -> ()
...
destroy_value %arg : $T
```
Redundancy can be inferred from these facts: `%arg` by definition cannot mutate, it is consumed in-scope by a `destroy_value`, and `%arg` is not copied again after `%copy` has been consumed:
 
The address-only property of arguments determines physical calling
conventions in LLVM IR. These conventions cannot be complete hidden
from SIL code. In particular, SIL is responsible for handling
reabstraction of function types. If the caller and callee have
different views of an argument type, then a SIL-level thunk is
required to bridge between the two conventions.

For example, a concrete function may satisfy a protocol with generic
constraints. A protocol witness thunk will be generated to load the
address-only arguments and store address-only results. An extra copy
is also generated to convert a guaranteed self argument to owned:
```
sil @foo : $@convention(method) (Int, S) -> Int {
bb0(%0 : $Int, %1 : $S):
  return %0 : $Int
}

// protocol witness for P.foo (A.T) -> A.T in conformance S : P
sil [thunk] @_TTWV1t1SS_1PS_FS1_3foofwx1TwxS2_
  : $@convention(witness_method) (@in Int, @in_guaranteed S) -> @out Int {
bb0(%0 : $*Int, %1 : $*Int, %2 : $*S):
  %3 = load [trivial] %1 : $*Int
  %4 = load [trivial] %2 : $*S
  %5 = function_ref @foo : $@convention(method) (Int, S) -> Int
  %6 = apply %5(%3, %4) : $@convention(method) (Int, S) -> Int
  store %6 to [trivial] %0 : $*Int
  %8 = tuple ()
  return %8 : $()
}
```

Conceivably, the address-only types in the thunk could be expressed as SSA values. However, the `@in`, `@in_guaranteed` parameter conventions must remain to communicate indirection to the SIL compiler:
```
// protocol witness for P.foo (A.T) -> A.T in conformance S : P
sil [thunk] @_TTWV1t1SS_1PS_FS1_3foofwx1TwxS2_
  : $@convention(witness_method) (@in Int, @in_guaranteed S) -> @out Int {
bb0(%0 : $Int, %1 : $*S):
  %2 = function_ref @foo : $@convention(method) (Int, S) -> Int
  %3 = apply %2(%0, %1) : $@convention(method) (Int, S) -> Int
  return %3 : $Int
}
```

This proposal argues that address-only SIL values should be
represented within SIL function bodies as SSA values, unless SIL
semantics would otherwise require an address even if the value's type
were loadable. SIL parameter and result conventions will continue to
reflect argument indirection. Two SIL function sig