BitValue Inference: Detecting and ExploitingNarrow Bitwidth ComputationsMihai Budiu Seth Copen GoldsteinJune 2000CMU-CS-00-141School of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213An abridged version of this text appeared in the Proceedings of 6th InternationalEuro-Par Conference, August 2000, published in LNCS 1900 by Springer Verlag.AbstractWe present a compiler algorithm called BitValue, which can discover unused and constantbits in dusty-deck C programs. BitValue uses forward and backward dataflow analyses,generalizing constant-folding and dead-code detection at the bit-level. This algorithmenables compiler optimizations targeting special processor architectures for computing onnon-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 (forprograms from SpecINT95 and Mediabench). A compiler for reconfigurable hardware usesthis algorithm to achieve substantial reductions (up to 20-fold) in the size of the synthesizedcircuits.This work was supported by DARPA contract DABT63-96-C-0083 and an NSF CAREER grant.Keywords: Compilation, dataflow analysis, reconfigurable hardware, CAD tools1 IntroductionAs the natural word width of processors increases, so grows the gap between the numberof bits used and those actually required for a computation. Recent architectural propos-als have addressed this inefficiency by providing collections of narrow functional units orthe ability to construct functional units on the fly. For example, instruction set exten-sions which support subword parallelism (e.g. [10]), Application-Specific Instruction-setProcessors (ASIPs) (e.g. [9]), and reconfigurable devices (e.g. [11]) all allow operations onoperands which are smaller than the natural word size.Reconfigurable computing devices are the most efficient at supporting arbitrary sizedata because they can be programmed post-fabrication to implement functions directly ashardware circuits. In such devices it is possible to create functional units which exactlymatch the bit-widths of the data values on which they compute.State of the art methods for using the special architectural features require the program-mer to use macro libraries or specify the bit-widths manually, a tedious and error-proneprocess. Furthermore, there is little or no support in high-level languages for specifyingarbitrary bit-widths.In this paper we present BitValue, an algorithm which enables the compilation ofunannotated high-level languages to take advantage of variable size functional units. Ourtechnique uses dataflow analysis to discover bits which are independent of the programinputs (constant bits) and bits which do not influence the program output (unused bits).By eliminating computations of both constant and unused bits the resulting program canbe made more efficient.BitValue generalizes constant folding and dead-code elimination to operate on individ-ual bits. When used on C programs, BitValue determines that a significant number ofthe bit operations performed are unnecessary: on average 14% of the computed bytes inprograms from SpecINT95 and 21% of the bytes in Mediabench are useless. Our techniquealso enables the programmer to use standard language constructs to pass width informationto the compiler using masking operations.Narrow width information can be used to help create code for sub-word parallel func-tional units. It can also be used to automatically find configurations for reconfigurabledevices. BitValue has been implemented in a compiler which generates configurations forreconfigurable devices, reducing circuit size by factors of three to twenty.Contributions. We summarize here the contributions of this paper:• We formulate the problem of bit-value inference as a dataflow problem, of inferringthe value of each computed bit (as one of “constant”, “useful bit”, “don’t care”).• We give an algorithm to solve the bit-value inference problem.• We evaluate the implementation of our algorithm in a C compiler and in a compilerfor reconfigurable hardware.• We measure the effects of our analysis for detecting narrow widths in programs fromSpecINT95 and Mediabench.1• We measure the reductions in circuit size due to our algorithm in a compiler forreconfigurable hardware.In Section 2 we present our BitValue inference algorithm. Section Section 3 shows thealgorithm in action on two examples. Results for the implementation in a C compiler arein Section 4 and for a reconfigurable hardware compiler in Section 5. Related work ispresented in Section 6 and we conclude in Section 7.2 The BitValue Inference AlgorithmFor each bit of an arbitrary-precision integer, our algorithm determines whether (1) it has aconstant value, or (2) its value does not influence the visible outputs of the program. Thosetwo possibilities are similar to constant folding and dead code elimination, respectively. Inour setting, however, these are performed at the bit-level within each word.We can cast our problem as a type-inference problem, where the type of a variabledescribes the possible value that each bit can have during an execution of the program.The BitValue algorithm solves this problem using dataflow analysis. In this section weintroduce first the dataflow lattice, we present the transfer functions, we give an outline ofthe algorithm and conclude with two examples.01UXFigure 1: The bit values lattice. The ordering is defined by the “information content”.The Bit-value Lattice. We represent the bit values by one of: h0i, h1i, don’t know(denoted by hui)anddon’t care, (denoted by hxi). Let us call this set of values B.Somebits are constant, independent of the inputs and control flow of the program; such bits arelabeled with their value, h0i or h1i. A bit is labeled hxi if it does not affect the output;otherwise a bit is labeled hui. These bit values form a lattice, depicted in Figure 1. Wewrite ∪ and ∩ for sup and inf in the lattice respectively. The top element of the lattice >is hxi and the bottom ⊥ is hui.The Bit String Lattice. We represent the type of each value in the program as a stringof bits. We write B∗to denote all strings of values in B. For example, for the C statement1unsigned char a = b & 0xf0,wedeterminethatthetypeofais huuuu0000i,andthatthetypeofb, assuming it is dead after this statement, is huuuuxxxxi. A regular 8-bit valueabout which we know nothing is