Subject: [PATCH] Make better use of the switch op in cond forms
From: Mattias Engdegård <[email-masked]>
To: [email-masked]
Cc: Stefan Monnier <[email-masked]>
Date: Sat, 8 Jun 2019 16:40:07 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

Currently, `cond' forms will only use a switch op under very specific circumstances, which limits their potential utility: every condition must be a scalar comparison (eq, eql or equal) between a variable and a constant; the same variable and the same test function must be used everywhere. These restrictions also limit the generation of switch ops from `pcase' and `cl-case' constructs.

In actual `cond' forms, scalar comparisons are mixed with multi-value ones (memq, memql, member); different comparisons are mixed, since the type of values can vary at runtime. There are also non-switch comparisons thrown into the same `cond' for convenience, typically at the beginning or end. Occasionally, there are even multiple switch-like sequences against different variables in the same cond.

Attached is a set of patches which gradually eliminate many of these restrictions. Each patch makes a fixed and hopefully easily-reviewed improvement. Short overview:

* 0001-Compile-list-member-functions-in-cond-to-switch.patch

Allow memq, memql and member to be used in switch generation, since these are idiomatically used for multiple values with the same body. They are also used by `pcase' and `cl-case'. For example,

 (cond ((eq x 'a) 11)
       ((memq x '(b c d)) 22))

will generate a single switch as if the code had been

 (cond ((eq x 'a) 11)
       ((eq x 'b) 22)
       ((eq x 'c) 22)
       ((eq x 'd) 22))

- that is, the byte code for the body (22) will be generated thrice.

* 0002-Share-identical-switch-clause-bodies.patch

An improvement of the above to share the body byte code between all values of the same `cond' clause. This means that the switch jump table is no longer an injective mapping.

* 0003-Tighter-pcase-or-pattern-member-function-selection.patch

Make `pcase' use the most specific comparison function (memq instead of memql, etc) in each case, depending on the values.
This patch is technically independent of the other ones, but improves code generation for `pcase'.

* 0004-Compile-cond-with-heterogeneous-tests-into-switch.patch

Allow switch generation with a mixture of eq, eql, equal, memq, memql and member.

* 0005-Compile-any-subsequence-of-cond-clauses-to-switch.patch

Generalise the code to produce switch ops for any switch-like part of a `cond' form. These switches can use different variables, and there can be any number of non-switch clauses before, after and between the switch clauses.

Performance: The patch set is loosely monotonous with the assumptions already present, in the sense that if the current code generator does not produce slower code in any case, nor is it expected to do so after the patches have been applied. In practice, micro-benchmarks naturally show the expected gains, but I haven't found much real-world code that is easy enough to benchmark. Some unpublished tree-traversal code improved about 7 %.