Representation of a program
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] : 3 [ 8] : 2 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] 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 the HotSpot JVM,[ 5] : 163 LibFirm ,[ 5] : 163 GraalVM .[ 5] : 163 [ 8] : 2 [ 11] V8 's TurboFan JIT compiler , but in 2022 they decided that it was poorly suited for JavaScript 's dynamicity , thereby making development and debugging too difficult, and so they decided to develop Turboshaft as a replacement, going back to using a CFG IR.[ 10] [ 12]
References
^ a b Click, Clifford Noel, Jr. (February 1995). Combining Analyses, Combining Optimizations OCLC 1031097124 . UMI Microform 9610626. ProQuest 304234279 . {{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 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 b Weaver, Glen (November 1995). Compiler Representations for Heterogeneous Processing (PDF) (Report). Amherst, MA: Department of Computer Science, University of Massachusetts. CMPSCI Techincal [sic] Report 95-102. ACM Digital Library 897299 . CiteSeerX 1728d25c087985261db87bbd892a1aa945ae562a . ^ Indutny, Fedor (8 October 2015). "Sea of Nodes" . Compilers. Fedor Indutny's Blog . d.sea-of-nodes.md in indutny/blog.ng on GitHub . Archived from the original on 20 October 2023. Retrieved 7 December 2023 . ^ 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. (21–24 November 2023). "Verifying Compiler Optimisations" (Invited Paper) . In Li, Yi; Tahar, Sofiène (eds.). Formal Methods and Software Engineering: 24th International Conference on Formal Engineering Methods, ICFEM 2023; Brisbane, QLD, Australia, November 21–24, 2023; Proceedings . Lecture Notes in Computer Science. Vol. 14308. Springer Nature. pp. 3– 8. doi :10.1007/978-981-99-7584-6_1 . ISBN 978-981-99-7584-6 Abstract also available from ACM Digital Library . ^ 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 . ^ a b "Combining Analyses, Combining Optimizations - Summary" . 3 August 2010. Archived from the original on 23 May 2023. Retrieved 7 December 2023 .^ a b Titzer, Ben L. (13 July 2015). "Digging into the TurboFan JIT: More sophisticated optimizations" . Internals. V8 JavaScript engine [blog] . Archived from the original on 24 May 2023. Retrieved 7 December 2023 . ^ Seaton, Chris (17 November 2020). "Understanding Graal IR" (Invited Talk) . Proceedings of the 12th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages . VMIL '20. New York, NY, USA: Association for Computing Machinery. p. 3. doi :10.1145/3427765.3432354 . ISBN 978-1-4503-8190-1 S2CID 227154653 . ^ Mercadier, Darius (25 March 2025). "Land ahoy: leaving the Sea of Nodes" . JavaScript; internals. V8 JavaScript engine [blog] . Archived from the original on 1 May 2025. Retrieved 17 May 2025 .
Further reading
