TY - GEN

T1 - A type system equivalent to static single assignment

AU - Matsuno, Yutaka

AU - Ohori, Atsushi

PY - 2006

Y1 - 2006

N2 - This paper develops a static type system equivalent to static single assignment (SSA) form. In this type system, a type of a variable at some program point represents the control flows from the assignment statements that reach the program point. For this type system, we show that a derivable typing of a program corresponds to the program in SSA form. By this result, any SSA transformation can be interpreted as a type inference process in our type system. By adopting a result on efficient SSA transformation, we develop a type inference algorithm that reconstructs a type annotated code from a given code. These results provide a static alternative to SSA based compiler optimization without performing code transformation. Since this process does not change the code, it does not incur overhead due to insertion of φ functions. Another advantage of this type based approach is that it is not constrained to naming mechanism of variables and can therefore be combined with other static properties useful for compilation and code optimization such as liveness information of variables. As an application, we express optimizations as type-directed code transformations.

AB - This paper develops a static type system equivalent to static single assignment (SSA) form. In this type system, a type of a variable at some program point represents the control flows from the assignment statements that reach the program point. For this type system, we show that a derivable typing of a program corresponds to the program in SSA form. By this result, any SSA transformation can be interpreted as a type inference process in our type system. By adopting a result on efficient SSA transformation, we develop a type inference algorithm that reconstructs a type annotated code from a given code. These results provide a static alternative to SSA based compiler optimization without performing code transformation. Since this process does not change the code, it does not incur overhead due to insertion of φ functions. Another advantage of this type based approach is that it is not constrained to naming mechanism of variables and can therefore be combined with other static properties useful for compilation and code optimization such as liveness information of variables. As an application, we express optimizations as type-directed code transformations.

KW - Compiler optimization

KW - Static single assignment form

KW - Type system

UR - http://www.scopus.com/inward/record.url?scp=33750910969&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750910969&partnerID=8YFLogxK

U2 - 10.1145/1140335.1140365

DO - 10.1145/1140335.1140365

M3 - Conference contribution

AN - SCOPUS:33750910969

SN - 1595933883

SN - 9781595933881

T3 - PPDP'06 - Proceedings of the Eight ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming

SP - 249

EP - 259

BT - PPDP'06 - Proceedings of the Eight ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming

PB - Association for Computing Machinery

T2 - PPDP'06 - 8th ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming

Y2 - 10 July 2006 through 12 July 2006

ER -