and their applications. SMC is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a member of
A Complete Transformational Toolkit for Compilers
rarely. We therefore believe that the exposition of the process, especially for a nontrivial program logic such as PIM, is itself a useful contribution. The remainder of this paper proceeds as follows: In Section 2, we give an overview of PIM and discuss related work. In Section 3, we introduce the system PIMt, which axiomatizes the behavior of PIM’s rst-order core. P IM0 has the property that orienting its equations from left to right yields t an interpreter for closed programs producing observable“base” values as results. We discuss the behavior of PIMt’s functions using examples written in a simple programming language. Section 4 gives an overview using examples of the relative power of the equational axiomatization of PIMt’s initial algebra semantics (PIM0 ), the initial algebra axiomatization of PIMt’s nal algebra semantics t (PIM+ ), and an ! -complete enrichment of PIM+, PIM= . Section 5 discusses the relationship between t t t !-complete equational systems and partial evaluation. In Section 6, we make some basic de nitions and illustrate the process by which we develop a complete logic using an example involving a stack data type. Next, in Section 7, we develop an enrichment of PIM0 called PIM+ that characterizes PIMt’s t t nal algebra semantics; i.e., one that equates terms that behave the same in all contexts that generate observable values. Such a semantics is natural for developing semantics-preserving transformations on program fragments. In Section 8, we produce our main result: an ! -complete axiomatization PIM= t for PIM+ . As before, PIM= is obtained simply by enriching PIM+ with additional equations. The t t t resulting system equates all open PIMt programs that behave the same under every substitution for their free variables, and thus yields the complete tran
sformational toolkit we seek. In Section 9, we show how rewriting systems formed by orienting subsystems of PIM= can be used to prove program t equivalences and produce normal forms with various interesting properties. We then develop several rewriting systems based on PIM= and prove that they are con uent and terminating. Finally, Section 10 t covers possible extensions and open problems.
2
PIM in Perspective
While there has been considerable work on calculi and logics of program equivalence for imperative languages, our work has the following points of departure: A graph form of PIM is by design closely related to popular intermediate representations (IRs) used in optimizing compilers, such as the PDG[17], SSA form[12], GSA form[3], the PRG[44], the VDG[41], and the representation of Click[11]. Indeed, PIM can be regarded as a rational reconstruction of elements of the earlier IRs. With the exception of the VDG and Click’s representation, PIM differs from the other IRs in that procedures, functions, and computations on addresses (e.g., as required for arrays or pointers) are“ rst-class” features of the formalism. What sets PIM apart from other IR work, however, is not so much the form of its graphs, but rather the existence of a logic for reasoning about equivalences, carrying out partial evaluation, and performing analysis. For structured programs, most of the non-trivial steps required to translate a program to the P IM analogue of one of the IRs mentioned above can be carried out as source-to-source transformations in PIM itself, once an initial PIM graph has been constructed from the program using a simple syntax-directed translation. For example, when constructing the PIM equivalent of GSA 3
A complete transformatio... 暂无评价 48页 免费 Toward a complete transf.....for the verification of PIM- a transformational toolkit for compilers隐藏>> ...
A complete transformatio... 暂无评价 48页 免费 Toward a complete transf.....for the verification of PIM- a transformational toolkit for compilers隐藏>> ...
热门文档