Formal Models for Code Generation and Code Compression

Abstract

We propose formal models for the problems of target code generation and compression of tree intermediate code. For the first problem, we adapt an existing model to work for prefix linearizations of intermediate tree code. Experiments have been carried out to generate tables from instruction set grammars for two machines. We have also proposed and implemented an algorithm that tests a machine grammar to check whether code generation can be performed in a single pass. For grammars where this is not possible, we propose an eager code generation strategy, which generates code for a subtree as soon as disambiguation becomes possible. For the second problem, we use the same model in a statistical modeling scheme for compression of code. Since the model is static and grammar-based, it can be used in conjunction with a dynamic context model to make refined estimates of the probability distribution of input symbols. Two features distinguish our model from those previously used for code compression:

Its ability to compactly encode both proximal and distant context, allowing for accurate prediction of input symbols. The use of a uniform approach to efficiently handle both operators and semantic attributes of variables that appear in the code.

Experiments on tree intermediate code indicate that this scheme outperforms standard text compression schemes like gzip and bzip2 for this specialized application, for both small and large files. Also, assuming that the intermediate code has an underlying grammar known to both the sender and the receiver, no information other than the compressed file needs to be transmitted.