Jump to content

Sea of nodes

From Wikipedia, the free encyclopedia

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  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 the HotSpot JVM,[5]: 163  LibFirm,[5]: 163  and GraalVM.[5]: 163 [8]: 2 [11] It was also used by 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

[edit]
  1. ^ a b Click, Clifford Noel, Jr. (February 1995). Combining Analyses, Combining Optimizations (PhD thesis). Houston, Texas: Rice University. OCLC 1031097124. UMI Microform 9610626. ProQuest 304234279.{{cite thesis}}: CS1 maint: multiple names: authors list (link)
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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. (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.
  8. ^ 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.
  9. ^ a b "Combining Analyses, Combining Optimizations - Summary". 3 August 2010. Archived from the original on 23 May 2023. Retrieved 7 December 2023.
  10. ^ 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.
  11. ^ 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.
  12. ^ 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

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Sea_of_nodes&oldid=1291978150"