Comparison and evaluation of back-translation algorithms for static single assignment forms

作     者：Sassa, Masataka Ito, Yo Kohama, Masaki 

作者机构：Tokyo Inst Technol Dept Math & Comp Sci Meguro Ku Tokyo 1528552 Japan 

出 版 物：《COMPUTER LANGUAGES SYSTEMS & STRUCTURES》 (计算机语言、系统与结构)

年 卷 期：2009年第35卷第2期

页      面：173-195页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Japanese Ministry of Education, Culture, Sports, Science and Technology Japan Society for the Promotion of Science Kayamori Foundation for Informational Science Advancement 

主　　题：Static single assignment form Back-translation Intermediate language Machine-independent program transformation Compiler 

摘      要：The static single assignment form (SSA form) is a popular intermediate representation in compilers. In the SSA form, the definition of each variable textually appears only once in the program by using a hypothetical function called a phi-function. Because these functions are nonexecutable, it is necessary to delete the phi-functions and return the SSA form to the normal form before code generation. This conversion is called SSA back-translation. Two major algorithms exist for SSA back-translation. One by Briggs et al., the other by Sreedhar et al. To date, there has been almost no research that compares these SSA back-translation algorithms. In this paper, we clarify the merits and demerits of these algorithms. We also propose an improvement to Briggs algorithm. We then compare the three methods through experiments using the SPEC benchmarks. Our experiments show that in most cases, Sreedhar s method is the more favorable. The efficiency of its object code is better than that from Briggs method by a few percent in general, up to a maximum of 28%. The experiments have also clarified several characteristic features of these methods. (C) 2007 Elsevier Ltd. All rights reserved.