google / google/xls

Channel size optimizations

Open
#573 1 comment 0 reactions 0 assignees View on GitHub
good first issue optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

Currently, we have no optimizations that affect the size of data travelling over a channel. In the presence of proc inlining such optimizations may cover some of the benefit of the optimizations in #561. In other multiproc implementation strategies, this can reduce the widths of FIFOs. Examples:

1. If the set of values sent over a given channel has size one, replace that channel with a single-bit channel.
2. Use range or ternary analysis to figure out the set of possible values sent over a given channel, and narrow it before sending and then unnarrow after receiving.
3. Use BDD analysis to find redundant bits in the values sent over the channel.
4. Find tagged union type data structures in the values sent over the channel. For example, if the channel has type `(bits[1], bits[32], bits[64])` and when the `bits[0]` element is `0` the `bits[64]` is always 0, and when the `bits[0]` element is `1` the `bits[64]` is always 0, this can be reduced to `(bits[1], bits[64])` where the `bits[32]` is sliced out of the `bits[64]` when it is nonzero. Simply supporting anonymous unions could be easier than doing this analysis, though it would only help in the case of the DSLX frontend, which does not support ADTs yet.

Doing this work interprocedurally before proc inlining has the benefit of doing less work overall, but the detriment of requiring more conservatism around any static analyses done.

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.