Optimize desugaring of match expressions

[ironcev]

This issue calls for implementation of a runtime efficient desugaring of match expressions. The proposal is to combine and to adapt to Sway:

• the pattern-matching compiler as explained in the Chapter 5 of "The Implementation of Functional Programming Languages"
• and the concept of join points as explained in the paper "Compiling without continuations"

Such combination was successfuly implemented by @vaivaswatha in the Scilla programming language:

• https://github.com/Zilliqa/scilla-compiler/blob/master/src/astlowering/FlattenPatterns.ml

The goal of the proposal is not change the existing desugaring approach and not to introduce desugaring specific AST nodes. We will still desugar to if-else structure using only the regular Sway language features.

Motivation

Currently we desugar match expressions into a straightforward if-else chain. This desugaring is inefficient at runtime. Consider the following example:

match e {
    Enum::A(11) => 1011,
    Enum::B(11) => 2011,
    Enum::A(22) => 1022,
    Enum::B(22) => 2022,
    Enum::A(_) => 1099,
    Enum::B(_) => 2099,
};

The desugared expression will be semantically equivalent to this pseudo-Sway code:

let __match_val = e;
if (__match_val is Enum::A) && (__match_val as u64) ==  11 {
    1011
}
else if (__match_val is Enum::B) && (__match_val as u64) ==  11 {
    2011
}
else if (__match_val is Enum::A) && (__match_val as u64) ==  22 {
    1022
}
else if (__match_val is Enum::B) && (__match_val as u64) ==  22 {
    2022
}
else if (__match_val is Enum::A) {
    1099
}
else if (__match_val is Enum::B) {
    2099
}
else {
  ... // Not relevant for the topic of optimization.
}

It is obvious that the original match expression can be more efficiently desugared into form in which each variant is scrutinized and casted only once:

let __match_val = e;
if (__match_val is Enum::A) {
   let __val = __match_val as u64;
   if __val == 11 {
      1011
   }
   if __val == 22 {
      1022
   }
   else {
      1099
   }
}
else (__match_val is Enum::B) {
  ... // Similar for Enum::B
}
else {
  ... // Not relevant for the topic of optimization.
} 

The pattern-matching compiler explained in the Chapter 5 of "The Implementation of Functional Programming Languages" provides a general algorithm for a similar optimization of an arbitrary match expression.

Join Points

Applying the algorithm as it is can lead to unwanted duplication of nodes in the generated code. An obvious example are OR match arms in Sway that can simply be treated as separate arms. E.g.

match e {
    Enum::A | Enum::B => <some complex code>,
    Enum::C | Enum::D => <some other complex code>,
    _ => <some default complex code>,
};

will be seen by the algorithm as:

match e {
    Enum::A => <some complex code>,
    Enum::B => <some complex code>,
    Enum::C => <some other complex code>,
    Enum::D => <some other complex code>,
    _ => <some default complex code>,
};

The end result of the optimized desugaring will contain duplicated code.

Note that this code duplication also happens even if we do not have OR match arms. E.g.

match e {
    Enum::A(11) => 1011,
    Enum::B(22) => 2022,
    _ => <some default complex code>
};

This will be desugared into:

let __match_val = e;
if (__match_val is Enum::A) {
   let __val = __match_val as u64;
   if __val == 11 {
      1011
   }
   else {
      <some default complex code>
   }
}
else (__match_val is Enum::B) {
   let __val = __match_val as u64;
   if __val == 22 {
      2022
   }
   else {
      <some default complex code>
   }
}
else {
      <some default complex code>
} 

The concept of join points as explained in the paper "Compiling without continuations" explains how the code duplication can be replaced by function calls of a special join semantics. In the Scilla programming language the joins were implemented by jumps to code locations called join points.

Proposal

At the moment we do not support local functions, but we discussed to support them. Proposal is to implement local functions first, and then (re)use them as join points. Such local functions can be even flagged as join points so that their join points semantics is further preserved in optimizations as described in the paper. But otherwise, they would be just regular local functions.

The obvious benefit of this approach is elimination of need for a separate construct of joint point and jumps to join points that would need to be considered in AST, analysis, etc. Jumping to a join point would be just a regular local function call.

In the above example, the final elses:

else {
  <some default complex code>
}

would become:

