Sea of nodes

Asea of nodesis agraphrepresentation ofsingle-static assignment (SSA)representation of a program that combinesdata flowandcontrol flow,and relaxes thecontrol flowfrom atotal orderto apartial order,keeping only the orderings required bydata flow.^[1]^: 86,113^[2]^: 248^[3]^: 11^[4]^[5]^: 163^[6]^: 25^[7]^[8]^: 2It is similar to a valuedependency graph(VDG).^[9]^: 1

It makes it easier for an optimizer to reorder instructions, but requires a globalcode motionalgorithm to convert it back into acontrol flow graph (CFG).^[1]^: 86,113^[2]^: 248^[3]^: 14^[10]It allowsdead code eliminationandconstant propagationto be done together, which allows both optimizations to apply more often.^[9]^: 4

It is used as anintermediate representation (IR)inHotSpot,^[5]^: 163LibFirm,^[5]^: 163GraalVM,^[5]^: 163^[8]^: 2^[11]andV8's TurboFanJIT compiler.^[10]

References

^^a ^bClick, Clifford Noel Jr. (February 1995).Combining Analyses, Combining Optimizations(PhD thesis). Thesis Committee: Keith D. Cooper, Robert Bixby, Mark W. Krentel, Linda Torczon. Houston, Texas: Rice University.OCLC 1031097124.UMI Microform 9610626 – via Rice Research Repository, Rice Fondren Library.
^^a ^bClick, Cliff (June 1995)."Global code motion/Global value numbering".Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation.PLDI '95. Association for Computing Machinery. pp. 246–257.doi:10.1145/207110.207154.ISBN 978-0-89791-697-4.S2CID 14257734.
^^a ^bWeaver, Glen (November 1995)."Compiler Representations for Heterogeneous Processing".Amherst, MA: Department of Computer Science, University of Massachusetts. CMPSCI Techincal [sic] Report 95-102 – via CiteSeerX.
^Indutny, Fedor (8 October 2015)."Sea of Nodes".Compilers.Fedor Indutny's Blog.Archivedfrom the original on 20 October 2023.Retrieved7 December2023.d.sea-of-nodes.md in indutny/blog.ng on GitHub.{{cite web}}:External link in|postscript=(help)CS1 maint: postscript (link)
^^a ^b ^c ^dDemange, Delphine; Fernández de Retana, Yon; Pichardie, David (24 February 2018)."Semantic reasoning about the sea of nodes".Proceedings of the 27th International Conference on Compiler Construction(PDF).Vol. CC 2018 (27th conference). New York, NY, USA: Association for Computing Machinery. pp. 163–173.doi:10.1145/3178372.3179503.ISBN 978-1-4503-5644-2.S2CID 3390229.
^Lemerre, Matthieu (11 January 2023)."SSA Translation Is an Abstract Interpretation"(PDF).Proceedings of the ACM on Programming Languages.POPL.7(65): 1895–1924.doi:10.1145/3571258.S2CID 254566327– via BINSEC development team via GitHub.
^Hayes, Ian J.; Utting, Mark; Webb, Brae J. (9 November 2023)."Verifying Compiler Optimisations: (Invited Paper)".Written at Singapore. In Li, Yi; Tahar, Sofiène (eds.).Formal Methods and Software Engineering.Lecture Notes in Computer Science. Vol. 14308. Brisbane, QLD, Australia: Springer Nature (published 21 November 2023). pp. 3–8.doi:10.1007/978-981-99-7584-6_1.ISBN 978-981-99-7584-6.
^^a ^bWebb, Brae J.; Utting, Mark; Hayes, Ian J. (5 July 2021). "A Formal Semantics of the GraalVM Intermediate Representation".Automated Technology for Verification and Analysis.Lecture Notes in Computer Science. Vol. 12971. pp. 111–126.arXiv:2107.01815.doi:10.1007/978-3-030-88885-5_8.ISBN 978-3-030-88884-8.S2CID 235732254.
^^a ^b"Combining Analyses, Combining Optimizations - Summary".3 August 2010.Archivedfrom the original on 23 May 2023.Retrieved7 December2023.
^^a ^b"Digging into the TurboFan JIT: More sophisticated optimizations".Internals.V8 JavaScript engine blog.13 July 2015.Archivedfrom the original on 24 May 2023.Retrieved7 December2023.
^Seaton, Chris (15 November 2020)."Understanding Graal IR (Invited talk)".Proceedings of the 12th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages.VMIL 2020 (12th workshop). Association for Computing Machinery. p. 3.doi:10.1145/3427765.3432354.ISBN 978-1-4503-8190-1.S2CID 227154653.

