Opportunistically reverse select chain order
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
Identified by @hongted
xlscc generates select chains which might be more efficiently expressed if the order of the chain is reversed. Example input:
```c++
result = ...
if (a) {
result = A;
} else if (b) {
result = B;
} else if (c) {
result = C;
} else {
result = D;
}
```
This might be lowered by xlscc to:
```
tmp0 = sel(a, cases=[result, A])
tmp1 = sel(!a & b, cases=[tmp0, B])
tmp2 = sel(!a & !b & c, cases=[tmp1, C])
out = sel(!a & !b & !c, cases=[tmp2, D])
```
A simpler representation is:
```
tmp0 = sel(c, cases=[D, C])
tmp1 = sel(b, cases=[tmp0, B])
out = sel(a, cases=[tmp1, A])
```
This could be identified using BDD's. Roughly, if the selector of the `n`-th element of the select chain implies the value of the selector for the `n-1`-th for each `n`, then reversal and simplification is possible. One should also consider the inverse cases where (not) selector `n` implies (not) selector `n-1`.
This might dovetail well with #547 which adds a priority select instruction. In this case, the transformation is simpler: reverse the selector bit vector and the data operand order.
Contributor guide
Assessment
This issue has not been assessed yet.