RSSA: A Reversible SSA Form View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-06-28

AUTHORS

Torben Ægidius Mogensen

ABSTRACT

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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi $$\end{document}-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. More... »

PAGES

203-217

Book

TITLE

Perspectives of System Informatics

ISBN

978-3-319-41578-9
978-3-319-41579-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-41579-6_16

DOI

http://dx.doi.org/10.1007/978-3-319-41579-6_16

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1027180056


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mogensen", 
        "givenName": "Torben \u00c6gidius", 
        "id": "sg:person.016655503425.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-06-28", 
    "datePublishedReg": "2016-06-28", 
    "description": "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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\phi $$\\end{document}-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.", 
    "editor": [
      {
        "familyName": "Mazzara", 
        "givenName": "Manuel", 
        "type": "Person"
      }, 
      {
        "familyName": "Voronkov", 
        "givenName": "Andrei", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-41579-6_16", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-41578-9", 
        "978-3-319-41579-6"
      ], 
      "name": "Perspectives of System Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "intermediate language", 
      "three-address code", 
      "reversible programming language", 
      "common-subexpression elimination", 
      "reversible updates", 
      "reversible languages", 
      "machine language", 
      "language", 
      "Value Numbering", 
      "first issue", 
      "programming language", 
      "copy propagation", 
      "form", 
      "RSSA", 
      "main issues", 
      "issues", 
      "context", 
      "compiler", 
      "uses", 
      "SSA form", 
      "data-flow analysis", 
      "code", 
      "split", 
      "labels", 
      "numbering", 
      "exchange", 
      "need", 
      "program", 
      "unsuitability", 
      "constant propagation", 
      "analysis", 
      "alternative", 
      "variants", 
      "variables", 
      "update", 
      "join", 
      "allocation", 
      "elimination", 
      "propagation", 
      "SSA", 
      "parameters", 
      "RILs", 
      "reversible variant", 
      "reversible machine language", 
      "reversible intermediate language RIL", 
      "intermediate language RIL", 
      "language RIL", 
      "context of RSSA", 
      "Reversible SSA Form"
    ], 
    "name": "RSSA: A Reversible SSA Form", 
    "pagination": "203-217", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027180056"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-41579-6_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-41579-6_16", 
      "https://app.dimensions.ai/details/publication/pub.1027180056"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_361.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-41579-6_16"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-41579-6_16'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-41579-6_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-41579-6_16'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-41579-6_16'


 

This table displays all metadata directly associated to this object as RDF triples.

114 TRIPLES      23 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-41579-6_16 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Ndd77d70ddd1448458dc3c0e5d3e77c77
4 schema:datePublished 2016-06-28
5 schema:datePublishedReg 2016-06-28
6 schema:description 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi $$\end{document}-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.
7 schema:editor N62f6afad3a944653b21727097a302a24
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N71895d550cc24f99a464f2b14a827c32
12 schema:keywords RILs
13 RSSA
14 Reversible SSA Form
15 SSA
16 SSA form
17 Value Numbering
18 allocation
19 alternative
20 analysis
21 code
22 common-subexpression elimination
23 compiler
24 constant propagation
25 context
26 context of RSSA
27 copy propagation
28 data-flow analysis
29 elimination
30 exchange
31 first issue
32 form
33 intermediate language
34 intermediate language RIL
35 issues
36 join
37 labels
38 language
39 language RIL
40 machine language
41 main issues
42 need
43 numbering
44 parameters
45 program
46 programming language
47 propagation
48 reversible intermediate language RIL
49 reversible languages
50 reversible machine language
51 reversible programming language
52 reversible updates
53 reversible variant
54 split
55 three-address code
56 unsuitability
57 update
58 uses
59 variables
60 variants
61 schema:name RSSA: A Reversible SSA Form
62 schema:pagination 203-217
63 schema:productId N343c60ea2f26498b9cbf354c6d776700
64 N8153bfea10914c43b5bbdab08293f7f1
65 schema:publisher N2f3bcb021ac74574be8b8443641fcf3f
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027180056
67 https://doi.org/10.1007/978-3-319-41579-6_16
68 schema:sdDatePublished 2021-11-01T18:57
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher Nccae9553dbca464aa82df2d323dae5ce
71 schema:url https://doi.org/10.1007/978-3-319-41579-6_16
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N22f7e056e07e430f83bb2acd19af9b15 schema:familyName Mazzara
76 schema:givenName Manuel
77 rdf:type schema:Person
78 N2f3bcb021ac74574be8b8443641fcf3f schema:name Springer Nature
79 rdf:type schema:Organisation
80 N343c60ea2f26498b9cbf354c6d776700 schema:name doi
81 schema:value 10.1007/978-3-319-41579-6_16
82 rdf:type schema:PropertyValue
83 N508eba914ccb4fb2ba518bc35451b8a3 rdf:first N90ebe48c8e8448a8951b4c333b9a7d03
84 rdf:rest rdf:nil
85 N62f6afad3a944653b21727097a302a24 rdf:first N22f7e056e07e430f83bb2acd19af9b15
86 rdf:rest N508eba914ccb4fb2ba518bc35451b8a3
87 N71895d550cc24f99a464f2b14a827c32 schema:isbn 978-3-319-41578-9
88 978-3-319-41579-6
89 schema:name Perspectives of System Informatics
90 rdf:type schema:Book
91 N8153bfea10914c43b5bbdab08293f7f1 schema:name dimensions_id
92 schema:value pub.1027180056
93 rdf:type schema:PropertyValue
94 N90ebe48c8e8448a8951b4c333b9a7d03 schema:familyName Voronkov
95 schema:givenName Andrei
96 rdf:type schema:Person
97 Nccae9553dbca464aa82df2d323dae5ce schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 Ndd77d70ddd1448458dc3c0e5d3e77c77 rdf:first sg:person.016655503425.67
100 rdf:rest rdf:nil
101 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
102 schema:name Language, Communication and Culture
103 rdf:type schema:DefinedTerm
104 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
105 schema:name Linguistics
106 rdf:type schema:DefinedTerm
107 sg:person.016655503425.67 schema:affiliation grid-institutes:grid.5254.6
108 schema:familyName Mogensen
109 schema:givenName Torben Ægidius
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67
111 rdf:type schema:Person
112 grid-institutes:grid.5254.6 schema:alternateName DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark
113 schema:name DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark
114 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...