Hoist operations above selects if it enables constant folding
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
An operation in which all of its operations are selects on the same predicate can be hoisted above the select, for example:
```
negate(sel(p, [a, b])) => sel(p, [negate(a), negate(b)])
```
An obvious instance where this is advantageous is where the selected operands are constants which then enables constant folding (`a` and `b` are constants in the example).
Example IR which should be optimized but currently isn't:
```
package p
top fn foo(p: bits[1]) -> bits[8] {
c0: bits[8] = literal(value=0xf0)
c1: bits[8] = literal(value=0x0f)
c2: bits[8] = literal(value=0xaa)
c3: bits[8] = literal(value=0x55)
op0: bits[8] = sel(p, cases=[c0, c1])
op1: bits[8] = sel(p, cases=[c2, c3])
ret sum: bits[8] = add(op0, op1)
}
```
This optimization is a special case of the following transform which moves operations across selects:
```
f(sel(p, [a_0, b_0, ...]), sel(p, [a_1, b_1,...]), ...)
<=>
sel(p, [f(a_0, b_,0, ...), f(a_1, b_1, ...), ...])
```
Both directions may be possible/pprofitable. Fundamentally it's trading off multiple instances of a function with specialized parameters vs a single general instance plus/minus some select overhead. In general, there may be area/delay tradeoffs.
Related:
https://github.com/google/xls/issues/938
https://github.com/google/xls/issues/1068
Contributor guide
Assessment
This issue has not been assessed yet.