google / google/xls

[enhancement][opt] Fuse `sign_ext(carry)` + `add` + `literal(1)` into a single carry‑in adder

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

Description

The pattern

```xls_ir
cext = sign_ext(carry, new_bit_count=N)
t1 = add(x, cext)
one = literal(value=1)
sum = add(t1, one)
```

currently stays as **two** N‑bit adders after optimization. We should automatically rewrite it into

```xls_ir
one = literal(value=1)
zero = literal(value=0)
inc = sel(carry, cases=[one, zero])
sum = add(x, inc)
```

which lowers to a **single** N‑bit adder with carry‑in, cutting gate count and depth.

Said another way for why this is suboptimal:

- Two’s‑complement subtraction: add(x, sign_ext(carry)) is really x − carry.
- Wraparound +1: the subsequent +1 turns that into x + (1 − carry).
- Conditional increment: since carry is 0 or 1, this ends up doing “increment by one” when carry==0, and “no increment” when carry==1.
- Double adder: hardware sees two back‑to‑back adders (and a sign‑ext), doubling both gate count and carry‑chain depth.

### Proposal
Add an IR‑level pass (e.g. in `narrowing_pass.cc` or a new `carryin_fusion_pass.cc`) that:

**Matches** the pattern:
```xls_ir
cext = sign_ext(carry, new_bit_count=N)
t1 = add(x, cext)
one = literal(value=1)
sum = add(t1, one)
```
**Rewrites** it to:
```xls_ir
one = literal(value=1)
zero = literal(value=0)
inc = sel(carry, cases=[one, zero])
sum = add(x, inc)
```

This will expose the carry‑in explicitly and let downstream passes (and gate mapping) produce a single adder.

### Repro Steps

1. **Create two IR files:**

**add_with_cast2.ir**
```xls_ir
package add_with_cast2_pkg
top fn add_with_cast2(x: bits[8] id=1, carry: bits[1] id=2) -> bits[8] {
cext: bits[8] = sign_ext(carry, new_bit_count=8, id=3)
tmp: bits[8] = add(x, cext, id=4)
one: bits[8] = literal(value=1, id=5)
sum: bits[8] = add(tmp, one, id=6)
ret out: bits[8] = identity(sum, id=7)
}
```

**add_with_sel3.ir**
```xls_ir
package add_with_sel3_pkg
top fn add_with_sel3(x: bits[8] id=1, carry: bits[1] id=2) -> bits[8] {
one: bits[8] = literal(value=1, id=3)
zero: bits[8] = literal(value=0, id=4)
inc: bits[8] = sel(carry, cases=[one, zero], id=5)
sum: bits[8] = add(x, inc, id=6)
ret out: bits[8] = identity(sum, id=7)
}
```

2. **Optimize & map to gates:**
(Using xlsynth-driver 0.0.119 for repro convenience.)
```bash
xlsynth-driver ir2opt --top add_with_cast2 add_with_cast2.ir > cast2.opt.ir
xlsynth-driver ir2opt --top add_with_sel3 add_with_sel3.ir > sel3.opt.ir

xlsynth-driver ir2gates --quiet=true cast2.opt.ir > cast2.rtl.json
xlsynth-driver ir2gates --quiet=true sel3.opt.ir > sel3.rtl.json

jq '.live_nodes, .deepest_path' cast2.rtl.json
jq '.live_nodes, .deepest_path' sel3.rtl.json
```

You'll see that add_with_cast2.ir, while equivalent, takes about twice as many (abstract) gates on account of having two `add()` nodes -- we could rely on synthesis tools to optimize it away but it seems like a bad idea to have both of these looking like adder delay for XLS delay modeling.

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.