google / google/xls

[enhancement] missed optimization opportunity for duplicated logic in `sel` branches

Open
#1,482 0 comments 0 reactions 0 assignees View on GitHub
enhancement optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 12h
Merged PRs (30d)
130

Description

### What's hard to do? (limit 100 words)

When refactoring deep `if` branches for readability in DSLX code one sometime encapsulates logic into `fn`s that get called w/ a few different parameters and return the same result type.

This can negatively impact the PPA:
- logic get duplicated across `sel` branches, bumping the gate count and the resulting area.
- `sel` would get wider to accomodate unified return type resulting in worst timing.

### (convoluted) example

[![colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/gist/proppy/ad7accddd27bd287e6330a7f76d56ef7/learn-xls-in-y-minutes.ipynb)

The following code:
```
fn opt1(sign: u1, a: u8, b: u1) -> u8 {
a + if sign {
// sign positive: increment a w/ b
b
} else {
// sign negative: invert increment
!b
} as u8
}
```
results in the following schedule:

![Image](https://github.com/google/xls/assets/5268/c4861cc2-6979-4d1d-888b-0579271b831c)

and the following BoM:

![Image](https://github.com/google/xls/assets/5268/7b70244b-c8e5-4063-8930-e662214cde37)

While the "refactored" version:

```
fn sign_positive (a:u8, b:u1) -> u8 {
a + b as u8
}

fn sign_negative(a:u8, b:u1) -> u8 {
a + !b as u8
}

fn opt2(sign: u1, a: u8, b: u1) -> u8 {
if sign == u1:0 {
sign_positive(a, b)
} else {
sign_negative(a, b)
}
}
```

results in a worst schedule (+40ps, because of the wider `sel`):

![Image](https://github.com/google/xls/assets/5268/41e5696b-0532-402c-b640-ea6e31c76683)

and an increased BoM (1 additional `add(u8, u8)`):

![Image](https://github.com/google/xls/assets/5268/ebaee084-d190-4e4f-9b01-482d45a815b4)

### Current best alternative workaround (limit 100 words)

One workaround could be to add additional arguments to the refactored function to share some common computation done ahead of the `sel` and return intermediate result to narrow the size of `sel`; lessening encapsulation and potentially going back to negatively impacting readability.

### Your view of the "best case XLS enhancement" (limit 100 words)

It would be nice if `opt_main` could detect `sel` w/ logic `duplicated` on each branches and move the common logic ahead of the `sel`.

This would likely result in sensible area saving and (limited) timing improvement.

Contributor guide

Open the contributing guide

Research direction

Start with the `opt_main` optimization pass and the DSLX examples in the issue, comparing the generated schedules and Bills of Materials for `opt1` and `opt2`. Done means duplicated branch logic is detected and moved ahead of the `sel` without requiring manual workaround arguments, with area and timing improvements demonstrated on a representative case.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
28/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.