Computer Science Department
School of Computer Science, Carnegie Mellon University
BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations
Mihai Budiu, Seth Copen Goldstein
October 2000
An abridged version of this text appeared in the
Proceedings of
the 6th International Euro-Par Conference,
August 2000, published in LN CS 1900 by Springer Verlag
CMU-CS-00-141.ps
CMU-CS-00-141.pdf
We present a compiler algorithm called BitValue, which can discover
unused and constant bits in dusty-deck C programs. BitValue uses
forward and backward dataflow analyses, generalizing constant-folding
and dead-code detection at the bit-level. This algorithm enables
compiler optimizations targeting special processor architectures for
computing on non-standard bitwidths.
Using this algorithm we show that up to 36% of the computed bytes are thrown away; also, we show that on average 26.8% of the values computed require 16 bits or less (for programs from SpecINT95 and Mediabench). A compiler for reconfigurable hardware uses this algorithm to achieve substantial reductions (up to 20-fold) in the size of the synthesized circuits.
28 pages
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu
School of Computer Science homepage