IIR: an Identifier-based Intermediate Representation To Support Declarative Compiler Specifications

概要

論文の詳細を見る
For compiler developers, one big issue is how to describe a specification of its intermediate representation (IR), which consists of various entities like symbol tables, syntax trees, analysis information and so on. As IR is a central data structure of a compiler, its precise specification is always strongly desired. However, the formalization of an actual IR is not an easy task since it tends to be large, has complex interdependency between its entities, and depends on a specific implementation language. In this paper, as a first step to solve this problem, we propose a new data model for IR, called IIR. The goal of IIR is to describe a specification of IR declaratively without depending on its concrete implementation detail. The main idea is to model all entities of IR as relations with explicit identifiers. By this, we can develop an IR model transliterally from an actual IR, and describe its specification by using the full expressiveness of conventional logic languages. The specification is inherently executable and can be used to check the validity of IR in compile time. As a practical case study, we formalized an IR of our production compiler in IIR, and developed a type system for it in Prolog. Experimental results about size and performance are shown.