Bitwise Compilation

The pioneers of the computer revolution hand-tuned their programs to take advantage of every architectural resource. As resources became more abundant and datapaths widened, programming styles changed. Programmers paid less attention to details such as the bitwidth (e.g., 1, 8, 16, 32) of program variables. For instance, today it is common to use a 32-bit integer data type to represent boolean variables! How can we explain this apparent programmer apathy?

First of all, memory became less of a commodity, making it unnecessary to waste valuable programmer time packing several sub-word quantities together. In addition, although datapaths became wider, the entire datapath was exercised regardless of operand size. Lastly, the additional overhead of packing and unpacking sub-word quantities -- now only to save abundant memory -- eventually led to performance degradation.

Recent architectural innovations and compilation techniques have re-invigorated the need for accurately specified bitwidths. For instance, recent compiler advances have made it possible to automatically extract data-parallelism from sequential code, dramatically improving performance on processors that support sub-word operations (see the SLP project for more information).

In addition, there has been a recent surge of both academic and industrial interest in creating reconfigurable architectures. For these architectures, bitwidth information is of paramount importance: smaller operand sizes correspond to smaller occupation of the reconfigurable substrate.

We created the Bitwise compiler to automatically determine the bitwidth of program variables. At a high level, Bitwise is a SUIF compiler pass that annotates variables with bitwidth information. The scope of Bitwise includes fixed point arithmetic, bit manipulation and boolean operations. It uses additional sources of information such as type casts, array bounds, and loop iteration counts to refine the bitwidth information gathered. In some cases, Bitwise is able to analyze the bitwidth information as accurately as the bitwidth information gathered from run-time profiles. On average we reduce the size of program scalars by 12% - 80% and program arrays by up to 93%.