google / google/xls

Narrowing needs to track replaced input values

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

Description

Consider code like the following:

```
(eq? ([zero_extend 32] (and_reduce x:u8))
([zero_extend 32] (and_reduce [(zero_extend 9) y:u8]))
```

or

```
fn example(a: u8, b: u8) -> uN[1] {
(and_reduce(a) as u32) == (and_reduce(b as u9) as u32)
}
```

For any 8-bit y the second `eq?` argument reduces to `0` since the highest bit is always unset.

For the first argument only 2 values are possible, `0` and `1`. This means we should be able to replace the 32-bit comparison with a 1 bit comparison.

(NB this example actually will be reduced due to other passes, as range analysis gets more sophisticated this can cause us to miss optimizations however).

This is caused by using the current inputs of the cmp (and add, mul, & array-index) when trying to narrow the cmp operation. We should use the 'original' arguments to ensure we get correct intervals and ternary information.

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.