google / google/xls

Fuzzy CSE matching

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

Description

This may be captured else where, but there's a general idea of an optimization like "fuzzy-tradeoff sharing".

In traditional compiler passes you CSE (common subexpression eliminate) exact matches in operations. In hardware, however, you could "fuzzy match" and just mask off wires, e.g. imagine a 4 bit adder and a 5 bit adder, you could reuse one unit instead of specializing for both, given they have the same operands.

E.g. an example @grebe just gave: `a + b` vs `a[3:0] + b[3:0]`.

(From there, you could generalize to "different operands", but that requires proof of mutual exclusion if you're going to reuse structural operator resources as in the resource binding problem. There's a simpler version with the same operands that doesn't require exclusivity.)

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.