swift234

SILGen: Match switches with tuples, wildcard patterns, and guards.

Lay the groundwork for the pattern matching compilation algorithm from Luc Maranget's "Compiling Pattern Matching to Good Decision Trees". This algorithm organizes the set of patterns to consider into a "clause matrix", where each row corresponds to a pattern and its branch destination, and each column is a destructured subelement of the pattern. The algorithm heuristically chooses a "necessary column"  on which to reduce the matrix; for that column, specialized matrices are generated for each constructor form in the column, which are then recursively considered until we reach a termination case where a matrix either has no rows, in which case the match fails, or a matrix's top row always succeeds, in which case we emit a leaf branch to that target.

For this initial version, we stick only to matching tuples and wildcards in naive left-to-right order. We modify the algorithm from the paper to also handle guards: if the first row in the clause matrix is all wildcards, then instead of unconditionally branching to the destination, we evaluate the guard and conditionally branch to the target; on the false branch, we proceed with Maranget's algorithm by removing the guarded row from the matrix.

We don't yet implement variable bindings, ExprPatterns, "is" patterns, or nominal type patterns.

Swift SVN r5993