Bit-Level Binding Time Analysis

Abstract

Using a high level language (HLL) to specify a computation for synthesis in ASIC or FPGA hardware requires aggressive compiler analysis to capture bit-level program characteristics that cannot normally be expressed in a HLL but which are important to specializing and optimizing logic for size and speed. It is useful, for instance, to identify unchanging bits of a variable and subsequently remove using partial evaluation any logic which depends on them. We describe a binding-time analysis for bits which can identify static and dynamic bits of computed expressions. The analysis proves to be expensive, possibly taking logarithmically as many steps as the actual binary computation.

Presentation Foils

• Gzipped PostScript version

Report

• Gzipped PostScript version
• PDF version

People

• Eylon Caspi -- author
• Alex Aiken -- course professor

The Course

This report describes a course project for Alex Aiken's graduate course, "CS-263: Design and Analysis of Programming Languages," at U.C.Berkeley's Computer Science department, spring 1998 semester. The course dealt primarily with the formal semantics of programming languages. Language analysis included the study of operational/denotational/axiomatic semantics, lattices, abstract interpretation, data-flow, and set constraints. Language case studies included Lambda Calculus, Standard ML, C++, Java, RLL, and CLU.