[:0-1] Click, Clifford Noel Jr. (February 1995).Combining Analyses, Combining Optimizations(PhD thesis). Thesis Committee: Keith D. Cooper, Robert Bixby, Mark W. Krentel, Linda Torczon. Houston, Texas: Rice University.OCLC 1031097124.UMI Microform 9610626 – via Rice Research Repository, Rice Fondren Library.

[:1-2] Click, Cliff (June 1995)."Global code motion/Global value numbering".Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation.PLDI '95. Association for Computing Machinery. pp. 246–257.doi:10.1145/207110.207154.ISBN 978-0-89791-697-4.S2CID 14257734.

[:2-3] Weaver, Glen (November 1995)."Compiler Representations for Heterogeneous Processing".Amherst, MA: Department of Computer Science, University of Massachusetts. CMPSCI Techincal [sic] Report 95-102 – via CiteSeerX.

[4] Indutny, Fedor (8 October 2015)."Sea of Nodes".Compilers.Fedor Indutny's Blog.Archivedfrom the original on 20 October 2023.Retrieved7 December2023.d.sea-of-nodes.md in indutny/blog.ng on GitHub.{{cite web}}:External link in|postscript=(help)CS1 maint: postscript (link)

[:3-5] Demange, Delphine; Fernández de Retana, Yon; Pichardie, David (24 February 2018)."Semantic reasoning about the sea of nodes".Proceedings of the 27th International Conference on Compiler Construction(PDF).Vol. CC 2018 (27th conference). New York, NY, USA: Association for Computing Machinery. pp. 163–173.doi:10.1145/3178372.3179503.ISBN 978-1-4503-5644-2.S2CID 3390229.

[6] Lemerre, Matthieu (11 January 2023)."SSA Translation Is an Abstract Interpretation"(PDF).Proceedings of the ACM on Programming Languages.POPL.7(65): 1895–1924.doi:10.1145/3571258.S2CID 254566327– via BINSEC development team via GitHub.

[7] Hayes, Ian J.; Utting, Mark; Webb, Brae J. (9 November 2023)."Verifying Compiler Optimisations: (Invited Paper)".Written at Singapore. In Li, Yi; Tahar, Sofiène (eds.).Formal Methods and Software Engineering.Lecture Notes in Computer Science. Vol. 14308. Brisbane, QLD, Australia: Springer Nature (published 21 November 2023). pp. 3–8.doi:10.1007/978-981-99-7584-6_1.ISBN 978-981-99-7584-6.

[:6-8] Webb, Brae J.; Utting, Mark; Hayes, Ian J. (5 July 2021). "A Formal Semantics of the GraalVM Intermediate Representation".Automated Technology for Verification and Analysis.Lecture Notes in Computer Science. Vol. 12971. pp. 111–126.arXiv:2107.01815.doi:10.1007/978-3-030-88885-5_8.ISBN 978-3-030-88884-8.S2CID 235732254.

[:4-9] "Combining Analyses, Combining Optimizations - Summary".3 August 2010.Archivedfrom the original on 23 May 2023.Retrieved7 December2023.

[:5-10] "Digging into the TurboFan JIT: More sophisticated optimizations".Internals.V8 JavaScript engine blog.13 July 2015.Archivedfrom the original on 24 May 2023.Retrieved7 December2023.

[11] Seaton, Chris (15 November 2020)."Understanding Graal IR (Invited talk)".Proceedings of the 12th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages.VMIL 2020 (12th workshop). Association for Computing Machinery. p. 3.doi:10.1145/3427765.3432354.ISBN 978-1-4503-8190-1.S2CID 227154653.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]