Sea of nodes

A sea of nodes is a graph representation of single-static assignment (SSA) representation of a program that combines data flow and control flow, and relaxes the control flow from a total order to a partial order, keeping only the orderings required by data flow.^[1]^: 86,113^[2]^: 248^[3]^: 11^[4]^[5]^: 163^[6]^: 25^[7]^[8]^: 2 It is similar to a value dependency graph (VDG).^[9]^: 1

It makes it easier for an optimizer to reorder instructions, but requires a global code motion algorithm to convert it back into a control flow graph (CFG).^[1]^: 86,113^[2]^: 248^[3]^: 14^[10] It allows dead code elimination and constant propagation to be done together, which allows both optimizations to apply more often.^[9]^: 4

It is used as an intermediate representation (IR) in HotSpot,^[5]^: 163 LibFirm,^[5]^: 163 GraalVM,^[5]^: 163^[8]^: 2^[11] and V8's TurboFan JIT compiler.^[10]

References

^ Jump up to: ^a ^b 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.
^ Jump up to: ^a ^b 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.
^ Jump up to: ^a ^b 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.
^ Indutny, Fedor (8 October 2015). "Sea of Nodes". Compilers. Fedor Indutny's Blog. Archived from the original on 20 October 2023. Retrieved 7 December 2023. d.sea-of-nodes.md in indutny/blog.ng on GitHub. {{cite web}}: External link in |postscript= (help)CS1 maint: postscript (link)
^ Jump up to: ^a ^b ^c ^d 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.
^ 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.
^ Jump up to: ^a ^b 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.
^ Jump up to: ^a ^b "Combining Analyses, Combining Optimizations - Summary". 3 August 2010. Archived from the original on 23 May 2023. Retrieved 7 December 2023.
^ Jump up to: ^a ^b "Digging into the TurboFan JIT: More sophisticated optimizations". Internals. V8 JavaScript engine blog. 13 July 2015. Archived from the original on 24 May 2023. Retrieved 7 December 2023.
^ 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] Jump up to: ^a ^b 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] Jump up to: ^a ^b 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] Jump up to: ^a ^b 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. Archived from the original on 20 October 2023. Retrieved 7 December 2023. d.sea-of-nodes.md in indutny/blog.ng on GitHub. {{cite web}}: External link in |postscript= (help)CS1 maint: postscript (link)

[:3-5] Jump up to: ^a ^b ^c ^d 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] Jump up to: ^a ^b 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] Jump up to: ^a ^b "Combining Analyses, Combining Optimizations - Summary". 3 August 2010. Archived from the original on 23 May 2023. Retrieved 7 December 2023.

[:5-10] Jump up to: ^a ^b "Digging into the TurboFan JIT: More sophisticated optimizations". Internals. V8 JavaScript engine blog. 13 July 2015. Archived from the original on 24 May 2023. Retrieved 7 December 2023.

[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]