google / google/xls

Opportunistically reverse select chain order

Open
#549 0 comments 0 reactions 0 assignees View on GitHub
optimizer
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

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.