google / google/xls

[idea] For exhaustive matches, should we expose the construct to the IR?

Open
#1,920 2 comments 0 reactions 0 assignees View on GitHub
ir long-term-enhancement optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

Filing for discussion -- I was thinking that for the match construct in DSLX -- e.g. imagine one that doesn't have a trailing wildcard arm -- we know that the coverage of arms is exhaustive because we've done a small proof of it in the type system. Following that, we place the last arm's expression in the "default value" position for a select op during IR conversion, while the other arms have equality/range tests (or compound equality/range tests) that guide whether they're selected.

The fact that the earlier arms have equality/range tests and the last arm doesn't need to compute any associated predicate seems gives an opportunity to reorder the arms so that the most costly predicate is the one that we don't need to compute. e.g. imagine one arm that had lots of range comparisons which are effectively comparisons, you may want to place the costliest one in the "default" position if the patterns for the arms were disjoint. Both proving disjointness of the arms and swizzling the arms around based on cost seems like potential opportunities for the IR if we kept the match-like construct in tact somehow.

Not very crisp in identifying the potential opportunity I know, but wanted to jot it down. Relates to recent discussion in #1913 cc @meheff

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.