SSI Properties Revisited

被引:11
作者
Boissinot, Benoit [1 ]
Brisk, Philip [2 ]
Darte, Alain [1 ]
Rastello, Fabrice [1 ]
机构
[1] UCB Lyon 1, ENS Lyon, CNRS, UMR,LIP,Compsys Team,Inria 5668, Lyon, France
[2] Univ Calif Riverside, Riverside, CA 92521 USA
关键词
Algorithms; Languages; Theory; Control-flow graph; interval graph; liveness analysis; loop nesting forest; static single assignment (SSA); static single information (SSI); intersection/interference graph; program structure tree (PST); REGISTER ALLOCATION; LOOPS;
D O I
10.1145/2180887.2180898
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
The static single information (SSI) form is an extension of the static single assignment (SSA) form, a well-established compiler intermediate representation that has been successfully used for numerous compiler analysis and optimizations. Several interesting results have also been shown for SSI form concerning liveness analysis and the representation of live-ranges of variables, which could make SSI form appealing for just-in-time compilation. Unfortunately, we have uncovered several mistakes in the previous literature on SSI form, which, admittedly, is already quite sparse. This article corrects the mistakes that are most germane to SSI form. We first explain why the two definitions of SSI form proposed in past literature, first by C. S. Ananian, then by J. Singer, are not equivalent. Our main result is then to prove that basic blocks, and thus program points, can be totally ordered so that live-ranges of variables correspond to intervals on a line, a result that holds for both variants of SSI form. In other words, in SSI form, the intersection graph defined by live-ranges is an interval graph, a stronger structural property than for SSA form for which the intersection graph of live-ranges is chordal. Finally, we show how this structure of live-ranges can be used to simplify liveness analysis.
引用
收藏
页数:23
相关论文
共 29 条
[1]  
Alpern B., 1988, Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, P1, DOI 10.1145/73560.73561
[2]  
Ananian C, 1999, MITLCSTR801
[3]  
Appel A.W., 2002, MODERN COMPILER IMPL, V2nd
[4]   Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency [J].
Boissinot, Benoit ;
Darte, Alain ;
Rastello, Fabrice ;
de Dinechin, Benoit Dupont ;
Guillon, Christophe .
CGO 2009: INTERNATIONAL SYMPOSIUM ON CODE GENERATION AND OPTIMIZATION, PROCEEDINGS, 2009, :114-+
[5]  
BOUCHEZ F, 2005, RR200533 LIP ENS LYO
[6]   Register allocation: what does the NP-Completeness proof of chaitin et al. really prove? Or revisiting register allocation: why and how [J].
Bouchez, Florent ;
Darte, Alain ;
Guillon, Christophe ;
Rastello, Fabrice .
LANGUAGES AND COMPILERS FOR PARALLEL COMPUTING, 2007, 4382 :283-+
[7]  
Briggs P, 1998, SOFTWARE PRACT EXPER, V28, P859, DOI 10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO
[8]  
2-8
[9]   Optimal register sharing for high-level synthesis of SSA form programs [J].
Brisk, P ;
Dabiri, F ;
Jafari, R ;
Sarrafzadeh, M .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2005, 25 (05) :772-779
[10]  
Brisk Philip, 2007, P 10 INT WORKSH SOFT, V235, P101, DOI DOI 10.1145/1269843.1269858