Make `ApplyInst` a `MultipleValueInstruction`?

Development Compiler
,
1

Context

SIL supports instructions that produce multiple values (i.e. multiple result SILValues).

However, apply instructions don't produce multiple values. Instead, they produce a single value, which may have a tuple type. This leads to much avoidable destructuring and restructuring of tuples, which complicates SIL transformations like autodiff:

// example.swift
@_silgen_name("foo")
func foo() -> (Int, Int) {
  (0, 0)
}

@_silgen_name("bar")
func bar() -> (Int, Int) {
  return foo()
}

$ swiftc -emit-silgen example.swift
sil hidden [ossa] @bar : $@convention(thin) () -> (Int, Int) {
bb0:
  %0 = function_ref @foo : $@convention(thin) () -> (Int, Int)
  %1 = apply %0() : $@convention(thin) () -> (Int, Int)
  (%2, %3) = destructure_tuple %1 : $(Int, Int) // this is not good
  %4 = tuple (%2 : $Int, %3 : $Int)
  return %4 : $(Int, Int)
}

Motivation

Here are utilities that can be cleaned up if ApplyInst produces multiple values:

Questions

  • It's my understanding is that this design is because MultipleValueInstruction infra was added after ApplyInst. Is this true?

  • Since SIL does not promise compatibility, can we change ApplyInst to inherit MultipleValueInstruction? What's the bar for accepting this change (e.g. all tests pass, code generation is unchanged after the change)?

I went ahead and filed an issue tracking this internal cleanup, feel free to modify it:

https://bugs.swift.org/browse/SR-13903

@Michael_Gottesman

1 Like
2

Hot take? It can be simpler to avoid tuple types in IRs. I believe JAX made this change ~a year ago to Jaxprs (their IR).

It's better to support operations that return multiple results. This guarantees that all values are not tuple-y (except the empty tuples).

Edit: @jekbradbury from JAX shared these insights:

  • "Detuplication" in JAX led to a bunch of simplifications: in the IR itself, and in producers and consumers of the IR.
  • "The only downside" is that control flow primitives (e.g. higher-order functions like scan) have flatter and less memorable signatures than they did when they could use tuples.
3

@Andrew_Trick @Erik_Eckstein

Thanks for bringing this up! Actually there is a bigger history here. Originally SIL had multiple instruction results. There was a lot of horrible code written that did not handle multiple instruction results correctly. At the time we did not have any need for multiple instruction results, So rather than fix that it was decided that we were going to rip out multiple instruction results from SIL. This was done and a bunch of bugs were fixed. Eventually we realized that we actually needed this functionality for destructures and co-routines, so we put support back in, but we added the minimum support necessary so that we could use it where we needed to. Changing ApplyInst in this way is going to involve I think adding support for MultipleValueInstruction to many more parts of the compiler.

That being said:

  1. Adding more support for MultipleValueInstruction to the compiler is good!
  2. ApplyInst is still how it was from that first transition from multiple instruction results -> single instruction results. It originally had multiple results IIRC.
  3. The main challenge here is going to be adding support for MultipleValueInstruction in a bunch of passes in the compiler and making sure things do not regress as a result of the change.
  4. The only reason that I don't think this has been done is that it is a medium sized project since it would involve touching a bunch of code and no one has had time.

The main question I think is how to stage it in without disrupting the rest of the project. What are your thoughts on that @dan-zheng. My main concern would be that one large patch with a flag day will make the change really hard to review. Instead I wonder if we could stage it in like this:

  1. Change ApplyInst to a MultipleValueInstruction... but only have SILGen emit ApplyInst's with a single result and leave in the tuple extraction codegen. Then the underlying codegen doesn't change and even Textual SIL is unchanged (IIRC we don't () around multiple instruction result arrays with a single value). And you can then use that to discover the passes/IRGen/etc that need to be updated. The main thing will be changing APIs that only accept SingleValueInstruction to instead accept SILInstruction. I would look for any place where code assumes a single value instruction and then does a pattern match against AppllyInst. These will start to fail after this change. The best part is since you are using SILInstruction, these changes can be committed without changing how SILGen emits code! You can also add support for destructure in certain places to add more tests if you want.

  2. Then change SILGen to emit the ApplyInst's with multiple instruction results and eliminate the tuple extraction codegen. This is going to cause more SIL tests to fail and will probably require a bunch of test updates. But if one did the first part right, it should be significantly easier since one has taken care of a lot of the pass updates early. Also most likely one will be familiar with the passes that need to be updated due to the work one did in part 1.

Your thoughts?

1 Like
4

Thanks for sharing the history and design rationale, that is quite illuminating.

I think y'all are the experts and reviewers, so you probably know best. The two steps you described make sense to me:

  1. Change definition: make ApplyInst a MultipleValueInstruction.
    • Fix obvious compilation errors in the compiler codebase. Fix as many tests as possible.
  2. Update and fix users: SIL generation + parsing + verification + printing, analyses and transformations, IRGen.
5

The biggest source of complexity in lowering SIL "opaque" values to SIL addresses is that applies generate fake tuples, which, unlike any other SILValue, cannot have an in memory representation. Working around that issue obscures the basic design. It would be a big help to finally get those applies properly multi-valued.

1 Like