google / google/xls

Hoist operations above selects if it enables constant folding

Open
#1,611 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

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

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.