[enhancement][opt] Fuse `sign_ext(carry)` + `add` + `literal(1)` into a single carry‑in adder
- 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
Assessment
This issue has not been assessed yet.