XLS optimizer can maybe transform sequential multiplies into adds
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 12h
- Merged PRs (30d)
- 130
Description
For array updates written in DSLX like
```
let a = for(i, o): (u32, u32[5]) in range(u32:0, u32:5) {
val = i * x
update(o, i, val)
} ( u32[5]:[0, ...]);
```
which initializes an array to [0, x, 2*x, 3*x, 4*x, 5*x]. The corresponding IR becomes something like
```
val0 = 0
val1 = x
val2 = umul(x, 2)
val3 = umul(x, 3)
val4 = umul(x, 4)
a = array_update(a, 0, val0)
a = array_update(a, 1, val1)
a = array_update(a, 2, val2)
a = array_update(a, 3, val3)
```
depending on the cost of the multiplies vs adds vs whether or not this is part of the critical path of the block, this can be instead realized by additions alone, transforming the parallel multiplies into a chain of adds.
```
val0 = 0
val1 = x
val2 = val1 + x
val3 = val2 + x
val4 = val3 + x
a = array_update(a, 0, val0)
a = array_update(a, 1, val1)
a = array_update(a, 2, val2)
a = array_update(a, 3, val3)
```
This issue is to enhance XLS to be able to perform that analysis and choose the alternative structure when it makes sense.
This issue could also be addressed by understanding the structure of multiplies as a sequence of shifts and adds and then performing some sort of datapath synthesis on the result in order to generate a CSA tree that in parallel computes val2, val3, and val4.
Contributor guide
Research direction
No files, tests, or entry points are named. Start by locating the XLS optimizer logic for sequential array updates and multiply rewrites, then study how cost and critical-path decisions are represented. Done means the optimizer can recognize the shown pattern, select an addition-based structure when beneficial, and validate the resulting IR and hardware behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100