Reorg optimization pipeline
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
In working on https://github.com/google/xls/issues/273 I ran into a number of issues where a sequence of simplifications weren't kicking in because some obfuscating optimization which narrowed or split operations caused the expected pattern matching to fail.
Example desired optimization which is the removal of a superfluous clamp on a shift amount:
```
bits[W]:a << (b > W ? W : b) => a << b
```
This is legal because shifting by an amount greater than the bit width produces the same result as shifting by the bit width. However, some other optimization was kicking in which sliced and diced the expression "b > W" because the optimizer saw that b and W share common bits.
A solution I'm thinking of is to roughly group optimizations into three categories:
1. generally removes operations, or replaces with equivalent number of operations. Examples: a+0 => a, a*4 => a<<2. Most arithmetic operations fall in this category. Operations remain "whole" not sliced in anyway.
2. operations which narrow operations with slices, and optimizations which result in net increase of node count. Examples: a << C => concat(slice(a), 0), narrowing add if all lsb are zero, etc.
3. operations which explode operations into constituent bits, or potentially small slices of bits. This category is already broken out and enabled only when split_ops is true in the standard pipeline.
The optimization pipeline would run optimizations of type (1) together to fixed point, then optimizations of type (1) and (2) together to fixed point, then optimizations of type (1), (2) and (3) together to fixed point.
Contributor guide
Assessment
This issue has not been assessed yet.