Compression of values with known bits to aid scheduler
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
If some node `n` has known bits under a ternary analysis, it doesn't ever hurt to replace it with something like `concat(literal(...), bit_slice(n, ...), literal(...))`, where the `literal`s contain the known bits. Since the result of the `bit_slice` contains fewer bits, and `bit_slice` and `concat` and `literal` all have zero delay, this transformation always helps the scheduler reduce flops. This will make the IR more messy, so probably it makes sense to run this pass right before scheduling, and then after scheduling apply another pass that cleans up any unused `bit_slice/concat/literal` bundles so the generated code isn't too messy. Implications from the BDD analysis could also be used for further compression (e.g.: if bit X implies bit Y and bit Y implies bit X, then we can omit bit Y and then copy it back in from X), though those could create fanout that has nonzero area cost.
We could do a similar transform using range analysis, by taking the convex hull of the intervals and subtracting off the lower bound. However, this involves adding nodes that actually have delay (two adders), so it will not always be beneficial. Probably this version is more sensibly done as a separate pass after scheduling, where we determine if any edges that traverse pipeline stage boundaries would benefit from this, and then apply the optimization to just those edges.
Contributor guide
Assessment
This issue has not been assessed yet.