google / google/xls

Optimize split adds

Open
#144 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

We should be able to simplify an add which has been split into separate adds with a carry between them back into the original add.

Sample input expression:

(u32:x[15:0] + u32:y[15:0]) + (u32:(x[31:16] + y[31:16]) << 16)

Should be simplified to x + y

Here is the IR (attached is IR graph)

fn split_add(x: bits[32], y: bits[32]) -> bits[32] {
literal.131: bits[1] = literal(value=0, pos=0,28,19)
bit_slice.85: bits[16] = bit_slice(x, start=0, width=16, pos=0,21,13)
literal.233: bits[1] = literal(value=0, pos=0,28,19)
bit_slice.87: bits[16] = bit_slice(y, start=0, width=16, pos=0,24,13)
concat.136: bits[17] = concat(literal.131, bit_slice.85, pos=0,27,13)
concat.138: bits[17] = concat(literal.233, bit_slice.87, pos=0,27,16)
add.91: bits[17] = add(concat.136, concat.138, pos=0,27,13)
literal.141: bits[15] = literal(value=0, pos=0,27,8)
bit_slice.227: bits[1] = bit_slice(add.91, start=16, width=1, pos=0,30,9)
bit_slice.86: bits[16] = bit_slice(x, start=16, width=16, pos=0,22,13)
bit_slice.88: bits[16] = bit_slice(y, start=16, width=16, pos=0,25,13)
concat.228: bits[16] = concat(literal.141, bit_slice.227, pos=0,30,9)
add.219: bits[16] = add(bit_slice.86, bit_slice.88, pos=0,28,19)
add.224: bits[16] = add(concat.228, add.219, pos=0,30,9)
bit_slice.230: bits[16] = bit_slice(add.91, start=0, width=16, pos=0,30,9)
ret concat.232: bits[32] = concat(add.224, bit_slice.230, pos=0,30,9)
}

![split_add](https://user-images.githubusercontent.com/24232157/94052162-641c1700-fd8d-11ea-8eb1-ca8dce80417e.png)

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.