Sea of nodes

From HandWiki

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](p86,113)[2](p248)[3](p11)[4][5](p163)[6](p25)[7][8](p2) It is similar to a value dependency graph (VDG).[9](p1)

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](p86,113)[2](p248)[3](p14)[10] It allows dead code elimination and constant propagation to be done together, which allows both optimizations to apply more often.[9](p4)

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

References

  1. ↑ 1.0 1.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.
  2. ↑ 2.0 2.1 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. https://dl.acm.org/doi/10.1145/207110.207154. 
  3. ↑ 3.0 3.1 Weaver, Glen (November 1995). "Compiler Representations for Heterogeneous Processing". Department of Computer Science, University of Massachusetts. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1728d25c087985261db87bbd892a1aa945ae562a. 
  4. ↑ Indutny, Fedor (8 October 2015). "Sea of Nodes". https://darksi.de/d.sea-of-nodes/. d.sea-of-nodes.md in indutny/blog.ng on GitHub. 
  5. ↑ 5.0 5.1 5.2 5.3 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. 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. https://inria.hal.science/hal-01723236/. 
  6. ↑ Lemerre, Matthieu (2023-01-11). "SSA Translation Is an Abstract Interpretation". Proceedings of the ACM on Programming Languages. POPL 7 (65): 1895–1924. doi:10.1145/3571258. https://binsec.github.io/assets/publications/papers/2023-popl-full-with-appendices.pdf. 
  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 (in en). Formal Methods and Software Engineering. Lecture Notes in Computer Science. 14308. Brisbane, QLD, Australia: Springer Nature. 21 November 2023. pp. 3–8. doi:10.1007/978-981-99-7584-6_1. ISBN 978-981-99-7584-6. https://dl.acm.org/doi/abs/10.1007/978-981-99-7584-6_1. 
  8. ↑ 8.0 8.1 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. 12971. pp. 111–126. doi:10.1007/978-3-030-88885-5_8. ISBN 978-3-030-88884-8. 
  9. ↑ 9.0 9.1 "Combining Analyses, Combining Optimizations - Summary". 2010-08-03. https://static.squarespace.com/static/50030e0ac4aaab8fd03f41b7/50030ec0e4b0c0ebbd07b0e0/50030ec0e4b0c0ebbd07b268/1281379125883/. 
  10. ↑ 10.0 10.1 "Digging into the TurboFan JIT: More sophisticated optimizations". 13 July 2015. https://v8.dev/blog/turbofan-jit#more-sophisticated-optimizations. 
  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. https://dl.acm.org/doi/abs/10.1145/3427765.3432354. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Sea_of_nodes&oldid=3372751"