Detecting and Exploiting Narrow Bitwidth Computations

Many important applications perform computations on non-standard bit-width values; mapping them to word-based processing units is wasteful of resources and results in suboptimal performance. While there are some processor architecture innovations which take advantage of varying bit-widths, compiler optimizations lag far behind. We present a compiler algorithm which infers minimal widths and constant bits using several program analyses. We present forward analyses, which compute the signs, find bits independent of the inputs and find constant bits; we describe a backward analysis, which discovers bits unused by the output; we also describe a mixing analysis, which trims all unnecessary work from the computation, by using the results of the other analyses. We show how these techniques can be used in a compiler for reconfigurable hardware to achieve substantial reductions in the size of the synthesized circuits (up to 20 times). We also show how the algorithm can be used to anal..