Static Single Information form (SSI) is a program representation that enables optimizations such as array bound checking elimination and conditional constant propagation. Transforming a program into SSI form has a non-negligible impact on compilation time; but, only a few SSI clients, that is, optimizations that use SSI, require a full conversion. This paper describes the SSI framework we have implemented for the LLVM compiler, and that is now part of this compiler's standard distribution. In our design, optimizing passes inform the compiler a list of variables of interest, which are then transformed to present, fully or partially, the SSI properties. It is provided to each client only the subset of SSI that the client needs. Our implementation orchestrates the execution of clients in sequence, avoiding redundant work when two clients request the conversion of the same variable. As empirically demonstrated, in the context of an industrial strength compiler, our approach saves compilation time and keeps the program representation small, while enabling a vast array of code optimizations.
"Efficient SSI Conversion"
André Tavares and Fernando Magno Pereira and Mariza Bigonha and Roberto Bigonha
In Proceedings of the 14th Brazilian Symposium on Programming Languages, Salvador, Brazil, September 2010.
@INPROCEEDINGS{x:2010,
AUTHOR="André Tavares and Fernando Magno Pereira and Mariza Bigonha and
Roberto Bigonha",
TITLE="Efficient SSI Conversion",
BOOKTITLE="SBLP 2010",
ADDRESS="",
DAYS="27-29",
MONTH="sep",
YEAR="2010",
ABSTRACT="Static Single Information form (SSI) is a program
representation that enables optimizations such as array bound checking
elimination and conditional constant propagation. Transforming a program
into SSI form has a non-negligible impact on compilation time; but, only
a few SSI clients, that is, optimizations that use SSI, require a full
conversion. This paper describes the SSI framework we have implemented
for the LLVM compiler, and that is now part of this compiler's standard
distribution.In our design, optimizing passes inform the compiler a list
of variables of interest, which are then transformed to present, fully
or partially, the SSI properties. It is provided to each client only the
subset of SSI that the client needs. Our implementation orchestrates the
execution of clients in sequence, avoiding redundant work when two
clients request the conversion of the same variable. As empirically
demonstrated, in the context of an industrial strength compiler, our
approach saves compilation time and keeps the program representation
small, while enabling a vast array of code optimizations.",
KEYWORDS="Program transformations; Program analysis and verification;
Compilation and interpretation techniques",
URL="http://llvm.org/pubs/2010-08-SBLP-SSI.pdf",
}