Sea of nodes: Difference between revisions

Content deleted Content added

Inline

Revision as of 15:48, 7 December 2023

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

^ ^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.{{cite thesis}}: CS1 maint: multiple names: authors list (link)
^ ^a ^b Click, Cliff (June 1995). "Global code motion/global value numbering". Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '95. Association for Computing Machinery: 246–257. doi:10.1145/207110.207154. ISBN 978-0-89791-697-4.
^ ^a ^b Weaver, Glen (November 1995). "Compiler Representations for Heterogeneous Processing". Amherst, MA: Department of Computer Science, University of Massachusetts. CiteSeerX 1728d25c087985261db87bbd892a1aa945ae562a. CMPSCI Techincal Report 95-102 – via CiteSeerX. {{cite web}}: Check |citeseerx= value (help)
^ 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)
^ ^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 International Conference on Compiler Construction. CC 2018 (27th conference). New York, NY, USA: Association for Computing Machinery: 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 – via BINSEC development team via GitHub.
^ Hayes, Ian J.; Utting, Mark; Webb, Brae J. (9 November 2023). Written at Singapore. Li, Yi; Tahar, Sofiène (eds.). "Verifying Compiler Optimisations". Formal Methods and Software Engineering: International Conference on Formal Engineering Methods. Lecture Notes in Computer Science. ICFEM 2023 (24th conference). Brisbane, QLD, Australia: Springer Nature (published 21 November 2023): 3–8. doi:10.1007/978-981-99-7584-6_1. ISBN 978-981-99-7584-6.
^ ^a ^b Webb, Brae J.; Utting, Mark; Hayes, Ian J. (5 July 2021). "A Formal Semantics of the GraalVM Intermediate Representation". arXiv. arXiv:2107.01815. Archived from the original on 7 July 2021. Retrieved 7 December 2023.
^ ^a ^b "Combining Analyses, Combining Optimizations - Summary". 3 August 2010. Archived from the original on 23 May 2023. Retrieved 7 December 2023.
^ ^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 ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages. VMIL 2020 (12th workshop). Association for Computing Machinery: 3. doi:10.1145/3427765.3432354. ISBN 978-1-4503-8190-1.

[: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.{{cite thesis}}: CS1 maint: multiple names: authors list (link)

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

[:2-3] Weaver, Glen (November 1995). "Compiler Representations for Heterogeneous Processing". Amherst, MA: Department of Computer Science, University of Massachusetts. CiteSeerX 1728d25c087985261db87bbd892a1aa945ae562a. CMPSCI Techincal Report 95-102 – via CiteSeerX. {{cite web}}: Check |citeseerx= value (help)

[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] Demange, Delphine; Fernández de Retana, Yon; Pichardie, David (24 February 2018). "Semantic reasoning about the sea of nodes". Proceedings of the International Conference on Compiler Construction. CC 2018 (27th conference). New York, NY, USA: Association for Computing Machinery: 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 – via BINSEC development team via GitHub.

[7] Hayes, Ian J.; Utting, Mark; Webb, Brae J. (9 November 2023). Written at Singapore. Li, Yi; Tahar, Sofiène (eds.). "Verifying Compiler Optimisations". Formal Methods and Software Engineering: International Conference on Formal Engineering Methods. Lecture Notes in Computer Science. ICFEM 2023 (24th conference). Brisbane, QLD, Australia: Springer Nature (published 21 November 2023): 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". arXiv. arXiv:2107.01815. Archived from the original on 7 July 2021. Retrieved 7 December 2023.

[:4-9] "Combining Analyses, Combining Optimizations - Summary". 3 August 2010. Archived from the original on 23 May 2023. Retrieved 7 December 2023.

[:5-10] "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 ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages. VMIL 2020 (12th workshop). Association for Computing Machinery: 3. doi:10.1145/3427765.3432354. ISBN 978-1-4503-8190-1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]