RSSA: a reversible SSA form

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

The SSA form (Static Single Assignment form) is used in compilers as an intermediate language as an alternative to traditional three-address code because code in SSA form is easier to analyse and optimize using data-flow analysis such as common-subexpression elimination, value numbering, register allocation and so on. We introduce RSSA, a reversible variant of the SSA form suitable as an intermediate language for reversible programming languages that are compiled to reversible machine language. The main issues in making SSA reversible are the unsuitability for SSA of the reversible updates and exchanges that are traditional in reversible languages and the need for ϕ-nodes on both joins and splits of control-flow. The first issue is handled by making selected uses of a variable destroy the variable and the latter by adding parameters to labels. We show how programs in the reversible intermediate language RIL can be translated into RSSA and discuss copy propagation, constant propagation and register allocation in the context of RSSA.

Original languageEnglish
Title of host publicationPerspectives of System Informatics : 10th International Andrei Ershov Informatics Conference, PSI 2015, Revised Selected Papers
EditorsManuel Mazzara, Andrei Voronkov
Number of pages15
PublisherSpringer
Publication date2016
Pages203-217
ISBN (Print)978-3-319-41578-9
ISBN (Electronic)978-3-319-41579-6
DOIs
Publication statusPublished - 2016
Event10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics, PSI 2015 - Kazan and Innopolis, Russian Federation
Duration: 24 Aug 201527 Aug 2015

Conference

Conference10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics, PSI 2015
LandRussian Federation
ByKazan and Innopolis
Periode24/08/201527/08/2015
SeriesLecture notes in computer science
Volume9609
ISSN0302-9743

ID: 168284239