google / google/xls

Implement Proc state optimization

Open
#561 1 comment 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

In many cases it may be possible to reduce the size of the proc state. The proc state translates directly to registers so a reduction in state size results in a reduction in the number of registers. The proc state is a single value of arbitrary type and typically includes multiple elements in a tuple. Optimizations can reduce the number and size of these elements. Possible optimizations:

* Remove dead state. The simplest example of this is a state element which has no users. Clearly such an element can be removed. More generally, if a state element is not observable (never reaches a side-effecting op) then removal of the state element is possible. This may include a connected set of elements which may collectively affect each other but none of the elements are observable.

* Remove invariant state. A state element may never change. Such an element can be replaced with a literal.

* Narrowing. The range of values a state element can assume may be limited and the width of the element is over-sized. In this case the element could be narrowed to just enough bits to cover the possible range of the value. In general determining the range of a state element is complicated. This involves determining the evolution of the state value as the proc iterates. This is analogous to scalar evolution in traditional compilers which is an important (and advanced) loop analysis. In general, you can't just run the proc to fixed point or until you find a cycle of state because that may take exponential time.

* A state element may assume only a small number of values and these values may not be densely packed near zero which would be handled by narrowing. An example might be a state element can assume the value 123 or 42. Rather than using 8-bits to store the value a single bit can be used to indicate whether the value is 123 or 42. A select statement in the body provides the actual value (123 or 42) based on the state bit.

* Eliminate redundant state. A state element may be always equivalent to another state element. In this case, one of the element might be removed. A generalization is that a state element can be easily reconstructed from another state element.

* Share registers with state elements which are use mutually exclusively. A state element may be used only for certain iterations of a proc. Outside these iterations the state storage the this element might be usable for different state element which is used in a mutually exclusive set of iterations. Predicated nodes as described in #552 may be of use here.

Splitting the proc state into a vector of values would facilitate these transformations because tuples can be awkward to manipulate. #548

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.