else {
  __fun_some_default_complex_code(...)
}
...
fn __fun_some_default_complex_code(...) -> u64 { // Local function.
  <some default complex code>
}

[vaivaswatha]

The goal of the proposal is not change the existing desugaring approach and not to introduce desugaring specific AST nodes. We will still desugar to if-else structure using only the regular Sway language features.

So we won't be translating it to jumps? but just a more efficient form of if-else structures. Maybe do the entire de-sugaring later in the compiler but translate to jumps then?

Other than this, it looks good to me !.

[ironcev]

So we won't be translating it to jumps? but just a more efficient form of if-else structures.

I pondered about this a lot. Right now we do not have a dedicated layer like MIR in Rust that has on one side less concepts and on the other side additional concepts not existing in the language itself (e.g. no loops, but gotos in addition and switches, ...) and is optimal for optimizations that can be done above IR level.

Introducing jumps on the AST level would make sense if we had something like MIR. In that case I would expect having other constructs there that simplify code constructs and turning it into a form easier to optimize. Actually we would be talking about adding jumps to MIR.

And doing it later in the compiler would mean the later stages need to know the match expression construct which is now not the case since they get regular ifs.

That's why this approach looked to me as the most fitting in regard to our current architecture. We desugar the match expression to already efficient if-else structure and still allow further optimizations of that structure down the chain.

[ironcev]

Hmmm, revoking my thoughts and rethinking it 🤔 Our IR is MIR. Which means we could bring match expressions all the way down to it and do the jumps there.

I am open to both approaches.

[vaivaswatha]

Hmmm, revoking my thoughts and rethinking it 🤔 Our IR is MIR. Which means we could bring match expressions all the way down to it and do the jumps there.

I am open to both approaches.

My vote is for translating to jumps if we can. I'm guessing that if we do that, we'll need a switch construct in the IR, similar to LLVM's switch. Since the IR and asm-gen infrastructure doesn't have that yet, we will need to do this whole optimization under a compiler flag. Until the support is there, the flag should default to have it generate if-else and not switch, so that we have some time and space to support the IR / asm-gen parts.

[ironcev]

I'm guessing that if we do that, we'll need a switch construct in the IR

Yes we will need switch in that case.

Until the support is there, the flag should default to have it generate if-else and not switch,

IMO there is no rush here. Even with the approach of optimizing if-elseconstructs I am for waiting until we have local functions. I would first fix the known issues in the steps that anyhow precede the desugaring/optimization and implement the optimization afterwards, using the approach we agree on. Thus IMO no need for the flag, just agreement on the steps and the approach.

[ironcev]

To sum up the discussion so far, we have two options with different tradeoffs:

1) Stay on the current path and desugar match expression into if-else and other constructs already available in the language (assuming we want to have local functions one day). Optimize the if-else constructs on this level (with further optimizations on the IR level, but those are not aware of switch expressions). 2) Leave match expression as it is without desugaring and translate it into optimized chains of IR's switches.

Option 1) means there is no need to change the analysis that comes after the type-checking phase. It is still only ifs. There are no changes in the IR either. The drawback is I guess the lack of possible further optimizations on the IR level that we would have if switch were there.

Option 2) is exactly the opposite, with the effort on both analysis and IR side.

Out of my current knowledge about IR and analysis which is very thin on both sides I cannot judge the tradeoffs (looking forward to more learning about those part of Sway!).

@vaivaswatha @tritao if you could provide more info that would be great.

[vaivaswatha]

@ironcev Your summary seems about right to me. I don't have anything much to add. If we decide to go down Option 2, please create a new Issue to track switch support in the IR and assign it to me.

[tritao]

Good summary about our options here @ironcev, I don't really have any strong opinions on which approach to take either, seems like both are good options.

Option 2 would probably be a bit cleaner since we could generate more optimized code out of the gate (making the assumption here that Option 1 code would need to run through the optimization passes to reach the same level of optimization).

And the other thing that comes to mind is that going with option 1. might allow in the future to target some higher-level laguages from Sway that don't provide unconditional jumps, but I don't think that's even on the scope of Sway at the moment so not really a concern.

So all in all I would probably go with the one you think would be less complex to implement.

[ironcev]

Thanks for the feedback @vaivaswatha @tritao! Let's sleep over it and see. In the first step I want to fix the open issues that we have in the phases that precede the desugaring/optimization.