  Manual optimization of Register Transfer Level (RTL) datapath is commonplace
in industry but holds back development as it can be very time consuming. We
utilize the fact that a complex transformation of one RTL into another
equivalent RTL can be broken down into a sequence of smaller, localized
transformations. By representing RTL as a graph and deploying modern graph
rewriting techniques we can automate the circuit design space exploration,
allowing us to discover functionally equivalent but optimized architectures. We
demonstrate that modern rewriting frameworks can adequately capture a wide
variety of complex optimizations performed by human designers on bit-vector
manipulating code, including significant error-prone subtleties regarding the
validity of transformations under complex interactions of bitwidths. The
proposed automated optimization approach is able to reproduce the results of
typical industrial manual optimization, resulting in a reduction in circuit
area by up to 71%. Not only does our tool discover optimized RTL, but also
correctly identifies that the optimal architecture to implement a given
arithmetic expression can depend on the width of the operands, thus producing a
library of optimized designs rather than the single design point typically
generated by manual optimization. In addition, we demonstrate that prior
academic work on maximally exploiting carry-save representation and on multiple
constant multiplication are both generalized and extended, falling out as
special cases of this paper.
